Учитывая кодировку конкретной машины Тьюринга, можно ли решить, остановится ли она на конкретном входе?
Скажем, у меня есть универсальная машина Тьюринга, кодирующая конкретную машину Тьюринга T. Также скажите, что у меня есть кодировка конкретного ввода s. Вопрос о том, останавливается ли T на s, разрешим? Можно ли использовать симуляцию бега T на s, чтобы получить ответ?
1 ответ
Эта проблема разрешима во всех случаях. Любая конкретная фиксированная ТМ либо останавливается, либо не останавливается на каком-либо конкретном фиксированном входе, предполагая, что исключенная середина - это не то, что вы хотите здесь оспорить. Для конкретного случая вашей проблемы, когда вы фиксируете ТМ и ввод, ТМ должен либо прекратить прием для всех входов (не конкретный фиксированный вход, с которым вы параметризируете проблему, а типичный вход для ТМ, который будет решить нашу параметризованную проблему), если этот конкретный случай, если проблема имеет остановку TM на входе, или она должна halt-reject если этот конкретный экземпляр имеет TM, который не может быть остановлен.
Сложность состоит в том, что для любого конкретного случая проблемы мы знаем, что конкретный TM либо останавливается, либо не дает конкретного ввода, но у нас нет какого-либо эффективного в вычислительном отношении способа узнать, в чем дело. Конечно, одно или другое (опять же, принимаете ли вы исключенную середину, является более широким обсуждением), и, следовательно, конкретный случай проблемы можно решить - даже регулярно - но это не слишком нам помогает, кроме как для понимания вычислимости немного лучше.
Обратите внимание, что есть много случаев этой проблемы, где мы могли бы знать, какой из двух случаев имеет место; например, это не трудно производить TMs, которые останавливают или не могут останавливаться на любом или всех входах. Эти случаи проблемы не только разрешимы и регулярны, но мы знаем, какие они разрешимые / регулярные языки.