Артур Дент, используя технологию космической эры, еще не доступную на Земле, разработал алгоритм, который определяет, останавливается или нет TM M1 при запуске на пустой ленте. Но позже он обнаружил, что смысл жизни, вселенной и всего остального - 42.
(a) [5] Учитывая TM M2, докажите, что Артур может определить, останавливается ли M2 на входе 42, используя уже разработанную им программу, которая определяет, останавливается или нет TM M1 при запуске на пустой ленте. Если вы создаете новую TM в своей проверке, дайте ее машинную схему.
(b) [5] Предположим, что существует программа, которая быстрее, чем программа Артура, но она отвечает на вопрос, останавливается ли TM M2 на входе 42. Объясните, как Артур может использовать этот алгоритм, чтобы определить, останавливается ли какой-то TM M1 при запуске с пустого поля. Лента. Если вы создаете новую TM в своей проверке, дайте ее машинную схему.
(c) [5] Мы доказали на занятии, что проблема определения остановки TM M при запуске на пустой ленте не разрешима. Можно ли использовать часть (a) или часть (b), чтобы доказать, что невозможно также определить, останавливается ли TM M на входе 42?
Может ли кто-нибудь помочь мне расшифровать, о чем здесь говорит мой профессор?
