Формально об алгоритмах. Вычислительные модели/Задачи/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.