Sprachklasse, erkennbar an Single-Tape-TMs mit drei Zuständen

9

Ich war eine Weile neugierig auf Turingmaschinen mit genau einem Band und genau 3 Zuständen (nämlich dem Startzustand , dem Annahmezustand q a c c e p t und dem Ablehnungszustand q r e j e c t ). Beachten Sie, dass ich beliebige (endliche) Bandalphabete zulasse (dh das Bandalphabet ist nicht auf das Eingabealphabet beschränkt).q0qacceptqreject

Rufen Sie der Einfachheit halber die Sprachklasse auf, die von solchen TMs erkannt wird . Ich habe mehrere Fragen zu dieser Klasse:C3

  1. Wurde bereits untersucht?C3
  2. Ist bekannt, dass anderen interessierenden Komplexitäts- / Berechenbarkeitsklassen entspricht?C3
  3. Ist die Klasse robust gegen Modelländerungen? Wenn zum Beispiel die verwendeten TMs während eines einzelnen Übergangs an Ort und Stelle bleiben dürfen (anstatt sich immer nach links oder rechts zu bewegen) oder wenn das Band in beide Richtungen unendlich anstatt nur nach rechts ist, wird die Klasse ausgeführt von Sprachen, die durch 3-Zustands-1-Band-TMs erkennbar sind, ändern sich?C3
  4. In welcher Beziehung steht zur Klasse der regulären Sprachen, R e g u l a r ? (Ist insbesondere jede reguläre Sprache in C 3 ?)C3RegularC3

Eine (eher flüchtige) Suche brachte nur diesen cs.stackexchange-Beitrag hervor, der relevant ist, aber meine Fragen nicht beantwortet, und dieses Papier , das ich nicht ausführlich genug gelesen habe, um sicherzugehen, dass es sich genau um die Klasse und nicht eine ähnliche, aber unterschiedliche Klasse (das Papier behauptet zu beweisen, dass (1) jede Sprache in C 3 entscheidbar ist und (2) dass C 3 und R e g u l a rC3C3C3Regularsind verschiedene Klassen mit nicht leerem Schnittpunkt). Wie in den Kommentaren des Beitrags cs.stackexchange erwähnt, können diese Arten von TMs als sehr spezielle zelluläre Automaten angesehen werden. Vielleicht könnte jemand helfen, der die Literatur zur Theorie der zellularen Automaten kennt.

Mikhail Rudoy
quelle
1
Wenn Sie nur einen nicht terminierenden Status und ein Band (Eingabeband) haben, kann sich Ihr Gerät an nichts erinnern, was es gelesen hat. So kann es genau Eingaben akzeptieren oder ablehnen, die bestimmte Symbole aus dem Eingabealphabet enthalten.
David G
4
Die Maschine kann sich nicht erinnern, was sie gelesen hat, aber sie kann das Gelesene mit etwas anderem umschreiben. Ich verstehe also nicht wirklich, warum die von Ihnen angegebene Charakterisierung korrekt ist. (dh ich kann mir eine einfache Maschine vorstellen, die akzeptiert und 011 ablehnt ; hier wird das Verhalten nicht vollständig dadurch bestimmt, welche Symbole in der Eingabe enthalten sind). 01011
Mikhail Rudoy
1
Du hast recht, meine Intuition war falsch.
David G

Antworten:

7

Das Biest ist extrem mächtig , zum Beispiel können wir ein TM , das jede Zeichenfolge der Form akzeptiertM

LY={r0n1mAmn}

und lehnt jede Zeichenfolge des Formulars ab

LN={r0n1mAm>n}

Die Idee ist, das erste in R umzuwandeln und dann den Kopf die Mitte der Saite erreichen zu lassen, dann einen "zustandslosen" Zick-Zack zu machen; Wenn es A vor R erreicht , akzeptiert es.rRAR

Informelle Beschreibung:

  • auf schreibe R und bewege dich nach rechts (bereite dich auf das Ablehnen vor)rR
  • auf schreibe c und bewege dich nach rechts (in Richtung Mitte)0c
  • auf schreibe > und bewege dich nach links (markiere eine 1 , bereite dich auf die nächste Kreuzung von links nach rechts vor und gehe nach links)1>1
  • auf schreibe < und bewege dich nach rechts (markiere eine 0 , bereite dich auf die nächste Kreuzung von rechts nach links vor und gehe nach rechts)c<0
  • auf schreibe > und gehe nach links (Kreuzung von links nach rechts, bereite dich auf die nächste von rechts nach links vor)<>
  • on schreibe < und gehe nach rechts (Kreuzung von rechts nach links, bereite dich auf die nächste von links nach rechts vor)><
  • auf akzeptieren, auf R ablehnenAR
  • auf leer ablehnenb

Beispiel:

  :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

Diese Zick-Zack-Technik wird in der kleinsten Universal-Turing-Maschine mit zwei Zuständen (mit 18 Symbolen) verwendet, die von Rogozhin konstruiert wurde (Rogozhin 1996. TCS, 168 (2): 215–240).

Es sollte etwas Aufmerksamkeit geschenkt werden, um zu beweisen, dass bei allen Eingaben anhält (beachten Sie nur, dass es bei leeren Eingaben zurückweist und alle nicht anhaltenden Symbole zu < oder > "konvergieren", was nicht zu einer Endlosschleife führen kann).M<>

Wie von DavidG kommentiert, ist die von M erkannte Sprache eine Obermenge von L Y (dh L YL ( M ) ), enthält jedoch keine Zeichenfolge von L N (dh L ( M ) L N. = ) und - wie von MikhailRudoy kommentiert - dies reicht aus, um zu beweisen, dass L ( M ) nicht regulär ist.L(M)MLYLYL(M)LNL(M)LN=L(M)

In der Tat, wenn regulär ist, dann wäre auch L ( M ) { r 0 1 A } = L Y = { r 0 n 1 m A m n } regulär (was nicht durch eine einfache Anwendung erfolgt des Pump-Lemmas); was zu einem Widerspruch führt.L(M)L(M){r01A}=LY={r0n1mAmn}

So ist nicht regulär .L(M)

... Aber wie alle Superhelden hat eine Achille-Ferse: Es kann nicht einmal die reguläre erkennen:C3

L={12n}

Informell kann nur das am weitesten links stehende ( b ist das leere Symbol) oder der rechte Nebel 1 b . . . als Haken und "expandieren" in die andere Richtung; Das endgültige Akzeptieren oder Ablehnen kann sich jedoch nicht auf dem leeren Symbol der gegenüberliegenden Seite befinden. Daher kann es nur im inneren Teil der 1 s ausgeführt werden. Ausgehend von einer ausreichend langen Eingabe kann es "gefälscht" werden, indem es um eins gedehnt wird.b1...b1b...1

Schließlich kann ich nach dem Lesen des Papiers bestätigen, dass das darin beschriebene Ein-Zustands-TM zu Ihrer -Klasse passt ... (also hier nichts Neues :-) ... und die Sprache, die der Autor verwendet, um zu beweisen, dass es enthält Nicht reguläre Sprachen sind meinen sehr ähnlich.C3

Marzio De Biasi
quelle
1
Die Antwort (+1) gefällt mir sehr gut. Das beschriebene TM akzeptiert jedoch eine andere Sprache. Es akzeptiert zum Beispiel auch Zeichenfolgen rrrrr00011AAAA, r000000r0000r0000r00011A, r00011A11111111 (nach A könnte es alles andere als eins sein) ...
David G
@ DavidG: Du hast recht! Ich habe nicht zu viel darüber nachgedacht ... Ich versuche es zu beheben.
Marzio De Biasi
4
LML(M)r01A=LL(M)L(M)r01A=LL(M)
Mikhail Rudoy
3
@MikhailRudoy: ja! Ich hatte die gleiche Idee. Ich habe cstheory geöffnet, um die Antwort zu bearbeiten, und Ihren Kommentar gesehen. Mal sehen, ob ich die Antwort unter Berücksichtigung Ihres Kommentars umschreiben kann ...
Marzio De Biasi
5

C3

(Ich poste dies als separate Antwort zur besseren Übersichtlichkeit)

M

LY={a0n1mRm2n}

und lehnt Zeichenfolgen der Form ab:

LN={a0n1mRm<2n}

aAZZSS))Z

Die Übergänge sind:

  • auf r schreibe RrR
  • 0Z
  • 1>1
  • ><
  • <>
  • ZS
  • S)
  • )Z
  • auf A akzeptieren, auf RAR
  • auf leer bb

Beispiel:

 :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)LYLYL(M)LNL(M)LN=

L(M){r01A}

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

LYCFLsLY01s2nLY

L(M)

... jetzt frage ich mich, ob dies eine andere Antwort ist, die das Rad neu erfindet, oder ob es ein neues (kleines) Ergebnis ist.

Marzio De Biasi
quelle
LYLN
@ EmilJeřábek: Ich sagte "nicht zu weit" ... ersticken Sie nicht die Ambitionen dieser winzigen Klasse ... :-)
Marzio De Biasi
2

In dieser Antwort wird angenommen, dass Turing-Maschinen unendliche Bänder in beide Richtungen haben. Die Ansprüche gelten nicht für unendliche Einwegbänder.

C3C3C3C3C3C3

C3C3LC3{1n;nN{0}}LLCC3{}{ε}{1n;nN}{1n;nN{0}}C3LC31nLn11mLmnC3C3{1}C3C3


C3M{1n;nN{0}}1nnN{0}M

M

MM

MnAnAMAMMAM

M{1n;nN{0}}


C3M1nn1M1mmnM

M

MM1nn1n

MmAmAMAM1nMnA1nM besucht die Zelle nicht direkt links von der ursprünglichen Zelle, da sie das leere Symbol enthält und wenn sie es lesen würde, würde sie für immer laufen.

M{1m;mn}

David G.
quelle
Erstens heißt es nirgends in der Frage, dass M an allen Eingängen anhalten muss, so dass ein Teil der Logik in dieser Antwort durcheinander kommt. Darüber hinaus macht die Logik in einigen Fällen für mich keinen Sinn. Wenn sich beispielsweise in Fall 3 M sowohl auf Leerzeichen als auch auf A nach links bewegt, besucht M die Zelle direkt links von A ganz rechts (im direkten Gegensatz zu der Behauptung aus der Antwort)
Mikhail Rudoy
Σ={1}k s.t. 1kL(M)L(M)={1nn>0}
@MikhailRudoy, ​​um zunächst den Fall 3 zu klären: Wenn sich der Kopf sowohl auf dem A- als auch auf dem leeren Symbol nach links bewegt, bewegt er sich für immer nach links und bleibt nicht stehen. Wenn es jemals (etwa nach 100 Schritten) die Zelle direkt links von A ganz rechts besucht, wird es bei Eingabe 1 nie angehalten (in diesem Fall enthält die Zelle direkt links von A ganz rechts das leere Symbol).
David G
@MikhailRudoy, ​​es ist wahr, dass ich angenommen habe, dass eine Turing-Maschine anhalten muss. Ich werde die Antwort so bearbeiten, dass sie auch die Möglichkeit enthält, dass sie für immer läuft. Das Ergebnis ist ähnlich.
David G
3
@MikhailRudoy: Übrigens ist das Hutproblem für Turing-Maschinen mit 1 Zustand entscheidbar. siehe Gabor T. Herman, Das Problem des einheitlichen Anhaltens für verallgemeinerte Ein-Zustands-Turingmaschinen . Das dort beschriebene Modell unterscheidet sich ein wenig von Ihrem: Das TM akzeptiert, wenn es in einer tödlichen Konfiguration endet (es gibt kein Akzeptieren / Ablehnen); Das Ergebnis gilt jedoch auch für Ihr Modell (Halten Sie einfach das TM auf den Symbolen an, die zu Ihren zusätzlichen Zustimmungs- / Ablehnungszuständen führen).
Marzio De Biasi