Пусть f(x) — количество единиц в бинарной записи числа x. Докажите, что функция f(x) является примитивно рекурсивной

задан 5 Мар 1:23

возвращен 14 Мар 22:10

falcao's gravatar image


227k2845

@Cookie: удалять условия задач нельзя -- тем более уже решённых. Это противоречит правилам форума. Я всё возвращаю на место, и закрываю вопрос.

(14 Мар 22:09) falcao
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Проблема не актуальна". Закрывший - falcao 14 Мар 22:10

0

При практическом вычислении значения такой функции мы обычно используем рекурсивный вызов той же процедуры. То есть полагаем f(x)=0, и далее при x > 0 имеем f(x)=f(x/2) для чётного x и f(x)=1+f((x-1)/2) для нечётного x. Этот способ хорошо и быстро работает, но для приспособления к стандартной схеме рекурсии мы должны возвращаться к значению функции для числа, меньшего на 1. Это побуждает несколько изменить сам процесс вычислений.

Продемонстрируем идею на таком примере. Пусть нас интересует значение f(123). Мы имеем f(123)=1+f(61)=2+f(30)=2+f(15)=... . Будем считать, что мы работаем с парами (0,123), (1,61), (2,30), (2,15) и так далее, где первый элемент -- это "копилка", в которой запоминается уже зарегистрированное на данный момент число единиц в двоичной записи, а второй элемент означает число, которое надо подвергнуть обработке. Процесс оканчивается, когда второй элемент равен нулю; первый элемент представляет собой значение функции.

От пары (x,y) мы за один шаг переходим к паре (u,v), где v=[y/2], и u=x+y-2[y/2]. Используемые при этом функции примитивно-рекурсивны, что уже должно быть к этому моменту известно. Разность здесь рассматривается как ограниченная.

Переход от пары к следующей описывается рекурсивными функциями. Способ кодирования пар также должен быть построен -- это стандартный способ нумерации пар по принципу (0,0), (1,0), (0,1), (2,0), (1,1) , (0,2) , ... (нумерация с нуля). Номер пары (x,y) даётся многочленом от x, y, явную формулу для которого нетрудно выписать. Обратные функции, которые по номеру пары n находят её первый и второй элемент, также строятся без проблем и являются примитивно-рекурсивными (см. учебник Мендельсона, где рассматривается ограниченный мю-оператор).

После такого кодирования пар мы имеем конкретную примитивно-рекурсивную функцию ф(n), которая по номеру n пары (x,y) выдаёт номер пары (u,v), описанной выше. Теперь берём пару (0,x) в качестве начальной (нулевой шаг), и строим функцию psi(t), которая при t=0 даёт номер пары (0,x), а psi(t+1) равно ф(psi(t)). Это укладывается в схему рекурсии.

После достаточного числа итераций получится пара (f(x),0), которая далее уже не будет меняться. Ясно, что x итераций точно хватит (достаточно примерно логарифма), и тогда psi(x)=(f(x),0), и остаётся взять первый элемент пары.

ссылка

отвечен 5 Мар 4:54

10|600 символов нужно символов осталось
Если вы не нашли ответ, задайте вопрос.

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

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

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

отмечен:

×4

задан
5 Мар 1:23

показан
103 раза

обновлен
14 Мар 22:10

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

по почте:

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

по RSS:

Ответы

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

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