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

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

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

[ Хронологический вид ]Комментарии

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


Пусть существует алгоритм А, выписывающий одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте. Каждой МТ Х поставим в соответствие МТ Х0, которая запускается на пустой ленте и за первые шаги переходит в начальное состояние Х(если после этого запустить Х и Х0, они будут работать одинаково).

Возьмем произвольную МТ М, ей соответствует М0. Запускаем М и МТ, реализующую алгоритм А. Дальее возможны два исхода:

1) М остановится.

2) Алгоритмом А будет выписана М0. Значит, М0 не останавливается, и М не останавливается.

В результате для произвольной МТ М решена проблема остановки. ПРОТИВОРЕЧИЕ. Следовательно, алгоритма А не существует.

Войдите, чтобы комментировать.