Lektion 3.1

Turingmaschinen

40 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • eine Turingmaschine als Tupel aufschreiben und jede Komponente erklären,

  • Konfigurationen und Rechenschritte einer Turingmaschine Schritt für Schritt notieren,

  • eine Turingmaschine für {anbn:n≥0}\{a^n b^n : n \ge 0\} als Übergangstabelle lesen und ihren Lauf protokollieren,

  • Akzeptieren, Verwerfen und Nicht-Halten auseinanderhalten,

  • begründen, warum Mehrband-Maschinen und nichtdeterministische Maschinen nicht mehr Sprachen erkennen als die einfache Turingmaschine.

Vorausgesetzt: Deterministische endliche Automaten (DEA), Nichtdeterministische Automaten und die Potenzmengenkonstruktion, Kellerautomaten

Ein endlicher Automat kann nicht zählen: Die Sprache {anbn:n≥0}\{a^n b^n : n \ge 0\} ist nach dem Pumping-Lemma nicht regulär. Ein Kellerautomat schafft sie mit seinem Stapel, aber schon bei {anbncn:n≥0}\{a^n b^n c^n : n \ge 0\} ist auch er am Ende, denn diese Sprache ist nicht kontextfrei. Jedes Mal hat ein stärkeres Modell mehr Speicher oder einen freieren Zugriff darauf bekommen.

Wo hört das auf? Gibt es ein Modell, das alles kann, was ein Computer überhaupt kann? Alan Turing hat 1936 dafür einen Menschen mit Bleistift und Papier beobachtet. Wer eine lange Rechnung von Hand ausführt, schaut immer nur auf eine Stelle des Papiers, hat einen von endlich vielen Gedanken im Kopf (welcher Teil der Rechnung gerade dran ist), schreibt etwas hin oder radiert, und geht dann ein Stück weiter. Das Papier ist so lang wie nötig.

Daraus wird die Turingmaschine: ein endlicher Automat mit einem unbegrenzten Band, auf dem er lesen, schreiben und in beide Richtungen gehen kann.

Vermute zuerst

Beim Kellerautomaten kommt man nur an das oberste Zeichen des Stapels heran. Ersetze den Stapel durch ein Band, auf dem der Automat frei nach links und rechts gehen und jedes Feld überschreiben kann. Was ändert sich?

Definition

Turingmaschine

Eine (deterministische) Turingmaschine (TM) ist ein Tupel M=(Q,Σ,Γ,δ,q0,□,qja,qnein)M = (Q, \Sigma, \Gamma, \delta, q_0, \square, q_\text{ja}, q_\text{nein}) mit:

  • QQ: endliche Menge von Zuständen,
  • Σ\Sigma: Eingabealphabet,
  • Γ⊇Σ\Gamma \supseteq \Sigma: endliches Bandalphabet, die Zeichen, die auf dem Band stehen dürfen,
  • □∈Γ∖Σ\square \in \Gamma \setminus \Sigma: das Blank, das Zeichen für ein leeres Feld,
  • q0∈Qq_0 \in Q: Startzustand,
  • qja,qnein∈Qq_\text{ja}, q_\text{nein} \in Q, qja≠qneinq_\text{ja} \ne q_\text{nein}: akzeptierender und verwerfender Haltezustand,
  • δ:(Q∖{qja,qnein})×Γ→Q×Γ×{L,R,N}\delta: (Q \setminus \{q_\text{ja}, q_\text{nein}\}) \times \Gamma \to Q \times \Gamma \times \{L, R, N\}: Übergangsfunktion.

Das Band ist eine in beide Richtungen unendliche Reihe von Feldern. Am Anfang steht dort die Eingabe w∈Σ∗w \in \Sigma^*, sonst nur □\square, und der Kopf steht auf dem ersten Zeichen von ww (bei w=εw = \varepsilon auf einem Blank).

δ(q,a)=(p,b,D)\delta(q, a) = (p, b, D) heißt: Im Zustand qq und beim Lesen von aa schreibt die Maschine bb in das Feld, wechselt nach pp und bewegt den Kopf ein Feld nach links (LL), nach rechts (RR) oder gar nicht (NN). In qjaq_\text{ja} und qneinq_\text{nein} hält sie.

δ(q,a)=(p,b,D),q∈Q∖{qja,qnein}, a,b∈Γ, D∈{L,R,N}\delta(q, a) = (p, b, D), \qquad q \in Q \setminus \{q_\text{ja}, q_\text{nein}\},\ a, b \in \Gamma,\ D \in \{L, R, N\}
Definition

Konfiguration und Rechenschritt

Eine Konfiguration hält Bandinhalt, Zustand und Kopfposition fest. Man schreibt sie als u q vu\,q\,v mit u,v∈Γ∗u, v \in \Gamma^*, q∈Qq \in Q: Auf dem Band steht uvuv (sonst nur Blanks), der Zustand ist qq, der Kopf steht auf dem ersten Zeichen von vv. Steht er auf einem Blank rechts von uu, schreibt man u q □u\,q\,\square.

Die Startkonfiguration bei Eingabe ww ist q0 wq_0\,w. Geht K′K' durch einmaliges Anwenden von δ\delta aus KK hervor, schreibt man K⊢K′K \vdash K' (ein Rechenschritt). K⊢∗K′K \vdash^* K' heißt: in null oder mehr Schritten. Beispiel: Ist δ(q1,a)=(q1,a,R)\delta(q_1, a) = (q_1, a, R), so gilt X q1 abb⊢Xa q1 bbX\,q_1\,abb \vdash Xa\,q_1\,bb.

Bei Eingabe ww gibt es drei Möglichkeiten:

  • MM akzeptiert ww, wenn q0 w⊢∗u qja vq_0\,w \vdash^* u\,q_\text{ja}\,v für irgendwelche u,vu, v.
  • MM verwirft ww, wenn q0 w⊢∗u qnein vq_0\,w \vdash^* u\,q_\text{nein}\,v.
  • MM hält nicht auf ww, wenn sie keinen der beiden Haltezustände je erreicht. Die Rechnung läuft dann unendlich lange.

Die von MM erkannte Sprache ist L(M)={w∈Σ∗:M akzeptiert w}L(M) = \{w \in \Sigma^* : M \text{ akzeptiert } w\}.

Beispiel

Die Idee für anbna^n b^n

Gesucht ist eine TM mit L(M)={anbn:n≥0}L(M) = \{a^n b^n : n \ge 0\}, die auf jedem Wort hält. Die Idee ist das Abhaken von Hand:

  • Ersetze das linkeste noch unmarkierte aa durch XX.
  • Laufe nach rechts zum ersten noch unmarkierten bb und ersetze es durch YY. Gibt es keins, verwirf.
  • Laufe zurück bis zum XX und beginne rechts davon die nächste Runde.
  • Steht rechts vom letzten XX kein aa mehr, sondern ein YY, prüfe, dass bis zum Ende nur noch YY kommen. Dann akzeptiere, sonst verwirf.

Bandalphabet Γ={a,b,X,Y,□}\Gamma = \{a, b, X, Y, \square\}; Zustände q0q_0 (nächstes aa), q1q_1 (nach rechts zum bb), q2q_2 (zurück zum XX), q3q_3 (Rest prüfen), qjaq_\text{ja}, qneinq_\text{nein}.

Bei Eingabe anbna^n b^n steht nach kk Runden Xkan−kYkbn−kX^k a^{n-k} Y^k b^{n-k} auf dem Band. Eine solche Aussage, die jede Runde erhält, heißt Invariante; mit Induktion über kk folgt, dass nach nn Runden XnYnX^n Y^n dasteht und die Maschine akzeptiert.

Beispiel

Übergangstabelle

Jede Zeile ist ein Wert δ(q,a)=(p,b,D)\delta(q, a) = (p, b, D).

Zustandgelesenneuer ZustandgeschriebenBewegungBedeutung
q0q_0aaq1q_1XXRRlinkestes aa abhaken
q0q_0YYq3q_3YYRRalle aa abgehakt, Rest prüfen
q0q_0□\squareqjaq_\text{ja}□\squareNNleeres Wort
q1q_1aaq1q_1aaRRüber aa nach rechts
q1q_1YYq1q_1YYRRüber YY nach rechts
q1q_1bbq2q_2YYLLerstes bb abhaken
q2q_2aaq2q_2aaLLzurück
q2q_2YYq2q_2YYLLzurück
q2q_2XXq0q_0XXRRrechts vom letzten XX weiter
q3q_3YYq3q_3YYRRnur YY erlaubt
q3q_3□\squareqjaq_\text{ja}□\squareNNEnde erreicht, akzeptieren

Für alle übrigen Paare (zum Beispiel q1q_1 liest □\square, q3q_3 liest bb) gilt δ(q,a)=(qnein,a,N)\delta(q, a) = (q_\text{nein}, a, N): Die Maschine verwirft.

So ist δ\delta überall definiert, wie verlangt. Ein Wort, das nicht die Form a∗b∗a^* b^* hat, scheitert spätestens in q3q_3: Bei abaaba hakt die Maschine aa und bb ab, wechselt nach q3q_3 und liest dort aa.

Beispiel

Ablaufprotokoll für aabbaabb

Die Spalte "Übergang" nennt das Paar aus Zustand und gelesenem Zeichen, dessen Zeile angewandt wurde.

SchrittKonfigurationÜbergang
0q0 aabbq_0\,aabbStart
1X q1 abbX\,q_1\,abb(q0,a)(q_0, a)
2Xa q1 bbXa\,q_1\,bb(q1,a)(q_1, a)
3X q2 aYbX\,q_2\,aYb(q1,b)(q_1, b)
4q2 XaYbq_2\,XaYb(q2,a)(q_2, a)
5X q0 aYbX\,q_0\,aYb(q2,X)(q_2, X)
6XX q1 YbXX\,q_1\,Yb(q0,a)(q_0, a)
7XXY q1 bXXY\,q_1\,b(q1,Y)(q_1, Y)
8XX q2 YYXX\,q_2\,YY(q1,b)(q_1, b)
9X q2 XYYX\,q_2\,XYY(q2,Y)(q_2, Y)
10XX q0 YYXX\,q_0\,YY(q2,X)(q_2, X)
11XXY q3 YXXY\,q_3\,Y(q0,Y)(q_0, Y)
12XXYY q3 □XXYY\,q_3\,\square(q3,Y)(q_3, Y)
13XXYY qja □XXYY\,q_\text{ja}\,\square(q3,□)(q_3, \square)

Nach 13 Schritten hält die Maschine in qjaq_\text{ja}: aabbaabb wird akzeptiert.

Zum Vergleich aabaab: Nach 5 Schritten steht X q0 aYX\,q_0\,aY da, die zweite Runde hakt das zweite aa ab, und q1q_1 läuft bis XXY q1 □XXY\,q_1\,\square. Für (q1,□)(q_1, \square) gibt es keine Zeile, die Maschine verwirft nach 8 Schritten. Für anbna^n b^n braucht sie genau 2n2+2n+12n^2 + 2n + 1 Schritte, denn jede Runde läuft hin und zurück über etwa nn Felder.

Kurz geprüft

Die Maschine aus der Tabelle bekommt das Wort abbabb. Wie endet der Lauf?

Beispiel

Eine Maschine, die nicht immer hält

Sei Σ={a,b}\Sigma = \{a, b\} und M′M' die Maschine mit δ(q0,a)=(q0,a,N)\delta(q_0, a) = (q_0, a, N), δ(q0,b)=(qja,b,N)\delta(q_0, b) = (q_\text{ja}, b, N) und δ(q0,□)=(qnein,□,N)\delta(q_0, \square) = (q_\text{nein}, \square, N).

Bei einem Wort, das mit bb beginnt, akzeptiert M′M' nach einem Schritt. Beim leeren Wort verwirft sie. Bei einem Wort, das mit aa beginnt, bleibt sie ewig in q0q_0 auf demselben Feld stehen: q0 aw⊢q0 aw⊢…q_0\,aw \vdash q_0\,aw \vdash \dots Sie hält nicht.

Es gilt L(M′)={bw:w∈Σ∗}L(M') = \{bw : w \in \Sigma^*\}, dieselbe Sprache wie bei einer Maschine, die bei aa verwirft. Die Sprache verrät also nicht, ob eine Maschine außerhalb von L(M)L(M) verwirft oder ewig rechnet. Von außen siehst du nach endlich vielen Schritten nie sicher, ob eine Rechnung noch endet. Das führt zum Halteproblem.

Häufige Fehler

Nicht-Halten ist kein Verwerfen

"Die Maschine hat das Wort nach 1000 Schritten noch nicht akzeptiert, also verwirft sie es." Oder: "Das Band ist so lang wie die Eingabe."

Richtig ist

Verwerfen heißt: Die Maschine erreicht qneinq_\text{nein} und hält. Nicht-Halten ist ein dritter Ausgang. Für L(M)L(M) zählt beides gleich, für die Frage, ob man eine Antwort bekommt, nicht. Nach 1000 Schritten kann die Maschine immer noch akzeptieren. Und das Band ist unbegrenzt: Neben der Eingabe stehen unendlich viele Blanks, die die Maschine beschreiben darf.

Definition

Mehrband-Turingmaschine

Eine kk-Band-Turingmaschine hat kk Bänder mit je einem eigenen Kopf. Die Übergangsfunktion liest die kk Zeichen unter allen Köpfen gleichzeitig und schreibt, bewegt jeden Kopf einzeln:

δ:(Q∖{qja,qnein})×Γk→Q×Γk×{L,R,N}k\delta: (Q \setminus \{q_\text{ja}, q_\text{nein}\}) \times \Gamma^k \to Q \times \Gamma^k \times \{L, R, N\}^k.

Die Eingabe steht auf Band 1, die anderen Bänder sind anfangs leer. Akzeptieren, Verwerfen und Nicht-Halten sind wie bisher erklärt.

Beispiel für anbna^n b^n: Kopiere jedes aa auf Band 2, gehe dort zurück an den Anfang der Kopie und hake dann für jedes bb auf Band 1 ein aa auf Band 2 ab. Das braucht ungefähr 3n3n Schritte statt 2n2+2n+12n^2 + 2n + 1.

Satz

Mehrband-Maschinen sind nicht stärker

Zu jeder kk-Band-Turingmaschine MM gibt es eine Turingmaschine M′M' mit einem Band, die auf jeder Eingabe genau dann akzeptiert, verwirft oder nicht hält, wenn MM es tut. Insbesondere ist L(M′)=L(M)L(M') = L(M). Macht MM auf einer Eingabe der Länge nn genau tt Schritte, so braucht M′M' höchstens c⋅t⋅(n+t)c \cdot t \cdot (n + t) Schritte mit einer Konstanten cc, für t≥nt \ge n also O(t2)O(t^2).

Definition

Nichtdeterministische Turingmaschine

Wie beim NEA darf eine nichtdeterministische Turingmaschine (NTM) in einer Situation mehrere Möglichkeiten haben. Statt eines Tripels liefert δ\delta eine endliche Menge von Tripeln:

δ:(Q∖{qja,qnein})×Γ→P(Q×Γ×{L,R,N})\delta: (Q \setminus \{q_\text{ja}, q_\text{nein}\}) \times \Gamma \to \mathcal{P}(Q \times \Gamma \times \{L, R, N\}),

wobei P\mathcal{P} die Potenzmenge bezeichnet. Aus einer Konfiguration können also mehrere Folgekonfigurationen hervorgehen. Alle möglichen Rechnungen bilden den Berechnungsbaum. Die NTM akzeptiert ww, wenn mindestens ein Pfad in qjaq_\text{ja} endet; andere Pfade dürfen verwerfen oder unendlich lang sein. Verwirft ein Pfad und akzeptiert ein anderer, wird das Wort also akzeptiert: Es gibt keine Mehrheitsabstimmung.

Satz

Nichtdeterminismus erkennt keine neuen Sprachen

Zu jeder nichtdeterministischen Turingmaschine NN gibt es eine deterministische Turingmaschine DD mit L(D)=L(N)L(D) = L(N).

Kurz geprüft

Warum durchsucht DD im Beweis den Berechnungsbaum ebenenweise und nicht, indem sie einen Pfad bis zum Ende verfolgt (Tiefensuche)?

Zusammenfassung

  • Eine Turingmaschine (Q,Σ,Γ,δ,q0,□,qja,qnein)(Q, \Sigma, \Gamma, \delta, q_0, \square, q_\text{ja}, q_\text{nein}) ist ein endlicher Automat mit einem unbegrenzten Band zum Lesen und Schreiben.

  • δ(q,a)=(p,b,D)\delta(q, a) = (p, b, D): im Zustand qq das Zeichen aa lesen, bb schreiben, nach pp wechseln, den Kopf nach D∈{L,R,N}D \in \{L, R, N\} bewegen.

  • Eine Konfiguration u q vu\,q\,v hält Bandinhalt, Zustand und Kopfposition fest; ⊢\vdash ist ein Rechenschritt.

  • Auf einer Eingabe akzeptiert eine TM, verwirft sie oder hält nicht. Nicht-Halten ist ein eigener Ausgang, kein Verwerfen.

  • Mehrband-Maschinen lassen sich mit einem Band und Spuren simulieren, mit höchstens quadratischem Zeitaufwand.

  • Nichtdeterministische Turingmaschinen erkennen dieselben Sprachen wie deterministische; die Simulation durchsucht den Berechnungsbaum in Breitensuche.

Übungen

Aufgabe 1Multiple Choice

Die Maschine aus der Lektion ist in der Konfiguration XX q1 YbXX\,q_1\,Yb. Welche Konfiguration folgt?

Aufgabe 2Numerisch

Wie viele Rechenschritte macht die Maschine aus der Lektion auf der Eingabe aaabbbaaabbb, bis sie in qjaq_\text{ja} hält?

Aufgabe 3Multiple Choice

Eine Maschine addiert 11 zu einer Binärzahl. Startzustand rr, Haltezustand ff (akzeptierend):

Zustandgelesenneuer ZustandgeschriebenBewegung
rr00rr00RR
rr11rr11RR
rr□\squareuu□\squareLL
uu11uu00LL
uu00ff11NN
uu□\squareff11NN

Was steht nach dem Halten auf dem Band, wenn die Eingabe 111111 war?

Aufgabe 4Freitext

Zeige: Zu jeder Turingmaschine MM gibt es eine Turingmaschine M′M' mit L(M′)=L(M)L(M') = L(M), die niemals verwirft, also auf jedem Wort außerhalb von L(M)L(M) nicht hält.

Aufgabe 5Freitext

Gib eine Turingmaschine mit einem Band an, die genau die Palindrome über {a,b}\{a, b\} akzeptiert (Wörter, die vorwärts und rückwärts gleich gelesen werden, einschließlich ε\varepsilon) und auf jedem Wort hält. Schreibe die Übergänge als Tabelle und erkläre die Bedeutung jedes Zustands.

Aufgabe 6Multiple Choice

Welche Aussage über eine nichtdeterministische Turingmaschine NN und die deterministische Maschine DD aus dem Simulationsbeweis stimmt?