Какое-то время мне было любопытно, что машины Тьюринга имеют ровно одну ленту и ровно 3 состояния (а именно, начальное состояние , состояние принятия и состояние отказа ). Обратите внимание, что я допускаю произвольные (конечные) алфавиты ленты (т. Е. Алфавит ленты не ограничен равным входному алфавиту).
Для удобства назовите класс языков, распознаваемых такими ТМ, . У меня есть несколько вопросов об этом классе:
- Имеет ранее были изучены?
- Известно ли, что равен другим интересующим классам сложности / вычислимости?
- Является ли класс устойчивым к изменениям в модели. Например, если используемым TM разрешено оставаться на месте в течение одного перехода (в отличие от постоянного перемещения влево или вправо) или если лента сделана бесконечной в обоих направлениях, а не только вправо, класс делает смены языков, распознаваемых 3-штативными ТМ с 1 лентой?
- Как относится к классу регулярных языков, ? (В частности, каждый регулярный язык в?)
(Довольно поверхностный) поиск вызвал только этот пост cs.stackexchange, который уместен, но не отвечает на мои вопросы и этот документ , который я не прочитал достаточно подробно, чтобы быть уверенным, что он относится именно к классу. а не похожий, но другой класс (в статье утверждается, что (1) каждый язык в разрешима и (2) что а также различные классы с непустым пересечением). Как отмечено в комментариях к посту cs.stackexchange, такие виды ТМ можно рассматривать как очень специфические клеточные автоматы, так что, возможно, кто-то, кто знает литературу по теории клеточных автоматов, мог бы помочь.
источник
Ответы:
Зверь очень мощный , например, мы можем построить ТМM который принимает каждую строку формы
и отклоняет каждую строку в форме
Идея состоит в том, чтобы преобразовать первыйr в R и затем позвольте голове достичь середины струны, затем сделайте зигзаг без состояния; если оно достигнетA перед R тогда он принимает.
Неформальное описание:
Пример:
Эта техника зигзага используется в самой маленькой универсальной машине Тьюринга с двумя состояниями (она имеет 18 символов), созданной Рогожиным (Рогожин, 1996. TCS, 168 (2): 215–240)).
Некоторое внимание следует уделить, чтобы доказать, чтоM остановка на всех входах (просто обратите внимание, что она отклоняется на пустом вводе, и все не останавливающие символы "сходятся" к < или > что не может привести к бесконечному циклу).
Как прокомментировал DavidG, языкL(M) признан M это надмножество LY (т.е. LY⊂L(M) ) но он не содержит строки из LN (т.е. L(M)∩LN=∅ ) и - как прокомментировал МихаилРудой - этого достаточно, чтобы доказать, что L(M) не регулярно.
Действительно, еслиL(M) регулярно, то также L(M)∩{r0∗1∗A}=LY={r0n1mA∣m≤n} будет регулярным (что не является простым применением леммы прокачки); приводя к противоречию.
ТакL(M) не регулярно .
... но как и все супергероиC3 имеет пятку Ахилла: он даже не может распознать
Неофициально он может использовать только самый левыйb1... (b это пустой символ) или правый туман 1b... как крюк и «расширяться» в другом направлении; но окончательное принятие или отклонение не может быть на пустом символе противоположной стороны, поэтому это может быть сделано только на внутренней части1 s и, начиная с достаточно длинного ввода, его можно «подделать», растягивая на единицу.
Наконец, прочитав статью, я могу подтвердить, что описанная в ней ТМ с одним состоянием соответствует вашемуC3 класс ... (так что ничего нового здесь :-) ... и язык, использованный автором для доказательства того, что он содержит нерегулярные языки, очень похож на мой.
источник
Я недооценил силуC3 ... на самом деле это не так уж далеко от гиперкомпьютера !
(Я публикую это как отдельный ответ для большей ясности)
Мы можем построить единую государственную машину ТьюрингаM который принимает строки в форме:
и отклоняет строки в форме:
Идея и конструкция аналогичны предыдущему ответу: трансформируйте первыйa в A позвольте голове достичь середины строки, затем сделайте зигзаг без состояния, но переходы «реализуют» двоичный счетчик в первой половине следующим образом: Z (Ноль) отскакивает голову вправо , и преобразоватьZ в S (Один) в следующий раз, когда голова достигает S , преобразовать его в ) и пусть голова двигается влево; когда голова достигает) превратить его в Z , Вторая половина строки ведет себя как одинарный счетчик.
Переходы:
Пример:
Некоторое внимание следует уделить, чтобы доказать, чтоM остановка на всех входах (только обратите внимание, что она отклоняется на пустом вводе, и все не прерывающиеся символы "циклически" (,S,Z или <,> что не может привести к бесконечному циклу).
ЯзыкL(M) это надмножество LY (LY⊂L(M) ) и не содержит строк из LN (L(M)∩LN=∅ ).
Предположим, чтоL(M) является контекстно-свободным , а затем - закрывающим свойством КЛЛ, пересекающим его с обычным языком{r0∗1∗A} создать язык CF:
Но простым применением леммы Огдена для КЛЛ мы можем доказать, чтоLY∉CFL : просто выбери достаточно долго s∈LY и отметьте все 0 S; по крайней мере, один ноль может быть накачан и что бы ни было число1s в насосной колонне экспоненциальный рост 2n приводит к строке ∉LY ).
ТакL(M) не Context Free .
... теперь мне интересно, если это еще один ответ "изобретать велосипед", или это новый (маленький) результат.
источник
В этом ответе предполагается, что машины Тьюринга имеют двусторонние бесконечные ленты. Претензии не распространяются на односторонние бесконечные ленты.
Позвольте мне сначала определить класс языковC′3 как класс всех языков, разрешимых на одноленточных машинах Тьюринга с 3 состояниями (C3 был определен как класс языков, распознаваемых одноленточными машинами Тьюринга с 3 состояниями). Я ввел классC′3 потому что в моем первоначальном ответе я неосознанно поменял классы C3 а также C′3 (Я только учел класс C′3 ).
Этот ответ является скорее дополнением к ответам @MarzioDeBiasi. Он показал, что классыC3 а также C′3 не содержатся в КЛЛ и, следовательно, содержат довольно интересные языки. Однако, как я покажу в этом посте, каждый языкL в C′3 обладает тем свойством, что множество {1n;n∈N∖{0}} либо в L или в его дополнении LC , таким образомC′3 также очень ограничительный, например. он содержит только тривиальные унарные языки{} , {ε} , {1n;n∈N} а также {1n;n∈N∖{0}} , КлассC3 содержит немного больше унарных языков. Тем не менее, он считает, что еслиL∈C3 а также 1n∈L за n≥1 , тогда 1m∈L для всех m≥n , Простым следствием является то, что не все обычные языкиC3 ни в C′3 , Также язык{1} не в C3 ни в C′3 ,
Для претензии (выделено жирным шрифтом) оC′3 , достаточно доказать, что одноленточная машина Тьюринга M с 3 состояниями, которые всегда останавливаются, принимает или отклоняет все строки из {1n;n∈N∖{0}} , Предположим, что строка вида1n , n∈N∖{0} , дается M , Есть три случая:
1) КогдаM читает 1, он принимает или отклоняет.
2) КогдаM читает 1, это перемещает голову налево. Если мы хотимM чтобы остановить этот ввод, он должен принять, отклонить или переместить вправо на пустой символ. Следовательно, он никогда не посещает ячейку справа от начальной ячейки ленты. Если это произойдет, он будет работать вечно на входе 1.
3) КогдаM читает 1, это перемещает голову вправо. Отсюда следует, что послеn шаги, содержание ленты An где A это какой-то символ из ленты алфавита и главы M находится на крайнем левом пустом символе справа от последнего A , Если мы хотимM чтобы остановить этот ввод, он должен принять, отклонить или переместить влево на пустой символ. Как и в случае 2), главаM теперь никогда не будет посещать камеру слева от самого правого A , Если бы это было, тоM будет работать вечно на входе 1.
Понятно, что во всех трех случаяхM принимает все строки из набора {1n;n∈N∖{0}} или это отвергает их всех.
Доказательство иска (выделено жирным шрифтом) оC3 следует той же линии, что и выше. Мы берем одноленточную машину Тьюринга с тремя состояниямиM который принимает строку 1n для некоторых n≥1 , предполагатьM дан вход 1m за m≥n , Мы должны доказать этоM принимает этот вход. У нас есть 3 случая:
1) КогдаM читает 1, он принимает.
2) КогдаM читает 1, это перемещает голову налево. Потому чтоM принимает ввод 1n , он должен принять или переместиться вправо на пустой символ. Следовательно, он никогда не посещаетn Ячейка справа от начальной ячейки. Если бы это было так, он бы работал вечно на входе1n ,
3) КогдаM читает 1, это перемещает голову вправо. Отсюда следует, что послеm шаги, содержание ленты Am где A это какой-то символ из ленты алфавита и главы M находится на крайнем левом пустом символе справа от последнего A , Потому чтоM принимает ввод 1n , он должен принять или переместиться влево на пустой символ. Как и в случае 2), главаM теперь никогда не будет посещать n Ячейка слева от самой правой A , Это потому что на входе1n , M не посещает ячейку, расположенную непосредственно слева от начальной ячейки, поскольку она содержит пустой символ, и если она прочитает его, она будет работать вечно.
Понятно, что во всех трех случаяхM принимает все строки из набора {1m;m≥n} ,
источник