Klasa języków rozpoznawalna przez 3-stanowe TM z pojedynczą taśmą

Przez pewien czas byłem ciekawy maszyn Turinga z dokładnie jedną taśmą i dokładnie 3 stanami (mianowicie stanem początkowym $q_0$, stan akceptacji i stan odrzucenia ). Zauważ, że zezwalam na dowolne (skończone) alfabety taśmowe (tzn. Alfabet na taśmie nie jest ograniczony do równego alfabetowi wejściowemu).$q_{accept}$$q_{reject}$

Dla wygody zadzwoń do klasy języków rozpoznawalnych przez takie TM . Mam kilka pytań na temat tej klasy:$C_3$

1. Czy był wcześniej badany?$C_3$
2. Czy wiadomo, że równa się innym interesującym klasom złożoności / obliczalności?$C_3$
3. Czy klasa odporna na zmiany w modelu. Na przykład, jeśli zastosowane bazy TM mogą pozostać na miejscu podczas jednego przejścia (w przeciwieństwie do zawsze poruszania się w lewo lub w prawo) lub jeśli taśma ma być nieskończona w obu kierunkach zamiast tylko w prawo, to klasa języków rozpoznawalnych przez 3-stanowe 1-taśmy TM zmieniają się?$C_3$
4. Jak odnosi się do klasy zwykłych języków, ? (W szczególności, czy każdy zwykły język w ?)$C_3$$Regular$$C_3$

(Raczej pobieżne) wyszukiwanie przyniosło tylko ten post cs.stackexchange, który jest istotny, ale nie odpowiada na moje pytania i ten artykuł , którego nie przeczytałem wystarczająco szczegółowo, aby mieć pewność, że dotyczy on dokładnie klasy a nie podobna, ale inna klasa (praca twierdzi, że (1) każdy język w jest rozstrzygalny oraz (2) że i są odrębnymi klasami z niepustym przecięciem). Jak wskazano w komentarzach postu cs.stackexchange, tego rodzaju TM można uznać za bardzo szczególne automaty komórkowe, więc może ktoś, kto zna literaturę na temat teorii automatów komórkowych, mógłby pomóc.$C_3$$C_3$$C_3$$Regular$

Bestia jest niezwykle potężna , na przykład możemy zbudować TM$M$ który akceptuje każdy ciąg formularza

$L_Y = \{ r\; 0^n \; 1^m\;A \mid m \leq n \}$

i odrzuca każdy ciąg formularza

$L_N = \{ r\; 0^n \; 1^m\;A \mid m > n \}$

Chodzi o przekształcenie pierwszego $r$ w $R$a następnie pozwólcie głowie sięgnąć do środka struny, a następnie wykonać „bezpaństwowy” zygzak; jeśli to osiągnie$A$ przed $R$ to akceptuje.

Nieformalny opis:

• na $r$ pisać $R$ i przejdź w prawo (przygotuj się na odrzucenie)
• na $0$ pisać $c$ i idź w prawo (w kierunku centrum)
• na $1$ pisać $>$ i idź w lewo (zaznacz a $1$, przygotuj się na następne przejście od lewej do prawej i idź w lewo)
• na $c$ pisać $<$ i idź w prawo (zaznacz a $0$, przygotuj się do następnego skrzyżowania od prawej do lewej i idź w prawo)
• na $<$ pisać $>$ i idź w lewo (przejście od lewej do prawej, przygotuj się na następny od prawej do lewej)
• na $>$ pisać $<$ i idź w prawo (przejście od prawej do lewej, przygotuj się na następne od lewej do prawej)
• na $A$ zaakceptować, w dniu $R$ odrzucać
• na pustym miejscu $b$ odrzucać

Przykład:

  :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

Ta technika zygzakowata jest stosowana w najmniejszej 2-stanowej uniwersalnej maszynie Turinga (ma 18 symboli) zbudowanej przez Rogozhina (Rogozhin 1996. TCS, 168 (2): 215–240)).

Należy na to zwrócić uwagę, aby to udowodnić $M$ zatrzymuje się na wszystkich wejściach (pamiętaj tylko, że odrzuca na pustych wejściach, a wszystkie symbole nie-zatrzymujące się „zbiegają”) $<$ lub $>$ które nie mogą prowadzić do nieskończonej pętli).

Jak skomentował DavidG, język $L(M)$ rozpoznawane przez $M$ jest nadzbiorem $L_Y$ (to znaczy $L_Y \subset L(M)$), ale nie zawiera żadnego ciągu z $L_N$ (to znaczy $L(M) \cap L_N = \emptyset$) i - jak skomentował MikhailRudoy - wystarczy, aby to udowodnić $L(M)$ nie jest regularny.

Rzeczywiście, jeśli $L(M)$ jest również regularny $L(M) \cap \{ r0^*1^*A \} = L_Y = \{ r0^n 1^mA \mid m \leq n \}$byłoby regularne (co nie polega na prostym zastosowaniu lematu pompującego); prowadząc do sprzeczności.

Więc $L(M)$ nie jest regularny .

... Ale jak wszyscy superbohaterowie $C_3$ ma piętę Achille'a: nawet nie rozpoznaje regularności:

$L = \{ 1^{2n} \}$

Nieformalnie może korzystać tylko z lewej strony $b 1 ...$ ($b$ jest pustym symbolem) lub prawą mgłą $1b...$jako haczyk i „rozszerzać się” w przeciwnym kierunku; ale ostateczna akceptacja lub odrzucenie nie może znajdować się na pustym symbolu po przeciwnej stronie, więc można to zrobić tylko na wewnętrznej stronie$1$i zaczynając od wystarczająco długiego wejścia, można go „sfałszować”, rozciągając go o jeden.

Wreszcie - po przeczytaniu artykułu - mogę potwierdzić, że opisana w nim jednostanowa TM pasuje do twojego $C_3$ klasa ... (więc nic nowego tutaj :-) ... a język użyty przez autora do udowodnienia, że ​​zawiera nieregularne języki, jest bardzo podobny do mojego.

Nie doceniłem mocy $C_3$... właściwie to nie jest zbyt daleko od Hyperkomputera !

(Publikuję to jako osobną odpowiedź dla większej przejrzystości)

Możemy zbudować maszynę Turinga w jednym stanie $M$ który akceptuje ciągi formularza:

$L_Y = \{ a \; 0^n \; 1^m \; R \mid m \geq 2^n\}$

i odrzuca ciągi formularza:

$L_N = \{ a \; 0^n \; 1^m \; R \mid m \lt 2^n\}$

Pomysł i konstrukcja jest podobna do tej z poprzedniej odpowiedzi: przekształć pierwszą $a$ w $A$, niech głowa dotrze do środka struny, a następnie wykona „bezstanowy” zygzak, ale przejścia „implementują” „licznik binarny” w pierwszej połowie w ten sposób: $Z$(Zero) odbij głowę z powrotem w prawo i przekonwertuj$Z$ w $S$ (Jeden) następnym razem, gdy głowa dotrze do $S$przekształć go w $)$i niech głowa przesunie się w lewo; kiedy głowa osiągnie$)$ przekształć to w $Z$. Druga połowa łańcucha zachowuje się jak jednoargumentowy licznik.

Przejścia są następujące:

• na $r$ pisać $R$ i przejdź w prawo (przygotuj się na odrzucenie)
• na $0$ pisać $Z$ i przesuń się w prawo (w kierunku środka, ustaw licznik binarny na 0 ..)
• na $1$ pisać $>$ i idź w lewo (zaznacz a $1$ i zmniejsz jednostronny licznik, przygotuj się do następnego przejścia od lewej do prawej i wróć do licznika binarnego)
• na $>$ pisać $<$ i idź w prawo (przejście od drugiej połowy sznurka od prawej do lewej, przygotuj się do następnej lewej do prawej)
• na $<$ pisać $>$ i idź w lewo (przejście od lewej do prawej drugiej połowy sznurka, przygotuj się do następnej prawej do lewej)
• na $Z$ pisać $S$ i przesuń w prawo (zamień cyfrę na jedną i odskocz z powrotem w prawo w kierunku licznika jednorzędowego)
• na $S$ pisać $)$ i przesuń się w lewo (usuń cyfrę i pozwól głowie przesunąć się w lewo jak „nieść”, przygotuj się do następnego od lewej do prawej pierwszej części)
• na $)$ pisać $Z$ i przesuń się w prawo (ustaw zero, które spowoduje odbicie) i pozwól głowie przesunąć się w prawo)
• na $A$ zaakceptować, w dniu $R$ odrzucać
• na pustym miejscu $b$ odrzucać

Przykład:

 :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

Należy na to zwrócić uwagę, aby to udowodnić $M$ zatrzymuje się na wszystkich wejściach (pamiętaj tylko, że odrzuca na pustych wejściach, a wszystkie nie zatrzymujące się symbole przechodzą cyklicznie) $( , S , Z$ lub $<, >$ które nie mogą prowadzić do nieskończonej pętli).

Język $L(M)$ jest nadzbiorem $L_Y$ ($L_Y \subset L(M)$) i nie zawiera ciągów z $L_N$ ($L(M) \cap L_N = \emptyset$).

Przypuszczam, że $L(M)$jest bezkontekstowy , a zatem - poprzez właściwości zamykania świetlówek kompaktowych, przecinając je ze zwykłym językiem$\{r 0^* 1^* A\}$ stworzyć język CF:

$L(M) \cap \{r 0^* 1^* A\} = \{ a \; 0^n \; 1^m \; R \mid m \geq 2^n\} = L_Y$

Ale poprzez proste zastosowanie Lemmy Ogdena dla CFL możemy to udowodnić$L_Y \notin CFL$: wybierz wystarczająco długo $s \in L_Y$ i zaznacz wszystkie $0$s; co najmniej jedno zero może być pompowane i niezależnie od liczby$1s$ w ciągu pompującym wykładniczy wzrost $2^n$ prowadzi do łańcucha $\notin L_Y$).

Więc $L(M)$ nie jest wolny od kontekstu .

... teraz zastanawiam się, czy jest to kolejna odpowiedź „odkrywania koła”, czy jest to nowy (mały) wynik.

W tej odpowiedzi zakłada się, że maszyny Turinga mają dwustronne nieskończone taśmy. Roszczenia nie dotyczą jednokierunkowych taśm nieskończonych.

Pozwól mi najpierw zdefiniować klasę języków $C_3'$jako klasa wszystkich języków rozstrzygalna przez maszyny Turinga z jedną taśmą z 3 stanami ($C_3$została zdefiniowana jako klasa języków rozpoznawalna przez maszyny Turinga z jedną taśmą z 3 stanami). Przedstawiłem klasę$C_3'$ ponieważ w mojej oryginalnej odpowiedzi nieświadomie zamieniłem klasy $C_3$ i $C_3'$ (Rozważyłem tylko klasę $C_3'$).

Ta odpowiedź jest bardziej uzupełnieniem odpowiedzi @MarzioDeBiasi. Pokazał, że zajęcia$C_3$ i $C_3'$nie są zawarte w CFL, a zatem zawierają dość interesujące języki. Jednak, jak pokażę w tym poście, każdy język$L$ w $C_3'$ ma właściwość ustawioną $\{1^n;n\in\mathbb{N}\backslash\{0\}\}$ jest albo w $L$ lub w jego uzupełnieniu $L^C$. A zatem$C_3'$jest również bardzo restrykcyjne, np. zawiera tylko trywialne, jednoargumentowe języki$\{\}$, $\{\varepsilon\}$, $\{1^n;n\in\mathbb{N}\}$ i $\{1^n;n\in\mathbb{N}\backslash\{0\}\}$. Klasa$C_3$zawiera nieco więcej jednojęzycznych języków. Utrzymuje jednak, że jeśli$L\in C_3$ i $1^n\in L$ dla $n\geq 1$, następnie $1^m\in L$ dla wszystkich $m\geq n$. Prostym następstwem jest to, że nie wszystkie zwykłe języki są w języku$C_3$ ani w $C_3'$. Również język$\{1\}$ nie jest w $C_3$ ani w $C_3'$.

Za roszczenie (pogrubione) około $C_3'$, wystarczy udowodnić, że maszyna Turinga z jedną taśmą $M$ z 3 stanami, które zawsze zatrzymują albo akceptują, albo odrzucają wszystkie ciągi $\{1^n;n\in\mathbb{N}\backslash\{0\}\}$. Załóżmy, że ciąg formularza$1^n$, $n\in\mathbb{N}\backslash\{0\}$, jest podane do $M$. Istnieją trzy przypadki:

1) Kiedy$M$ czyta 1, przyjmuje lub odrzuca.

2) Kiedy$M$czyta 1, przesuwa głowę w lewo. Jeśli chcemy$M$aby zatrzymać na tym wejściu, musi zaakceptować, odrzucić lub przejść w prawo na pusty symbol. Dlatego nigdy nie odwiedza komórki po prawej stronie początkowej komórki taśmy. Gdyby tak było, działałoby wiecznie na wejściu 1.

3) Kiedy$M$odczytuje 1, przesuwa głowę w prawo. Wynika z tego, że po$n$ kroki, zawartość taśmy jest $A^n$ gdzie $A$ to jakiś symbol z alfabetu taśmy i nagłówka $M$ jest na lewym pustym symbolu po prawej stronie ostatniego $A$. Jeśli chcemy$M$aby zatrzymać na tym wejściu, musi zaakceptować, odrzucić lub przesunąć w lewo na pusty symbol. Jak w przypadku 2), szef$M$ will now never visit the cell directly to the left of the rightmost $A$. If it would, then $M$ would run forever on input 1.

It is clear that in all three cases $M$ accepts all strings from the set $\{1^n;n\in\mathbb{N}\backslash\{0\}\}$ or it rejects them all.

The proof of the claim (in bold) about $C_3$ follows the same line as above. We take a one-tape 3-state Turing machine $M$ that accepts a string $1^n$ for some $n\geq 1$. Suppose $M$ is given an input $1^m$ for $m\geq n$. We have to prove that $M$ accepts this input. We have 3 cases:

1) When $M$ reads 1, it accepts.

2) When $M$ reads 1, it moves the head to the left. Because $M$ accepts the input $1^n$, it has to accept or move to the right on the blank symbol. Hence, it never visits the $n$th cell to the right of the initial cell. If it would, it would run forever on input $1^n$.

3) When $M$ reads 1, it moves the head to the right. It follows that after $m$ steps, the content of the tape is $A^m$ where $A$ is some symbol from the tape alphabet and the head of $M$ is on the leftmost blank symbol to the right of the last $A$. Because $M$ accepts the input $1^n$, it must accept or move to the left on the blank symbol. As in case 2), the head of $M$ will now never visit the $n$th cell to the left of the rightmost $A$. This is because on the input $1^n$, $M$ does not visit the cell directly left of the initial cell, because it contains the blank symbol and if it would read it, it would run forever.

It is clear that in all three cases $M$ accepts all strings from the set $\{1^m;m\geq n\}$.