Есть функция $$p^\ast:S\to N$$ $$\epsilon\mapsto p_2(0,0)\\n\mapsto p_2(0,n+1)\\ (n_1,\dots, n_k)\mapsto p_2(k-1,p_k(n_1,\dots,n_k))$$

Для любой $%f:N\to N$% определим $%\bar f:N\to N$% $$\bar f(0)=p^\ast(\epsilon)\\ \bar f(n+1)=p^\ast(f(0),\dots,f(n))$$ (То есть $%\bar f(n+1)=F(\bar f(n), f(n))$% где $%F$% - примитивно рекурсивная функция из вопроса)

Пусть $%g:N\to N$%. Тогда существует единственнаая $%f:N\to N$% такая что $%f(n)=g(\bar f(n))$%

Докажите, что $%f$% примитивно рекурсивна если $%g$% примитивно рекурсивна

задан 10 Ноя '19 19:24

изменен 10 Ноя '19 19:26

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,113

задан
10 Ноя '19 19:24

показан
138 раз

обновлен
10 Ноя '19 19:26

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

по почте:

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

по RSS:

Ответы

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

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