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

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

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

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

Добавить i-ю машину в лист
Подать на вход i-ой машине пустую ленту
for each j in list:
Сделать следующий шаг на j-ой машине тьюринга
Если j-я машина остановилась, выписать ее

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

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

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

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