Можно ли решить, достигнет ли ТМ какой-либо позиции на ленте?

У меня есть эти вопросы из старого экзамена, который я пытаюсь решить. Для каждой задачи, вход является кодирование некоторой машины Тьюринга $M$ .

Для целого числа $c>1$ и следующих трех задач:

1. Правда ли, что для каждого входа $x$ M не передает $|x|+c$ позиции при работе на $x$ ?

2. Верно ли, что для каждого входа M не передает max { | х | - c , 1 } положение при работе на х ?$x$$\max \{|x|-c,1 \}$$x$

3. Правда ли, что для каждого входа M не проходит позицию ( | x | + 1 ) / c при работе на x ?$x$$(|x|+1)/c$$x$

Сколько проблем разрешимо?

Номер задачи (1), на мой взгляд, в , если я понимаю правильно , так как я могу запустить все входы параллельно, и остановки , если входные данные достигли этой позиции и показать , что это не в R I может уменьшить дополнение от Атм к нему. Я строю машину Тьюринга M ′ следующим образом: для ввода$\text {coRE} \smallsetminus \text R$$\text R$$M'$ я проверяю, является ли y историей вычислений, если это так, то M ′ работает правильно и не останавливается, если нет, то останавливается.$y$$y$$M'$

Для (3) я считаю, что это разрешимо, так как для $c \geqslant 2$ все машины Тьюринга всегда остаются в первой ячейке полосы, поскольку для строки из одного символа он может пройти первую ячейку, поэтому мне нужно смоделировать все строки длины 1 для шагов (правильно ли это?), И посмотреть , если я использую только первую ячейку во всех из них.$|Q|+1$

Я действительно не знаю, что делать с (2).

Любая ситуация, которая спрашивает, ограничена ли машина Тьюринга конечной частью ленты (скажем, длины ) на данном входе, разрешима.$n$

Аргумент работает следующим образом. Рассмотрим машину Тьюринга, ленту и положение машины Тьюринга на ленте. Все вместе они имеют конечное число конфигураций. Чтобы быть конкретным, есть только возможные конфигурации. $t = n|\Gamma|^n|Q|$ - набор символов ленты и$\Gamma$ - набор состояний. Я буду продолжать использовать слово «конфигурация» для описания состояния машины Тьюринга в сочетании с состоянием ленты и ее положением на ленте до конца этого ответа, но это не стандартный словарь.$Q$

Запустите машину, отслеживая все ее прошлые конфигурации. Если он когда-либо выходит за пределы точки , верните «да, M проходит позицию n ». В противном случае машина находится где-то между 0 и n . Если машина когда-либо повторяет конфигурацию - ее состояние, символы на ленте и ее положение на ленте совпадают с тем, что было раньше - верните «нет, $n$$M$$n$$n$$M$ никогда не проходит позицию ».$n$

По принципу pidgeonhole это должно происходить не более чем за шагов. Так что все вышеперечисленное разрешимо; после максимум$t+1$ смоделированных шагов вы получите ответ.$t+1$

Краткое замечание о том, почему это работает: когда аппарат, лента и ее положение на ленте повторяются, между этими повторениями должна быть последовательность конфигураций. Эта последовательность будет повторяться снова, приводя к той же конфигурации еще раз - машина находится в бесконечном цикле. Это потому, что мы отслеживаем каждый аспект машины Тьюринга; ничто за пределами конфигурации не может повлиять на то, что произошло. Поэтому, когда конфигурация повторяется, она повторяется снова, с идентичной серией конфигураций между ними.

Таким образом, ограничение ленты конечной частью строки является разрешимым. Поэтому, перебирая все возможные входные строки, проблема в $\text{coRE}$ для всех трех вопросов. Возможно, вы уже поняли это (между вашими идеями для 1 и 3 и ответом Ранга G для 2 это все равно кажется полностью решенным), но я решил, что, тем не менее, стоит опубликовать.

(2) очень похож на (3), и то же рассуждение, которое вы использовали для (3), применимо и здесь: обратите внимание, что машины, которые в имеют странное свойство - они не читают весь ввод (они никогда не достигают его последние c бит.) И это верно для каждого входа.$L_2$$c$

Хорошо, теперь давайте рассмотрим только входные данные до длины . Для каждого из них есть только два варианта: машина зацикливается / останавливается без перемещения головки или перемещает головку. Если он перемещает голову на некоторый x (с | x | ≤ c ), эта машина не находится в$c$$x$$|x|\le c$ из-за этого входа x . В противном случае я утверждаю, что машина находится в L 2 . Так как он никогда не двигает головой - он понятия не имеет, каков размер ввода! это означает, что он ведет себя одинаково для всех входов длины | х | > в . Следовательно, L 2 разрешима.$L_2$$x$$L_2$$|x|>c$$L_2$