Участник:Gmorgachev/ex-no-enumeration-of-cycled

Материал из DISCOPAL
Перейти к: навигация, поиск

Формально об алгоритмах. Вычислительные модели/Задачи/ex-no-enumeration-of-cycled


Пусть существует машина Тьюринга, выписывающая все машины Тьюринга M, неостанавливающиеся на пустом слове.

Тогда для каждой машины Тьюринга N определим N', которая, если N остановилась, начинает бесконечно выписывать нули.

StasFomin (обсуждение) 10:03, 29 марта 2018 (MSK): Ну и получаем гарантированно зацикленную машину N', из факта зацикленности которой нельзя сделать никакого вывода про N. Задачу разбирали на семинаре, есть в видео лекций, вспоминайте или смотрите.


Тогда для любой МТ A, МТ M выдаст когда-то либо машину Тьюринга A либо A'. Следовательно, определяем, останавливается ли A на пустом слове или нет. Следовательно задача HALT, остановки на пустом слове, разрешима.

Противоречие.