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

Версия 00:31, 26 декабря 2014

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

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

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

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

i++

for each j in list:

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

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

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