Будем работать с регистровыми машинами. Назовем программой некоторую последовательность нулей и единиц (удовлетворяющую некоторым условиям). Если $%P$% программа, то $%P=x$% означает, что если запустить программу $%P$% со словами $%w_i$% (в алфавите 0,1) в регистре $%i$%, то в конце концов программа завершит работу и выдаст слово $%x$% в первом регистре. Если $%P$% не программа, то $%P$% не определено.

Как, используя $%s_n^m$%-теорему, теорему о рекурсии и универсальную программу доказать, что существует программа $%P$% такая, что для любого слова $%w$%, $$P=w?$$


Факты, которые упомянуты выше:

  • $%s_n^m$% теорема: Существует программа $%s_n^m$% такая что $$[s_n^m](p,q_1,\dots,q_m)=p$$

  • теорема о рекурсии: Для любой программы $%p$% существует программа $%q$% такая, что для всех слов $%w$%, $$q=p$$

  • универсальная программа: $%u$% - программа, для которой $%u=x\iff p=x$%

задан 14 Окт '19 4:35

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

Ваш ответ

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

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

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

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

отмечен:

×32

задан
14 Окт '19 4:35

показан
378 раз

обновлен
14 Окт '19 4:35

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

по почте:

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

по RSS:

Ответы

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

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