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

9

Przez pewien czas byłem ciekawy maszyn Turinga z dokładnie jedną taśmą i dokładnie 3 stanami (mianowicie stanem początkowym q0, 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).qacceptqreject

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

  1. Czy był wcześniej badany?C3
  2. Czy wiadomo, że równa się innym interesującym klasom złożoności / obliczalności?C3
  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ę?C3
  4. Jak odnosi się do klasy zwykłych języków, ? (W szczególności, czy każdy zwykły język w ?)C3RegularC3

(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.C3C3C3Regular

Michaił Rudoy
źródło
1
Jeśli masz tylko jeden stan nie kończący się i jedną taśmę (taśmę wejściową), urządzenie nie może zapamiętać niczego, co odczytał. Może więc akceptować lub odrzucać dokładnie dane wejściowe zawierające określone symbole z alfabetu wejściowego.
David G
4
Maszyna nie pamięta, co przeczytała, ale może przepisać to, co przeczytała, czymś innym. Więc tak naprawdę nie rozumiem, dlaczego podana przez ciebie charakterystyka byłaby poprawna. (tzn. mogę wymyślić prostą maszynę, która akceptuje i odrzuca ; tutaj zachowanie nie jest całkowicie określone przez to, które symbole są na wejściu). 01011
Michaił Rudoy
1
Masz rację, moja intuicja była błędna.
David G

Odpowiedzi:

7

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

LY={r0n1mAmn}

i odrzuca każdy ciąg formularza

LN={r0n1mAm>n}

Chodzi o przekształcenie pierwszego r w Ra następnie pozwólcie głowie sięgnąć do środka struny, a następnie wykonać „bezpaństwowy” zygzak; jeśli to osiągnieA 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 LY (to znaczy LYL(M)), ale nie zawiera żadnego ciągu z LN (to znaczy L(M)LN=) 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){r01A}=LY={r0n1mAmn}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 C3 ma piętę Achille'a: nawet nie rozpoznaje regularności:

L={12n}

Nieformalnie może korzystać tylko z lewej strony b1... (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 stronie1i 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 C3 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.

Marzio De Biasi
źródło
1
Bardzo podoba mi się odpowiedź (+1). Jednak opisana TM akceptuje inny język. Na przykład akceptuje także ciągi znaków rrrrr00011AAAA, r000000r0000r0000r00011A, r00011A11111111 (po A może być cokolwiek zamiast jednych) ...
David G
@DavidG: Masz rację! Nie myślałem o tym za dużo ... Próbuję to naprawić.
Marzio De Biasi,
4
Właściwie nawet przez L nie jest językiem rozpoznawanym przez opisaną TM, ten język zdecydowanie nie jest regularny: jeśli to TM M, następnie L(M)r01A=L tak krótki dowód sprzeczności (jeśli L(M) jest zatem regularny L(M)r01A=Lbędzie również regularne; sprzeczność) może to pokazaćL(M)nie jest regularny.
Michaił Rudoy
3
@MikhailRudoy: tak! Miałem ten sam pomysł. Otworzyłem cstheory, aby edytować odpowiedź, i zobaczyłem twój komentarz. Zobaczmy, czy mogę przepisać odpowiedź, biorąc pod uwagę twój komentarz ...
Marzio De Biasi
5

Nie doceniłem mocy C3... 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:

LY={a0n1mRm2n}

i odrzuca ciągi formularza:

LN={a0n1mRm<2n}

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 przekonwertujZ w S (Jeden) następnym razem, gdy głowa dotrze do Sprzekształć 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 LY (LYL(M)) i nie zawiera ciągów z LN (L(M)LN=).

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{r01A} stworzyć język CF:

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

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

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.

Marzio De Biasi
źródło
Cóż, język tutaj można obliczyć w tak niskiej klasie jak coNLOGTIME, więc nie wymaga on hiperkomputera. (W rzeczywistości,LY i LNmożna rozdzielić nawet w DLOGTIME.)
Emil Jeřábek
@ EmilJeřábek: Powiedziałem „nie zbyt daleko” ... nie tłumić ambicje tej maleńkiej klasy ... :-)
Marzio De Biasi
2

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 C3jako klasa wszystkich języków rozstrzygalna przez maszyny Turinga z jedną taśmą z 3 stanami (C3została zdefiniowana jako klasa języków rozpoznawalna przez maszyny Turinga z jedną taśmą z 3 stanami). Przedstawiłem klasęC3 ponieważ w mojej oryginalnej odpowiedzi nieświadomie zamieniłem klasy C3 i C3 (Rozważyłem tylko klasę C3).

Ta odpowiedź jest bardziej uzupełnieniem odpowiedzi @MarzioDeBiasi. Pokazał, że zajęciaC3 i C3nie są zawarte w CFL, a zatem zawierają dość interesujące języki. Jednak, jak pokażę w tym poście, każdy językL w C3 ma właściwość ustawioną {1n;nN{0}} jest albo w L lub w jego uzupełnieniu LC. A zatemC3jest również bardzo restrykcyjne, np. zawiera tylko trywialne, jednoargumentowe języki{}, {ε}, {1n;nN} i {1n;nN{0}}. KlasaC3zawiera nieco więcej jednojęzycznych języków. Utrzymuje jednak, że jeśliLC3 i 1nL dla n1, następnie 1mL dla wszystkich mn. Prostym następstwem jest to, że nie wszystkie zwykłe języki są w językuC3 ani w C3. Również język{1} nie jest w C3 ani w C3.


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

1) KiedyM czyta 1, przyjmuje lub odrzuca.

2) KiedyMczyta 1, przesuwa głowę w lewo. Jeśli chcemyMaby 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) KiedyModczytuje 1, przesuwa głowę w prawo. Wynika z tego, że pon kroki, zawartość taśmy jest An 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 chcemyMaby zatrzymać na tym wejściu, musi zaakceptować, odrzucić lub przesunąć w lewo na pusty symbol. Jak w przypadku 2), szefM 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 {1n;nN{0}} or it rejects them all.


The proof of the claim (in bold) about C3 follows the same line as above. We take a one-tape 3-state Turing machine M that accepts a string 1n for some n1. Suppose M is given an input 1m for mn. 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 1n, it has to accept or move to the right on the blank symbol. Hence, it never visits the nth cell to the right of the initial cell. If it would, it would run forever on input 1n.

3) When M reads 1, it moves the head to the right. It follows that after m steps, the content of the tape is Am 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 1n, 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 nth cell to the left of the rightmost A. This is because on the input 1n, 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 {1m;mn}.

David G
źródło
First of all, nowhere in the question does it say that M must halt on all inputs, so that screws up some of the logic in this answer. Beyond that, the logic in several of the cases doesn't make sense to me. For example, in case 3, if M moves left on both blank and A, then M will visit the cell directly left of the rightmost A (in direct contrast to the claim from the answer.)
Mikhail Rudoy
Nice; another way to state it is: if Σ={1} (unary languages) then k s.t. 1kL(M)L(M)={1nn>0} ...
Marzio De Biasi
@MikhailRudoy, to first clarify the case 3: if the head moves left on both A and blank symbol, then it will move left forever and will not halt. If it ever (say after 100 steps) visits the cell directly left of the rightmost A, then in the case of input 1 it never halts (in this case the cell directly left of the rightmost A will contain the blank symbol).
David G
@MikhailRudoy, it is true that I assumed that a Turing machine has to halt. I will edit the answer to include also the possibility that it runs forever. The result is similar.
David G
3
@MikhailRudoy: BTW the hatling problem is decidable for 1 state Turing machines; see Gabor T. Herman, The uniform halting problem for generalized one-state turing machines. The model described there is a little bit different from yours: the TM accepts if it ends in a mortal configuration (there is no Accept/Reject); but the result also applies to your model (just Halt the TM on the symbols that lead to your extra Accept/Reject states).
Marzio De Biasi