Ist eine Stack-Maschine mit einem Forward-Read-Iterator Turing vollständig?

7

Es ist bekannt, dass eine Maschine mit einem einzelnen Stapel als nur unbegrenztem Speicher nicht vollständig ist, wenn sie nur von der Oberseite des Stapels lesen kann. Ich möchte eine Maschine, die (etwas) leistungsfähiger als eine Stapelmaschine ist, aber immer noch nicht vollständig ist. (Ich frage mich, ob es eine nicht-Turing-vollständige Maschine gibt, die nicht deterministische Pushdown-Automaten mit einer einzigen polynomiellen Verlangsamung deterministisch simulieren kann.) Die harmloseste (unkomplizierte) Erweiterung, die mir in den Sinn kam, war eine (einzelne) Vorwärtsbewegung Iterator lesen.

Lassen Sie mich die Implementierungsdetails näher erläutern, um zu verdeutlichen, was ich unter einem Forward-Read-Iterator verstehe. Eine einfach verknüpfte Liste kann zum Implementieren eines Stapels verwendet werden. Lassen Sie die Liste durch einen Zeiger implementiert werden pTop, der entweder Null ist oder auf einen SListKnoten zeigt. Ein SListKnoten besteht aus einem Nutzlastfeld valueund einem Zeigerfeld pNext, wobei pNextentweder Null ist oder auf einen SListKnoten zeigt. Lassen Sie den Vorwärtslese-Iterator durch einen Zeiger implementiert werden pRead, der entweder Null ist oder auf einen SListKnoten zeigt. Die Zeiger pTopund pReadkönnen nicht direkt aufgerufen werden, sondern können nur über die folgenden Methoden verwendet werden:

  • Push(val)Erstellt einen neuen SListKnoten nmit n.value = valund n.pNext = pTopund setzt pTop = &n.
  • Pop()bricht ab, wenn pTop == 0oder pRead == pTop. Andernfalls liest val = pTop->valueund pTopNext = pTop->pNextgibt es den SListKnoten frei, auf den es zeigt pTop, setzt pTop = pTopNextund gibt ihn zurück val.
  • ReadBegin()setzt pRead = pTop.
  • ReadNext()bricht ab wenn pRead == 0. Andernfalls liest val = pRead->value, setzt pRead = pRead->pNextund kehrt es zurück val.
  • ReadFinished()gibt trueif pRead == 0und falseandernfalls zurück.
Thomas Klimpel
quelle
Ich sollte das zunächst klarstellen pTop == 0und pRead == 0. Eine Methode, ReadCancel()die setzt, pRead = 0könnte auch eine gute Idee sein, da sonst der Abbruch von Pop()for pRead == pTopärgerlich sein könnte.
Thomas Klimpel
3
Zwischen den Pushdown-Automaten und den Turing-Maschinen in der Chomsky-Hierarchie befindet sich die linear begrenzte nicht deterministische Turing-Maschine, die der kontextsensitiven Sprache entspricht .
Pål GD
1
Es gibt Automaten mit einem Stapel Stapel, aber ich habe den Namen vergessen. Ich erinnere mich auch an unsere "Homebrew" -Haufenautomaten .
Raphael
@ThomasKlimpel nur einen Hinweis darauf, dass meine Antwort einen Fehler enthielt, aber keinen katastrophalen. Sie sind immer noch von der Vollständigkeit von Turing überzeugt, aber Ihr Modell ist etwas leistungsfähiger als ich zuerst dachte (ich habe die nicht löschende Eigenschaft falsch interpretiert im Nachhinein wirklich dumm).
Luke Mathieson
1
@ThomasKlimpel, ein zweites Heads-Up, Benutzer23013 ist korrekt (siehe seine Antwort), Ihr Modell ist Turing komplett - der Clou ist, dass Sie zwei Zeiger im Stapel haben, während Stapelautomaten nur einen haben (damit er sich um den Stapel bewegen kann). kann aber nur oben knallen / drücken).
Luke Mathieson

Antworten:

5

Ihr Modell ist leider Turing-komplett.

Mit dem folgenden Algorithmus können Sie eine Warteschlange in Ihrer Datenstruktur simulieren. Es wurden 3 neue Stapelsymbole eingeführt:d,x,y.

Enqueue(val)ist einfach Push(val).

Für Dequeue():

  1. ReadBegin().
  2. Zählen Sie die Anzahl von allem anderen - Anzahl von dim gesamten Stapel (der immer nicht negativ sein sollte). drückeny oder Pop x für jeden dund drücken x oder Pop yfür alles andere. Immer lieber Pop als Push. Endlich wird es keine gebeny im Stapel und das Ergebnis ist die Anzahl von x auf der Oberseite des Stapels.
  3. ReadBegin().
  4. Während pTopist einx::
    1. Wiederholen, ReadNext()bis etwas anderes als zurückgegeben wirdx und d.
    2. Pop().
  5. Drücken Sie a d.
  6. Das letzte Ergebnis von ReadNext()wird als Ergebnis von zurückgegeben Dequeue.

Der Beweis ist unkompliziert. Überprüfen Sie den Versionsverlauf auf eine kompliziertere Version und reduzieren Sie sie zunächst auf eine bidirektionale Version.

user23013
quelle
Haben Sie den Unterschied gefunden, Sie haben Recht, das Modell des OP ist Turing vollständig. Ein Stapelautomat hat keinen zweiten Lesekopf zum Scannen des Stapels, er kann nur seinen normalen Kopf auf und ab bewegen, sondern nur nach oben drücken.
Luke Mathieson
5

Ihr Modell ist Turing vollständig (im Gegensatz zu dem, was ich zuvor gedacht habe). In der Antwort von user23013 finden Sie eine Skizze des Beweises (das Wesentliche ist, dass Sie eine Warteschlange simulieren können und Warteschlangenautomaten Turing vollständig sind).

Es gibt verschiedene Möglichkeiten, Ihr Modell zu schwächen, damit es mit linear gebundenen Automaten oder niedriger gleichwertig ist.

Ginsburg, Greibach & Harrison [1] geben eine Maschine namens "Stack Automaton" an, bei der es sich um einen PDA mit zwei zusätzlichen Funktionen handelt: 1. Der Eingabekopf kann sich nach links und rechts bewegen (damit zuvor gesehene Teile der Eingabe gescannt werden können). 2. Der Lese- / Schreibkopf auf dem Stapel kann den Stapel im schreibgeschützten Modus durchsuchen, aber das Drücken und Knallen erfolgt immer noch nur oben. Beachten Sie hier den Hauptunterschied zu Ihrem Modell, der mich früher verwirrt hat: Der Stapel hat nur einen Kopf / Zeiger, mit dem er sich auf und ab bewegen kann, während Ihr Stapel zwei hat, was ausreicht, um Ihr Modell Turing vollständig zu machen. Sie geben auch ein anderes Modell [2] an, bei dem die Eingabe nur von links nach rechts gelesen werden kann, das zusätzliche schreibgeschützte Stapelscannen jedoch weiterhin verfügbar ist.

In Abbildung 2 von [1] geben sie das Containment an (bewiesen in Abschnitt 5 desselben, möglicherweise mit einigen Teilen in [2]), und in nichtdeterministischen Zwei-Wege-Stapelautomatensprachen sind streng enthalten R. Sie entsprechen jedoch nichtdeterministischen linear gebundenen Automaten, sodass sie kontextsensitive Sprachen erkennen.

Zweiwege- und nichtdeterministische Stapelautomaten und deterministische Zweiwegestapelautomaten scheinen gleichwertig zu sein, jedoch macht das Ändern des Eingabekopfs in Einweg einen signifikanten Unterschied. Die Menge der nichtdeterministischen Einweg-Stapelautomatensprachen ist eine strikte Teilmenge der kontextsensitiven Sprachen (ich kann noch nicht genau sagen, wo) und die Menge der deterministischen Einweg-Stapelautomaten (die Ihrem Modell entsprechen) ) Languages ​​ist eine strikte Teilmenge der Menge nichtdeterministischer Einweg-Stapelautomatensprachen.

Ein schwächerer Typ, der darunter liegt, sind nicht löschende Stapelautomaten, die nur in den Stapel schreiben können.

Hopcroft & Ullman zeigen, dass die Sprachen, die von nicht löschenden deterministischen Stapelautomaten erkannt werden, entsprechen DSPACE(nlogn) und nicht löschbare nichtdeterministische Stapelautomaten entsprechen DSPACE(n2).

Nachtrag

Nach einigem Hin und Her deuten diese Vorlesungsfolien darauf hin, dass deterministische Stapelautomaten in einer Richtung, die nicht gelöscht werden können, streng schwächer sind als die Version in zwei Richtungen. Erkennen Sie also etwas weniger alsDSPACE(nlogn).

Ich habe auch weitere Hopcroft & Ullman [4,5] -Papiere gefunden, die vielleicht ein paar weitere Hinweise liefern, aber an diesem Punkt scheinen sie tangential zu sein. [5] beweist zumindest einige Äquivalenzen einiger Stapelautomaten mit LBAs.

Verweise

  1. Seymour Ginsburg, Sheila A. Greibach und Michael A. Harrison, "Stack Automata and Compiling". Journal of the ACM, 14 (1): 172–201, 1967.
  2. Seymour Ginsburg, Sheila A. Greibach und Michael A. Harrison, "One-Way-Stack-Automaten". Journal of the ACM, 14 (2): 389–418, 1967.
  3. John E. Hopcroft, Jeffrey D. Ullman, "Nonerasing Stack Automata" . JCSS, 1 (2): 166–186, 1967.
  4. John E. Hopcroft, Jeffrey D. Ullman, "Deterministische Stapelautomaten und der Quotientenoperator" , JCSS, 2: 1-12, 1968.
  5. John E. Hopcroft, Jeffrey D. Ullman, "Zwei Ergebnisse zu Einweg-Stapelautomaten" , Symposium über Switching und Automatentheorie (SWAT - aber nicht diese SWAT), 1967.
Luke Mathieson
quelle
Das Modell in dieser Frage ist jedoch nicht nicht löschbar, was seiner Zwei-Wege-Version entsprechen sollte (durch Aufzeichnen und Zählen von Push / Pop / Up / Down-Operationen im Stapel).
user23013
@ user23013 richtig, ich habe den nicht löschenden Teil falsch interpretiert.
Luke Mathieson
Ich habe gerade versucht herauszufinden, warum meine Schlussfolgerung nicht mit Ihrer übereinstimmt, und ich bin überzeugt, dass dieses Modell tatsächlich Turing jetzt vollständig ist. Zur Bestätigung: Wo steht, dass der Zwei-Wege-Stapelautomat den Stapel nicht als Warteschlange verwenden kann (setzen Sie den zusätzlichen Zeiger unten und bewegen Sie sich nie nach unten)? Wenn es irgendwie verboten ist, denke ich, dass das in dieser Frage nicht angegeben ist.
user23013
@ user23013 Der zweite Zeiger ist schreibgeschützt. Es gibt keine Operation, um etwas hinzuzufügen, wo es pReadist. (wie ich es verstehe)
Luke Mathieson
Aber pTopund pReadsind zwei getrennte Zeiger. Sie können bei einreihen pTopund aus dem Verkehr ziehen (indem Sie nach oben gehen und alles unten ignorieren) pRead? (Wenn es in beide Richtungen ist.)
user23013