Sind Turing -Maschinen leistungsfähiger als Pushdown -Automaten?

Question

Ich habe ein Ergebnis erzielt, als ich einige Automatenbücher gelesen habe, dass Turing -Maschinen leistungsfähiger zu sein scheinen als Pushdown -Automaten. Da das Band einer Turing -Maschine immer so gemacht werden kann, sich wie ein Stapel zu verhalten, scheint es, dass wir tatsächlich behaupten können, dass TMs leistungsfähiger sind.

Ist das wahr?

Answer 1

Wenn Sie nur der Meinung sind, dass "Turing -Maschinen immer so gemacht werden können, sich wie ein Stapel zu verhalten", können Sie nur zu dem Schluss kommen, dass sie mindestens so leistungsfähig sind wie Pushdown -Automaten.

Aber im Allgemeinen ist es wahr, Turing -Maschinen sind leistungsfähiger als PDAs. Am einfachsten wäre es, zu zeigen, dass Turing -Maschinen kontextempfindliche Sprachen beschreiben können.

Answer 2

Sie können nicht auf den Boden des Stapels gehen, ohne den Rest des Stapels zu "vergessen". Mit einer Turing -Maschine können Sie leicht auf das Band hin und her gehen.

Diese einfache Aufgabe kann nicht mit einem Pushdown -Wandler durchgeführt werden (ungefähr das Gleiche wie die Pushdown -Automata, aber das kann in jedem Schritt Dinge schreiben), kann aber leicht mit einem Band erfolgen:

Lesen Sie eine Zeichenfolge $ w $ und schreiben Sie dann die Zeichenfolge zweimal: $ ww $

Wenn Sie nicht von Wandlern hören möchten, ist das ähnliche Problem für Sie: Diese Sprache ist leicht von einer Turing -Maschine zu erkennen, aber nicht mit einem Pushdown -Automat:

$$ l = {ww Mid W in σ^* } $$

Aber ich denke, mit einem Wandler bekommt man einen Verständnis für den Unterschied.

Answer 3

Turing -Maschinen sind in der Tat leistungsfähiger als normale PDAs.

Im Sonderfall einer PDA mit zwei Stapeln (TPDA oder 2-PDA) ist die TPDA jedoch gleichermaßen leistungsfähig als eine Turing-Automata.

Die Grundidee ist, dass Sie das TM-Band mit zwei Stapeln simulieren können: Im linken Stapel wird alles gespeichert, das vom Kopf auf dem Turing-Tape gelassen wird, während das Symbol unter dem Kopf und alles direkt vom Kopf in der gespeichert ist Anderer Stapel. Und so kann die TPDA die Arbeit einer Turing -Maschine simulieren und sind gleichwertig. Eine etwas detailliertere Beschreibung kann gefunden werden hier.

Answer 4

Einer Turing -Maschine ist leistungsfähiger als eines Pushdown Automaton - Das ist ein grundlegender Theorem der Automatentheorie und kann in vielerlei Hinsicht bewiesen werden. Zum Beispiel ist das Anhaltungsproblem für TMS unentscheidbar-es gibt kein Programm (oder andere TM), das immer eine korrekte Ja-or-Nein-Antwort auf die Frage gibt: Wird dieser TM bei diesem Eingangsbestand stehen? Aber für PDAs ist das Anhaltsproblem lösbar. Die Modelle haben also von Natur aus unterschiedliche Leistung, das TM -Modell hat mehr Leistung als das PDA -Modell, aber auch "leidet" dafür.

Aber zwei Pushdown -Automaten "Zusammenarbeiten" können eine Turing -Maschine simulieren. Wir müssen nur angeben, was wir mit zwei PDAs meinen, die zusammenarbeiten - beide sind mit der Eingangszeichenfolge verbunden und jeder kann unabhängig voneinander mit seinem Stapel arbeiten. Ihre endlichen Zustandskontrollen sind ebenfalls verbunden oder gleichbedeutend mit einer einzigen Finite-State-Kontrolle verbunden.

Der Beweis dafür geht grob, dass jeder der PDAs die Hälfte des TM -Bandes simulieren kann, dh dem Teil des TMS -Bandes, der am Heimquadrat beginnt und auf unbestimmte Zeit nach links oder rechts ausgeht. Die Details können etwas unordentlich werden, aber die Grundidee ist einfach. Die Oberseite des "linken" Pushdown -Speichers repräsentiert das aktuelle Kopfquadrat des TM und der Boden repräsentiert das linke aktive Quadrat des TM -Bandes. Ähnlich für den "rechten" Pushdown -Store. Wenn sich beispielsweise die Bewegungen um einen Quadrat nach links bewegt, steckt die simulierende Kombination von PDAs ein Symbol aus dem rechten Drangspeicher und schiebt es auf den oberen Rand des linken Pushdown -Store. Wenn das TM das Symbol unter seinem Kopf neu schreibt, platziert die linke PDA sein oberes Symbol (der vorherige Wert) und drückt ein anderes Symbol (den neuen Wert) zurück.

Die Kombination von zwei PDAs, die auf diese Weise arbeiten, hat also genau die gleiche Leistung wie TMS, und das Anstiegsproblem für die Kombination ist ebenfalls unentscheidbar.

Answer 5

Zeigen Sie einfach einen TM auf, der $ 0^n 1^n 2^n $ akzeptiert, was nicht kontextfrei ist (und daher gibt es keine PDA, die es akzeptiert).

Answer 6

Der übliche Beweis ist ein Umweg.

1. Zeigen Sie, dass Pushdown-automata genau die akzeptiert Kontextfreie Sprachen, der Satz der Sprachen, die durch kontextfreie Grammatiken akzeptiert werden. (In jedem Lehrbuch zu dieser Angelegenheit gefunden)
2. Beachten Sie, dass Turing -Maschinen alle rekursiven Sprachen akzeptieren (per Definition).
3. Zeigen Sie, dass die kontextfreien Sprachen beispielsweise eine ordnungsgemäße Teilmenge der rekursiven Sprachen sind Lemma pumpen -was leicht mit kontextfreien Grammatiken nachgewiesen wird-und $ {ww Mid W in {a, b }^*} $.