Формально об алгоритмах. Вычислительные модели/Задачи/ex-no-enumeration-of-cycled
Докажите, что не существует алгоритма, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте.
Стенина Мария, группа 974
Заметим сперва, что существует алгоритм, который выписывает все МТ, которые останавливаются на пустом входе. Этот алгоритм перебирает все возможные пары (M, n), для каждой пары запуская машину M на n тактов, затем смотрит, остановилась ли M. Если остановилась, то ее заносим в список, если нет, то берем следующую пару. Чтобы этот процесс перебирал поочередно все машины, пары надо перебирать змейкой: (1, 1)->(1, 2)->(2, 2)->(2, 1)->(3, 1)->(3, 2)->(3, 3)->(2, 3)...
Если теперь предположить, что еще существует и алгоритм, который выписывает все МТ, которые не останавливаются на пустом входе, то можно построить алгоритм, который проверяет, останавливается ли произвольная МТ на пустом входе. Для этого достаточно запустить оба выписывающих алгоритма и ждать, пока интересующая МТ появится в одном из списков. Однако, как известно, задача определения останова произвольной МТ на пустом входе не разрешима. Отсюда заключаем, что алгоритма, который выписывает все МТ, не останавливающиеся на пустом входе, не существует.
[ Хронологический вид ]Комментарии
Пусть существует алгоритм А, выписывающий одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте. Каждой МТ Х поставим в соответствие МТ Х0, которая запускается на пустой ленте и за первые шаги переходит в начальное состояние Х(если после этого запустить Х и Х0, они будут работать одинаково).
Возьмем произвольную МТ М, ей соответствует М0. Запускаем М и МТ, реализующую алгоритм А. Дальее возможны два исхода:
1) М остановится.
2) Алгоритмом А будет выписана М0. Значит, М0 не останавливается, и М не останавливается.
В результате для произвольной МТ М решена проблема остановки. ПРОТИВОРЕЧИЕ. Следовательно, алгоритма А не существует.
Войдите, чтобы комментировать.