Класс языков, распознаваемых одноленточными ТМ с тремя состояниями

9

Какое-то время мне было любопытно, что машины Тьюринга имеют ровно одну ленту и ровно 3 состояния (а именно, начальное состояние , состояние принятия и состояние отказа ). Обратите внимание, что я допускаю произвольные (конечные) алфавиты ленты (т. Е. Алфавит ленты не ограничен равным входному алфавиту).q0qacceptqreject

Для удобства назовите класс языков, распознаваемых такими ТМ, . У меня есть несколько вопросов об этом классе:C3

  1. Имеет ранее были изучены?C3
  2. Известно ли, что равен другим интересующим классам сложности / вычислимости?C3
  3. Является ли класс устойчивым к изменениям в модели. Например, если используемым TM разрешено оставаться на месте в течение одного перехода (в отличие от постоянного перемещения влево или вправо) или если лента сделана бесконечной в обоих направлениях, а не только вправо, класс делает смены языков, распознаваемых 3-штативными ТМ с 1 лентой?C3
  4. Как относится к классу регулярных языков, ? (В частности, каждый регулярный язык вC3RegularC3?)

(Довольно поверхностный) поиск вызвал только этот пост cs.stackexchange, который уместен, но не отвечает на мои вопросы и этот документ , который я не прочитал достаточно подробно, чтобы быть уверенным, что он относится именно к классу.C3 а не похожий, но другой класс (в статье утверждается, что (1) каждый язык в C3 разрешима и (2) что C3 а также Regularразличные классы с непустым пересечением). Как отмечено в комментариях к посту cs.stackexchange, такие виды ТМ можно рассматривать как очень специфические клеточные автоматы, так что, возможно, кто-то, кто знает литературу по теории клеточных автоматов, мог бы помочь.

Михаил Рудой
источник
1
Если у вас есть только одно состояние без завершения и одна лента (входная лента), то ваш компьютер не может запомнить ничего, что он прочитал. Таким образом, он может принимать или отклонять именно те входные данные, которые содержат определенные символы из входного алфавита.
Дэвид Г
4
Машина не может вспомнить, что она прочитала, но она может переписать то, что прочитала, чем-то другим. Так что я не понимаю, почему указанная вами характеристика была бы правильной. (т.е. я могу думать о простой машине, которая принимает01 и отвергает 011; здесь поведение не полностью определяется тем, какие символы находятся на входе).
Михаил Рудой
1
Вы правы, моя интуиция была не права.
Дэвид Г

Ответы:

7

Зверь очень мощный , например, мы можем построить ТМM который принимает каждую строку формы

LY={r0n1mAmn}

и отклоняет каждую строку в форме

LN={r0n1mAm>n}

Идея состоит в том, чтобы преобразовать первый r в Rи затем позвольте голове достичь середины струны, затем сделайте зигзаг без состояния; если оно достигнетA перед R тогда он принимает.

Неформальное описание:

  • на r записывать R и двигайтесь направо (приготовьтесь к отказу)
  • на 0 записывать c и двигайтесь вправо (двигаясь к центру)
  • на 1 записывать > и двигаться влево (отметить 1, подготовьтесь к следующему перекрестку слева направо и идите налево)
  • на c записывать < и двигаться вправо (отметьте 0, подготовьтесь к следующему перекрестку справа налево и идите направо)
  • на < записывать > и идите налево (пересечение слева направо, подготовьтесь к следующему справа налево)
  • на > записывать < и идите направо (перекресток справа налево, подготовьтесь к следующему слева направо)
  • на A принять, на R отклонять
  • на бланке b отклонять

Пример:

  :r 0 0 0 1 1 A
   R:0 0 0 1 1 A
   R c:0 0 1 1 A
   R c c:0 1 1 A
   R c c c:1 1 A
   R c c:c > 1 A
   R c c <:> 1 A
   R c c < <:1 A
   R c c <:< > A
   R c c:< > > A
   R c:c > > > A
   R c <:> > > A
   ...
   R c < < < <:A ACCEPT

Эта техника зигзага используется в самой маленькой универсальной машине Тьюринга с двумя состояниями (она имеет 18 символов), созданной Рогожиным (Рогожин, 1996. TCS, 168 (2): 215–240)).

Некоторое внимание следует уделить, чтобы доказать, что M остановка на всех входах (просто обратите внимание, что она отклоняется на пустом вводе, и все не останавливающие символы "сходятся" к < или > что не может привести к бесконечному циклу).

Как прокомментировал DavidG, язык L(M) признан M это надмножество LY (т.е. LYL(M)) но он не содержит строки из LN (т.е. L(M)LN=) и - как прокомментировал МихаилРудой - этого достаточно, чтобы доказать, что L(M) не регулярно.

Действительно, если L(M) регулярно, то также L(M){r01A}=LY={r0n1mAmn}будет регулярным (что не является простым применением леммы прокачки); приводя к противоречию.

Так L(M) не регулярно .

... но как и все супергерои C3 имеет пятку Ахилла: он даже не может распознать

L={12n}

Неофициально он может использовать только самый левый b1... (b это пустой символ) или правый туман 1b...как крюк и «расширяться» в другом направлении; но окончательное принятие или отклонение не может быть на пустом символе противоположной стороны, поэтому это может быть сделано только на внутренней части1s и, начиная с достаточно длинного ввода, его можно «подделать», растягивая на единицу.

Наконец, прочитав статью, я могу подтвердить, что описанная в ней ТМ с одним состоянием соответствует вашему C3 класс ... (так что ничего нового здесь :-) ... и язык, использованный автором для доказательства того, что он содержит нерегулярные языки, очень похож на мой.

Марцио де Биаси
источник
1
Мне очень нравится ответ (+1). Однако описанный TM принимает другой язык. Например, он принимает также строки rrrrr00011AAAA, r000000r0000r0000r00011A, r00011A11111111 (после A это может быть что угодно, а не единицы) ...
David G
@DavidG: Ты прав! Я не думал об этом слишком много ... Я пытаюсь это исправить.
Марцио Де
4
На самом деле, даже через L не является языком, распознаваемым описанной ТМ, этот язык определенно не является регулярным: если эта ТМ M, тогда L(M)r01A=L поэтому краткое доказательство от противного (если L(M) тогда регулярно L(M)r01A=Lтакже будет регулярным; противоречие) может показать, чтоL(M)не регулярно.
Михаил Рудой
3
@MikhailRudoy: да! У меня была такая же идея. Я открыл cstheory, чтобы отредактировать ответ, и увидел твой комментарий. Посмотрим, смогу ли я переписать ответ с учетом вашего комментария ...
Марцио Де
5

Я недооценил силу C3... на самом деле это не так уж далеко от гиперкомпьютера !

(Я публикую это как отдельный ответ для большей ясности)

Мы можем построить единую государственную машину Тьюринга M который принимает строки в форме:

LY={a0n1mRm2n}

и отклоняет строки в форме:

LN={a0n1mRm<2n}

Идея и конструкция аналогичны предыдущему ответу: трансформируйте первый a в Aпозвольте голове достичь середины строки, затем сделайте зигзаг без состояния, но переходы «реализуют» двоичный счетчик в первой половине следующим образом: Z(Ноль) отскакивает голову вправо , и преобразоватьZ в S (Один) в следующий раз, когда голова достигает S, преобразовать его в )и пусть голова двигается влево; когда голова достигает) превратить его в Z, Вторая половина строки ведет себя как одинарный счетчик.

Переходы:

  • на r записывать R и двигайтесь направо (приготовьтесь к отказу)
  • на 0 записывать Z и двигайтесь вправо (двигаясь к центру, установите двоичный счетчик на 0 ..)
  • на 1 записывать > и двигаться влево (отметить 1 и уменьшаем унарный счетчик, готовимся к следующему пересечению слева направо и возвращаемся к двоичному счетчику)
  • на > записывать < и идите направо (пересечение второй половины строки справа налево, подготовка к следующему слева направо)
  • на < записывать > и идите налево (пересечение второй половины строки слева направо, подготовка к следующему справа налево)
  • на Z записывать S и двигаться вправо (преобразовать цифру в единицу и отскочить назад вправо в направлении унарного счетчика)
  • на S записывать ) и двигаться влево (очистить цифру, и пусть голова сместится влево, как «перенос», подготовиться к следующему слева направо первой части)
  • на ) записывать Z и двигайтесь вправо (установите ноль, который вызовет отскок, и пусть голова сместится вправо)
  • на A принять, на R отклонять
  • на бланке b отклонять

Пример:

 :a 0 0 0 1 1 1 1 1 1 1 1 R
  A:0 0 0 1 1 1 1 1 1 1 1 R
  A Z:0 0 1 1 1 1 1 1 1 1 R
  ...
  A Z Z Z:1 1 1 1 1 1 1 1 R
  A Z Z:Z > 1 1 1 1 1 1 1 R
  A Z Z S:> 1 1 1 1 1 1 1 R
  A Z Z S <:1 1 1 1 1 1 1 R
  A Z Z S:< > 1 1 1 1 1 1 R
  A Z Z:S > > 1 1 1 1 1 1 R
  A Z:Z ) > > 1 1 1 1 1 1 R
  A Z S:) > > 1 1 1 1 1 1 R
  A Z S Z:> > 1 1 1 1 1 1 R
  ...
  A Z S:Z > > > 1 1 1 1 1 R
  ...
  A Z S S < < <:1 1 1 1 1 R
  ...
  A S:) ) > > > > 1 1 1 1 R
  ...
 :A ) ) ) > > > > > > > > R ---> ACCEPT

Некоторое внимание следует уделить, чтобы доказать, что M остановка на всех входах (только обратите внимание, что она отклоняется на пустом вводе, и все не прерывающиеся символы "циклически" (,S,Z или <,> что не может привести к бесконечному циклу).

Язык L(M) это надмножество LY (LYL(M)) и не содержит строк из LN (L(M)LN=).

Предположим, что L(M)является контекстно-свободным , а затем - закрывающим свойством КЛЛ, пересекающим его с обычным языком{r01A} создать язык CF:

L(M){r01A}={a0n1mRm2n}=LY

Но простым применением леммы Огдена для КЛЛ мы можем доказать, чтоLYCFL: просто выбери достаточно долго sLY и отметьте все 0S; по крайней мере, один ноль может быть накачан и что бы ни было число1s в насосной колонне экспоненциальный рост 2n приводит к строке LY).

Так L(M) не Context Free .

... теперь мне интересно, если это еще один ответ "изобретать велосипед", или это новый (маленький) результат.

Марцио де Биаси
источник
Ну, язык здесь вычислим в таком низком классе, как coNLOGTIME, поэтому он не требует гиперкомпьютеров. (По факту,LY а также LNможно разделить даже в DLOGTIME.)
Эмиль Йержабек
@ EmilJeřábek: Я сказал "не слишком далеко" ... не подавляйте амбиции этого крошечного класса ... :-)
Марцио Де
2

В этом ответе предполагается, что машины Тьюринга имеют двусторонние бесконечные ленты. Претензии не распространяются на односторонние бесконечные ленты.

Позвольте мне сначала определить класс языков C3как класс всех языков, разрешимых на одноленточных машинах Тьюринга с 3 состояниями (C3был определен как класс языков, распознаваемых одноленточными машинами Тьюринга с 3 состояниями). Я ввел классC3 потому что в моем первоначальном ответе я неосознанно поменял классы C3 а также C3 (Я только учел класс C3).

Этот ответ является скорее дополнением к ответам @MarzioDeBiasi. Он показал, что классыC3 а также C3не содержатся в КЛЛ и, следовательно, содержат довольно интересные языки. Однако, как я покажу в этом посте, каждый языкL в C3 обладает тем свойством, что множество {1n;nN{0}} либо в L или в его дополнении LC, таким образомC3также очень ограничительный, например. он содержит только тривиальные унарные языки{}, {ε}, {1n;nN} а также {1n;nN{0}}, КлассC3содержит немного больше унарных языков. Тем не менее, он считает, что еслиLC3 а также 1nL за n1, тогда 1mL для всех mn, Простым следствием является то, что не все обычные языкиC3 ни в C3, Также язык{1} не в C3 ни в C3,


Для претензии (выделено жирным шрифтом) о C3, достаточно доказать, что одноленточная машина Тьюринга M с 3 состояниями, которые всегда останавливаются, принимает или отклоняет все строки из {1n;nN{0}}, Предположим, что строка вида1n, nN{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;nN{0}} или это отвергает их всех.


Доказательство иска (выделено жирным шрифтом) о C3следует той же линии, что и выше. Мы берем одноленточную машину Тьюринга с тремя состояниямиM который принимает строку 1n для некоторых n1, предполагатьM дан вход 1m за mn, Мы должны доказать это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;mn},

Дэвид Г
источник
Во-первых, нигде в вопросе не говорится, что M должен останавливаться на всех входах, так что в этом ответе есть какая-то логика. Кроме того, логика в некоторых случаях не имеет смысла для меня. Например, в случае 3, если M перемещается влево и на пустое, и на A, то M посетит ячейку непосредственно слева от крайней правой A (в противоположность утверждению из ответа.)
Михаил Рудой
Ницца; другой способ заявить это: еслиΣ={1} (унарные языки) тогда k s.t. 1kL(M)L(M)={1nn>0}...
Марцио Де
@MikhailRudoy, ​​чтобы сначала прояснить случай 3: если голова перемещается влево и на символе А, и на пустом символе, то она будет двигаться влево навсегда и не остановится. Если он когда-либо (скажем, после 100 шагов) посещает ячейку, расположенную непосредственно слева от крайней правой буквы A, то в случае ввода 1 он никогда не останавливается (в этом случае ячейка, расположенная непосредственно слева от крайней правой буквы A, будет содержать пустой символ).
Дэвид Г
@MikhailRudoy, ​​это правда, что я предположил, что машина Тьюринга должна остановиться. Я отредактирую ответ, чтобы включить также возможность того, что он будет работать вечно. Результат аналогичный.
Дэвид Г
3
@MikhailRudoy: Кстати, проблема хетлинга разрешима для машин Тьюринга с 1 состоянием; см. Габор Т. Герман. Равномерная проблема остановки для обобщенных машин Тьюринга с одним состоянием . Описанная модель немного отличается от вашей: TM принимает, если она заканчивается в смертельной конфигурации (нет принятия / отклонения); но результат также относится к вашей модели (просто остановите TM на символах, которые приводят к вашим дополнительным состояниям Accept / Reject).
Марцио Де