Является ли разрешимым набор машин Тьюринга, который останавливается не более чем на 50 шагов на всех входах?

19

Пусть . Мне нужно решить, является ли F разрешимым или рекурсивно перечислимым. Я думаю, что это можно решить, но я не знаю, как это доказать.F={M:M is a TM which stops for every input in at most 50 steps}

Мои мысли

Эта часть "50 шагов" немедленно поворачивает знак R для меня. Если бы это было для конкретного ввода, это было бы разрешимо. Тем не менее, здесь это для каждого входа. Проверка его на бесконечные входные данные заставляет меня думать, что проблема в ко-RE , то есть его дополнение приемлемо.

Возможно, я могу проверить конфигурации и увидеть, что все конфигурации после 50 шагов не приводят к принятию состояния - как мне это сделать?

Юзеф
источник

Ответы:

21

NN1

Как отмечает Свиг в более раннем ответе, если машина останавливается после не более чем шагов, значительными будут только ячейки на ленте. Тогда достаточно смоделировать машину на всех входных строках вида , из которых существует конечное число.0 , 1 , , N - 1 МN0,1,,N1MxΣN

  • Если какой-либо из этих симуляций не удается войти в состояние остановки с помощьюпереход, это указывает, что любая входная строка, начинающаяся с является той, для которой машина не останавливается в течение первых шагов.NthNxN
  • Если все эти симуляции останавливаются с помощьюпереходного периода, то останавливается за шагов на всех входах любой длины (из которых подстрока длины - это все, на что она когда-либо действует).NthN NMNN
Ниль де Бодрап
источник
И - Предполагаю ли я, что , длина которого больше , автоматически отклоняется? NxN
Юзеф
Почему он не может перейти дальше, чем N ячейка в N этапов вычислений?
Юзеф
@Jozef: Моделирование просто перебрать все возможные входные строки длиной N . Вы можете перебирать больше строк, но больше ничего не узнаете, потому что в любом случае важны только первые N символов. Причина, по которой он не может идти дальше, чем N ячеек, заключается в том, что машины Тьюринга (или их стандартное определение в любом случае) перемещают только одну ячейку за шаг.
Ниль де Бодрап,
Хорошо, я понял. поэтому вы обращаете внимание только на первые N символов каждого слова, поэтому вы проверяете все их комбинации. почему вы удалили описание конфигурации?
Юзеф
Это все еще видно, если вы посмотрите на предыдущие изменения. Я пересмотрел его к этому , потому что в то время как другой ответ , может быть , интересно, много того , что сделал это «интересно» только служил , чтобы скрыть тот факт , что процедура принятия решения ничего более или менее имитируя на всех возможных входах длины . Я подумал, что лучше пересмотреть ответ на что-то гораздо более простое, и которое в основном дало понять, что делает проблему решаемой. НMN
Ниль де Бодрап,
4

Если останавливается не более чем за 50 шагов, то позиции могут быть достигнуты на обычно бесконечной ленте, ограничены. Таким образом, бесконечная лента может моделироваться конечной. Это означает, что лента может моделироваться конечным автоматом. Отсюда следует, что машина Тьюринга которая останавливается не более чем за 50 шагов, похожа на некоторый конечный автомат .М М М MMMM

Пусть - множество состояний , - множество принимающих состояний, а - алфавит. Затем мы строим множество состояний из следующим образом: где - позиция головки чтения / записи над лентой. Мы можем ограничить позицию потому что количество разрешенных вычислительных шагов ограничивает количество достижимых позиций.М Ж Q Γ Q ' М ' Q ' = { п , д , ев , р , QMFQΓQMр { - 50 , . , , , 50 }Q={n,q,s,p,a|n{0,...,50}qQ,sΓ,p{50,...,50},aqF}p{50,...,50}

Наличие состояния конечного автомата означает, что мы находимся в состоянии исходного автомата с на ленте в положении где также находится головка чтения / записи позиционируется после шага вычисления. Состояние является принимающим, если .M ' Q сек р п т т у йn,q,s,p,aMqspnatrue

Преобразование отношения перехода конкретной машины Тьюринга - немного больше работы, но не обязательно для исходного вопроса, потому что этого достаточно, чтобы показать, что пространство состояний конечно (и, таким образом, мы можем просто проверить каждый вход с длиной не более 50). символы на каждом таком автомате). Идея состоит в том, чтобы построить новое отношение перехода, которое переходит из состояния в состояние в -го вычисления шага тогда и только тогда переход был в первоначальном отношении перехода.п + 1 , д ' , ев ' , р ' , 'п д , ев , р д ' , ев ' , р 'n,q,s,p,an+1,q,s,p,anq,s,pq,s,p

swegi
источник
Как вы имитируете хранилище на ленте, то есть способность пересматривать символы, которые вы уже прочитали, на конечном автомате?
Ниль де Бодрап,
@NieldeBeaudrap: вы перечисляете все пространство состояний, т.е. вы проверяете модель конечной ленты и управляющего автомата машины Тьюринга.
Swegi
1
Учитывая, что ОП задает основные вопросы вычислимости для машин Тьюринга, вы можете распаковать этот эскиз во что-то более полное. (Сам я никогда раньше не слышал фразу «проверка модели» в вычислительном контексте.) В контексте я бы обычно предполагал, что под «конечным автоматом» вы подразумевали бы DFA или подобное, если не указали иное, и мне не ясно, что будет соответствовать вкладу DFA в такой конструкции. Если вы просто имеете в виду график, представляющий возможные траектории ТМ, то я согласен.
Ниль де Бодрап,
Под проверкой модели конечной части ленты я в основном имею в виду то, что вы написали в своем ответе: просто протестируйте каждый вход размером не более 50 и проверьте, достигнуто ли состояние приема.
Swegi
1
Я бы хотел, чтобы люди перестали распространять миф о том, что лента машины Тьюринга должна быть бесконечной. Это не так - оно может быть конечным, пока оно расширяется по мере необходимости.
reinierpost