Можно ли построить turing-machine, у которого есть другая turing-machine и строку в качестве входных данных и принимает, будет ли полученная машина двигаться влево или вправо (или что-либо еще) для этой строки?
Машина Тьюринга, которая принимает другую машину Тьюринга, если она делает определенный ход
comment
Я думаю, что это должно быть возможно, если смоделировать аргументную машину Тьюринга на этой строке и посмотреть, какие ходы она делает. Поэтому, если аргумент TM останавливается на строке, наш тоже останавливается. Это не так уж отличается от создания универсальной машины Тьюринга.
- person Kolmar schedule 31.01.2015
comment
Похоже на решение проблемы остановки.
- person GSerg schedule 31.01.2015
comment
@GSerg Нет, это не так. Проблема с остановкой является проблемой только потому, что если эмулируемая программа не останавливается по истечении времени x, никакого прироста знаний не происходит.
- person Peter - Reinstate Monica schedule 31.01.2015
comment
Что ж, если возможно, что полученная машина не останавливается вместо принятия решения, то, очевидно, это проблема остановки. Если OP означает, что полученная машина сделает правильный ход вместо чего-то другого, но конечного, то это не проблема остановки, поскольку полученная машина всегда останавливается.
- person Peter - Reinstate Monica schedule 31.01.2015
comment
К ОП: комментарием выше я также хотел сказать, что нашел вопрос несколько неясным ;-). Хотите уточнить?
- person Peter - Reinstate Monica schedule 31.01.2015
Ответы (1)
Нет. Создание такой машины требует решения проблемы остановки. Чтобы показать это, предположим, что ваши входные данные — это машина Тьюринга T, и я пропускаю их через другую машину, которая изменяет каждую инструкцию halt с помощью turn left, за которой следует halt. Затем я загружаю эту новую машину T' в вашу машину-кандидата. Чтобы ваша машина правильно определяла, будет ли T' turn left, она должна решить проблему остановки.
person
MooseBoys
schedule
31.01.2015
