Докажите, является ли этот язык разрешимым или неразрешимым

Question

Поэтому я просматриваю свои заметки по этой проблеме, и я не могу понять, как эта проблема работает. Скажем, у нас есть M, и M принимает входные данные, которые заставляют его посещать каждое состояние без остановки.

Я убедил себя, что эта проблема разрешима, но мне трудно доказать это. Примерный план моего ответа: предположим, что у нас есть TM T, у которого есть только одно состояние остановки, и если он хочет пройти через все состояния, он должен пройти через это состояние остановки, и нам как-то нужно показать, как они циклически проходят через все штаты как таковые.

Любая помощь будет полезна, спасибо!

Answer 1

Я думаю, вы найдете ответ на самом деле, что это неразрешимый. Зачем? Ну, это позволит вам решить проблему остановки.

Вам дается ТМ М и ввод x и оракул Q для проблемы, которую вы описываете. Можем ли мы решить проблему остановки M с помощью ввода x с помощью оракула Q?

Сначала мы подключаем новый TM N к передней части M. Вот что делает N: - удаляет содержимое ленты - записывает x на ленту

M останавливается на x тогда и только тогда, когда NM останавливается на всех входах. Это должно быть легко увидеть, так как N покидает ленту точно так же, как M видел бы, если бы ввод был x. Мы можем спроектировать N таким образом, чтобы все состояния N были посещены.

Теперь измените M в M ', добавив вторую ленту. Вторая лента будет использоваться для отслеживания состояния наибольшего числа M, которое мы посетили. Добавьте переходы к M ', которые читают n-е состояние со вторичной ленты и приводят к переходу M' в (n+1) -ное состояние. Переход из состояния с наибольшим номером M 'должен вернуться в исходное состояние M' и записать что-то вроде "закончено" на вторичной ленте. Когда M 'видит "законченный" на вторичной ленте, он ведет себя так же, как M и рассматривает только основную ленту.

Таким образом, M 'делает именно то, что делает M', за исключением того, что он сначала посещает все состояния M, а затем сбрасывает, после чего он ведет себя так же, как M.

M 'останавливается на x, если M останавливается на x. Также NM 'останавливается, если M останавливается на x.

Наконец мы готовы к доказательству. Оракул Q принимает NM, если M останавливается на x. Q принимает NM, если NM принимает вход y, который заставляет NM посещать все состояния. Но: - все входы y заставляют NM 'посещать все состояния (поскольку все состояния N посещаются конструкцией, а все состояния M' посещаются модификацией M); так что Q на самом деле просто отвечает на вопрос "принимает ли NM какие-либо строки?" - NM'стирает y с ленты ввода, записывает x и передает его M'. Таким образом, ввод y не имеет значения; если NM 'принимает любой ввод, он принимает все из них. И он принимает их все, если M 'принимает x. - М 'принимает тот же язык, что и М.

Таким образом, Q применительно к NM 'действительно говорит нам, останавливается ли M на x. Тогда Q решает проблему остановки.