Формально об алгоритмах. Вычислительные модели/Задачи/ex-exists-enumeration-of-halts — различия между версиями
Материал из DISCOPAL
| Строка 8: | Строка 8: | ||
:''Добавить i-ю машину в лист''<br /> | :''Добавить i-ю машину в лист''<br /> | ||
:''Подать на вход i-ой машине пустую ленту''<br /> | :''Подать на вход i-ой машине пустую ленту''<br /> | ||
| + | :''i++''<br/> | ||
:''for each j in list:''<br /> | :''for each j in list:''<br /> | ||
::''Сделать следующий шаг на j-ой машине тьюринга''<br /> | ::''Сделать следующий шаг на j-ой машине тьюринга''<br /> | ||
Версия 21:13, 9 октября 2014
Маркеева Лариса 973б
Предположим, что мы пронумеровали все МТ(их счетное число, как известно).
Рассмотрим следующий алгоритм:
i=0
list=[]
while(true)
- Добавить i-ю машину в лист
- Подать на вход i-ой машине пустую ленту
- i++
- for each j in list:
- Сделать следующий шаг на j-ой машине тьюринга
- Если j-я машина остановилась, выписать ее
- Сделать следующий шаг на j-ой машине тьюринга
Очевидно, что если МТ останавливается на пустом входе, то рано или поздно алгоритм обнаружит эту остановку, иначе машина будет вечно находиться в list.