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