Вопрос, касающийся машины Тьюринга с бесполезным состоянием

10

Итак, вот вопрос из прошлого теста в моем классе теории вычислений:

Бесполезное состояние в ТМ - это состояние, которое никогда не вводится ни в какую строку ввода. Пусть Докажите, что неразрешима.

USЕLЕSSTMзнак равно{M,Q|Q бесполезное состояние в M},
USELESSTM

Я думаю, что у меня есть ответ, но я не уверен, что он правильный. Включит это в раздел ответов.

BrotherJack
источник
В будущем, пожалуйста, включите ваши попытки в вопрос!
Рафаэль
1
@ Рапаэль Только что сделал. Я написал это, когда задал вопрос, но из-за отсутствия репутации я не смог опубликовать его как минимум 8 часов. Мне было бы интересно узнать, если это правильный ответ.
BrotherJack,
Нет, я имел в виду просто включить его в вопрос, есть ли конкретные моменты, в которых вы не уверены.
Рафаэль

Ответы:

12

Это явно сводится к проблеме остановки. Если машина не останавливается на входе x, то любое конечное состояние «бесполезно». Учитывая вход M , x для задачи Остановки, легко построить M x, который останавливается на каждом входе (таким образом, его конечное состояние не бесполезно) тогда и только тогда, когда M останавливается на x . Таким образом, вы можете решить проблему остановки, если вы можете решить U S E L E S S T M , что приводит к противоречию.MxM,xMxMxUSELESSTM

Ран Г.
источник
... и поскольку проблема Остановки неразрешима, эта проблема также неразрешима, верно?
BrotherJack,
Действительно, это правильно.
Ран Г.
2

Для целей этого доказательства мы будем предполагать, что разрешимо, чтобы показать противоречие.USЕLЕSSTM

Создайте TM который выполняет следующее:р

  • Конвертирует TM в автомат P с уменьшенным стеком (т. Е. Без требований LIFO). Это эквивалентно тому , ориентированный граф подробно переход между M состояниями «S.MпM
  • Отметить начальное состояние .P
  • Из начального состояния начните поиск в ширину по каждому исходящему ребру, отмечая каждый немаркированный узел.
  • Когда поиск заканчивается, если есть какие-либо немаркированные узлы, которые соответствуют , принять ; в противном случае отклонить .q

Затем создайте TM = "На входе $$S

  1. Создайте TM как показано выше.R
  2. Запуск на R .qR
  3. Если возвращает принять, принять ; если R бракованных, отвергают " RR

Таким образом, если является решающим фактором для U S E L E S S T M, то S является решающим фактором для A T M (проблема принятия). Поскольку доказано, что A T M неразрешима (см. Теорию вычисления Майкла Сипсера 4.11 на стр. 174), мы пришли к противоречию. Следовательно, исходная гипотеза неверна и U S E L E S S T M неразрешима.RUSELESSTMSATMATMUSELESSTM

BrotherJack
источник
В чем смысл превращать ТМ в КПК с расслабленным стеком?
Ран Г.
1
Является ли решающим фактором? если так - вам не нужно описывать его действие. На самом деле вы не можете описать его действие, так как оно на самом деле не существует. Все вы знаете , что он не отвечает да / нет в зависимости от того или нет , вход в L . RL
Ран Г.