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

Версия 11:58, 11 октября 2020

Существует ли алгоритм, который выписывает одну за другой все машины Тьюринга, которые останавливаются, будучи запущенными на пустой ленте?

@@ Строка 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.
-[[Категория:На проверку]]