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

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

Маркеева Лариса 973б

Предположим, что мы пронумеровали все МТ(их счетное число, как известно).
Рассмотрим следующий алгоритм:
i=0
list=[]
while(true)

Добавить i-ю машину в лист

Подать на вход i-ой машине пустую ленту

i++

for each j in list:

Сделать следующий шаг на j-ой машине тьюринга

Если j-я машина остановилась, выписать ее

Очевидно, что если МТ останавливается на пустом входе, то рано или поздно алгоритм обнаружит эту остановку, иначе машина будет вечно находиться в list.

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

(нет элементов)

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