Формально об алгоритмах. Вычислительные модели/Задачи/ex-no-enumeration-of-cycled — различия между версиями
StasFomin (обсуждение | вклад) |
|||
| Строка 3: | Строка 3: | ||
запущенными на пустой ленте. | запущенными на пустой ленте. | ||
| − | [[Category: | + | [[Category:На проверку]] |
<!--Вообще-то, решения уже есть--> | <!--Вообще-то, решения уже есть--> | ||
| + | |||
| + | ===Стенина Мария, группа 974=== | ||
| + | |||
| + | Заметим сперва, что существует алгоритм, который выписывает все МТ, которые ''останавливаются'' на пустом входе. Этот алгоритм перебирает все возможные пары (M, n), для каждой пары запуская машину M на n тактов, затем смотрит, остановилась ли M. Если остановилась, то ее заносим в список, если нет, то берем следующую пару. Чтобы этот процесс перебирал поочередно все машины, пары надо перебирать змейкой: (1, 1)->(1, 2)->(2, 2)->(2, 1)->(3, 1)->(3, 2)->(3, 3)->(2, 3)... | ||
| + | |||
| + | Если теперь предположить, что еще существует и алгоритм, который выписывает все МТ, которые ''не останавливаются'' на пустом входе, то можно построить алгоритм, который проверяет, останавливается ли произвольная МТ на пустом входе. Для этого достаточно запустить оба выписывающих алгоритма и ждать, пока интересующая МТ появится в одном из списков. Однако, как известно, задача определения останова произвольной МТ на пустом входе не разрешима. Отсюда заключаем, что алгоритма, который выписывает все МТ, не останавливающиеся на пустом входе, не существует. | ||
Версия 17:19, 9 ноября 2014
Докажите, что не существует алгоритма, который выписывает одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте.
Стенина Мария, группа 974
Заметим сперва, что существует алгоритм, который выписывает все МТ, которые останавливаются на пустом входе. Этот алгоритм перебирает все возможные пары (M, n), для каждой пары запуская машину M на n тактов, затем смотрит, остановилась ли M. Если остановилась, то ее заносим в список, если нет, то берем следующую пару. Чтобы этот процесс перебирал поочередно все машины, пары надо перебирать змейкой: (1, 1)->(1, 2)->(2, 2)->(2, 1)->(3, 1)->(3, 2)->(3, 3)->(2, 3)...
Если теперь предположить, что еще существует и алгоритм, который выписывает все МТ, которые не останавливаются на пустом входе, то можно построить алгоритм, который проверяет, останавливается ли произвольная МТ на пустом входе. Для этого достаточно запустить оба выписывающих алгоритма и ждать, пока интересующая МТ появится в одном из списков. Однако, как известно, задача определения останова произвольной МТ на пустом входе не разрешима. Отсюда заключаем, что алгоритма, который выписывает все МТ, не останавливающиеся на пустом входе, не существует.