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

Ссылки сюда (14) →

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

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

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

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

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

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

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

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

— Девицкий Иван 375 • 13 мая 2016 в 21:55 последняя правка 13 мая 2016 в 21:55

• страница

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