Определение примитивно рекурсивных функций.

Имеет место равенство:

alt text

($%(n)_i$% определяется тут, что взято из этого вопроса)

Требуется как-то использовать это равенство для того, чтобы определить функцию $%\ast$% на натуральных числах такую, что $%s(n\ast m)=s(n)+s(m)$% (плюс обозначает конкатенацию слов, определение $%s(n)$% снова тут). Например, $%3\ast 4=16,\ 4\ast 3=19$%, ибо

alt text

задан 13 Окт '19 21:13

2

@logic: математическое выражение для функции f(n,m)=n*m легко выписать. Это будет (m+1)2^{[log_2(n+1)]}-1. Дальше надо изучить главу учебника Мендельсона о рекурсивных функциях. Там последовательно строятся функции delta(x)=x-1 (x>=1), delta(0)=0; затем сложение x+y, умножение xy (по рекурсии); степень 2^x (также по рекурсии). Основное -- построить [log_2(x+1)] -- целая часть двоичного логарифма. Для этого надо знать конструкцию ограниченного мю-оператора.

(14 Окт '19 3:59) falcao

А как до такого выражения можно додуматься? Оно как-то использует данное в условии равенство?

Квадратные скобки обозначают целую часть? Если да, то округление вниз?

У Мендельсона построение сложения, умножения, степени нашел. Определение ограниченного мю-оператора там тоже есть, но его применения к логарифму нет. И тогда еще надо доказывать, что целая часть - примитивно рекурсивная функция.

(14 Окт '19 4:15) logic
1

@logic: тут всё следует из описания кодирования. Берутся двоичные разложения n+1 и m+1, от второго убираем первую единицу, приписываем, и вычитаем 1 из результата. Например, при n=3, m=4 имеем n+1=100, m+1=101, затем 10001, и минус 1 будет 10000=16.

Квадратные скобки -- обычная школьная целая часть.

Позже напишу, как работать с y=[log_2(x+1)]. Надо построить сначала при помощи мю-оператора, потом добавить ограничение по x и сослаться на теорию.

(14 Окт '19 12:47) falcao

А почему этот процесс (убирание первой единицы и приписывание результата справа описывается как произведение квадрата m+1 на логарифм?

(14 Окт '19 16:07) logic
1

@logic: там m+1 домножается на два в степени. Но к этому я забыл прибавить n+1 без первой единицы. Формула будет чуть отличаться, но строится она таким же способом.

(14 Окт '19 16:13) falcao

Как тогда итоговая формула будет выглядеть? Возникновения 2 в степени логарифма я пока не понял тоже.

(14 Окт '19 19:44) logic
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
2

Запишем сначала математическую формулу для $%n\ast m$%. Напомним, что мы записываем числа $%n+1$%, $%m+1$% в двоичной системе счисления. Далее убираем первую единицу в записи второго числа, приписываем результат к записи первого, и в самом конце вычитаем единицу.

Пусть за первой единицей в записи $%m+1$% находится $%k$% двоичных разрядов. Тогда $%2^k\le m+1 < 2^{k+1}$%, то есть $%k\le\log_2(m+1) < k+1$%. Отсюда $%k=\lfloor\log_2(m+1)\rfloor$%. Теперь мы вычитаем $%2^k$% из $%m$%, получая $%k$%-разрядное число $%m+1-2^k$%. К записи числа $%n+1$% мы сначала приписываем $%k$% нулей, что соответствует умножению на $%2^k$%. Затем прибавляем последние $%k$% разрядов, и вычитаем $%1$%, получая $%n\ast m=(n+1)2^k+m+1-2^k-1=n2^k+m$%.

Для примера: $%n=3$%, $%m=4$%; $%k=\lfloor\log_2(m+1)\rfloor=\lfloor\log_25\rfloor=2$%, откуда $%3\ast4=3\cdot2^2+4=16$%. Аналогично, при $%n=4$%, $%m=3$% имеем $%k=2$%, и $%4\ast3=4\cdot2^2+3=19$%.

Поскольку сложение, умножение, и возведение в степень -- это примитивно-рекурсивные функции (см. Мендельсон), достаточно доказать, что функция $%y=\lfloor\log_2(x+1)\rfloor$% примитивно-рекурсивна. Вспоминаем, что $%2^y\le x+1< 2^{y+1}$%, поэтому $%y$% есть наименьшее число, для которого $%x+1 < 2^{y+1}$%. Последнее условие равносильно тому, что $%\overline{\rm sg}(2^{y+1}-(x+1))=0$%. (Минус должен быть с точечкой сверху, как ограниченная разность, но я не помню, как набирать такой символ.)

Теперь выражаем функцию при помощи $%\mu$%-оператора: $%f(x)=\mu_y(\overline{\rm sg}(2^{y+1}-(x+1))=0)$%. Здесь мы временно выходим за рамки примитивно-рекурсивных операторов, но достаточно заметить, что $%y < 2^y\le x+1$%, откуда $%y\le x$%. Теперь можно выразить функцию $%f(x)=\lfloor\log_2(x+1)\rfloor$% через ограниченный $%\mu$%-оператор: $%f(x)=\mu_{y\le x}(\overline{\rm sg}(2^{y+1}-(x+1))=0)$%. Здесь уже всё примитивно-рекурсивно, согласно теории.

ссылка

отвечен 14 Окт '19 23:02

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×32

задан
13 Окт '19 21:13

показан
588 раз

обновлен
14 Окт '19 23:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru