Есть функция $$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))$$

Хотим найти функцию $%s:N\to N$% такую, что для любой последовательности $%(x_1,\dots,x_n)$% $$s(p^\ast(x_1,\dots,x_n))=\sum_i x_i$$ следующим способом:

Найдите вычислимую функцию $%\alpha$% для которой $$\alpha(x)=last(x)+\alpha(exceptlast(x))$$

(определения last и exceptlast ниже) и потом докажите требуемое равенство по индукции.

Определим $%exceptlast(x)=p_2(f_{12}(x)-1,f_{12}(f_{22}(x)))$% где $%f_{jk}(p_k(x_1,\dots,x_k))=x_j$%. Имеем $$exceptlast(p^\ast(x_1,\dots,x_k))=p^\ast(x_1,\dots,x_{k-1})$$

Определим функцию $%last$% для которой $$last(p^\ast(x_1,\dots,x_k))=x_k$$ (например $%last(x)=x$% если длина последовательности, кодом которой является $%x$%, есть 1; и $%last(x)=f_{22}(f_{22}(x))$% если эта длина более 1)

Можно пользоваться теоремой о рекурсии: $%\forall p\exists q\forall r\ \phi_q(r)=\phi_p(q,r)$% и существованием универсальной программы $%u$% для которой $%\phi_u(p)=x\iff \phi_p()=x$%

задан 10 Ноя '19 0:27

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

Ваш ответ

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

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

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

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

отмечен:

×49

задан
10 Ноя '19 0:27

показан
201 раз

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

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

по почте:

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

по RSS:

Ответы

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

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