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