Итак, вот вопрос из прошлого теста в моем классе теории вычислений:
Бесполезное состояние в ТМ - это состояние, которое никогда не вводится ни в какую строку ввода. Пусть Докажите, что неразрешима.
Я думаю, что у меня есть ответ, но я не уверен, что он правильный. Включит это в раздел ответов.
computability
undecidability
formal-methods
turing-machines
BrotherJack
источник
источник
Ответы:
Это явно сводится к проблеме остановки. Если машина не останавливается на входе x, то любое конечное состояние «бесполезно». Учитывая вход M , x для задачи Остановки, легко построить M x, который останавливается на каждом входе (таким образом, его конечное состояние не бесполезно) тогда и только тогда, когда M останавливается на x . Таким образом, вы можете решить проблему остановки, если вы можете решить U S E L E S S T M , что приводит к противоречию.M x M,x Mx M x USELESSTM
источник
Для целей этого доказательства мы будем предполагать, что разрешимо, чтобы показать противоречие.U S E L E S SТ М
Создайте TM который выполняет следующее:р
Затем создайте TM = "На входе $$S
Таким образом, если является решающим фактором для 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 неразрешима.R USELESSTM S ATM ATM USELESSTM
источник