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