Turingmaschinen
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 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 ist nach dem Pumping-Lemma nicht regulär. Ein Kellerautomat schafft sie mit seinem Stapel, aber schon bei 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.
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?
Turingmaschine
Eine (deterministische) Turingmaschine (TM) ist ein Tupel mit:
- : endliche Menge von Zuständen,
- : Eingabealphabet,
- : endliches Bandalphabet, die Zeichen, die auf dem Band stehen dürfen,
- : das Blank, das Zeichen für ein leeres Feld,
- : Startzustand,
- , : akzeptierender und verwerfender Haltezustand,
- : Übergangsfunktion.
Das Band ist eine in beide Richtungen unendliche Reihe von Feldern. Am Anfang steht dort die Eingabe , sonst nur , und der Kopf steht auf dem ersten Zeichen von (bei auf einem Blank).
heißt: Im Zustand und beim Lesen von schreibt die Maschine in das Feld, wechselt nach und bewegt den Kopf ein Feld nach links (), nach rechts () oder gar nicht (). In und hält sie.
Konfiguration und Rechenschritt
Eine Konfiguration hält Bandinhalt, Zustand und Kopfposition fest. Man schreibt sie als mit , : Auf dem Band steht (sonst nur Blanks), der Zustand ist , der Kopf steht auf dem ersten Zeichen von . Steht er auf einem Blank rechts von , schreibt man .
Die Startkonfiguration bei Eingabe ist . Geht durch einmaliges Anwenden von aus hervor, schreibt man (ein Rechenschritt). heißt: in null oder mehr Schritten. Beispiel: Ist , so gilt .
Bei Eingabe gibt es drei Möglichkeiten:
- akzeptiert , wenn für irgendwelche .
- verwirft , wenn .
- hält nicht auf , wenn sie keinen der beiden Haltezustände je erreicht. Die Rechnung läuft dann unendlich lange.
Die von erkannte Sprache ist .
Die Idee für
Die Idee für
Gesucht ist eine TM mit , die auf jedem Wort hält. Die Idee ist das Abhaken von Hand:
- Ersetze das linkeste noch unmarkierte durch .
- Laufe nach rechts zum ersten noch unmarkierten und ersetze es durch . Gibt es keins, verwirf.
- Laufe zurück bis zum und beginne rechts davon die nächste Runde.
- Steht rechts vom letzten kein mehr, sondern ein , prüfe, dass bis zum Ende nur noch kommen. Dann akzeptiere, sonst verwirf.
Bandalphabet ; Zustände (nächstes ), (nach rechts zum ), (zurück zum ), (Rest prüfen), , .
Bei Eingabe steht nach Runden auf dem Band. Eine solche Aussage, die jede Runde erhält, heißt Invariante; mit Induktion über folgt, dass nach Runden dasteht und die Maschine akzeptiert.
Übergangstabelle
Übergangstabelle
Jede Zeile ist ein Wert .
| Zustand | gelesen | neuer Zustand | geschrieben | Bewegung | Bedeutung |
|---|---|---|---|---|---|
| linkestes abhaken | |||||
| alle abgehakt, Rest prüfen | |||||
| leeres Wort | |||||
| über nach rechts | |||||
| über nach rechts | |||||
| erstes abhaken | |||||
| zurück | |||||
| zurück | |||||
| rechts vom letzten weiter | |||||
| nur erlaubt | |||||
| Ende erreicht, akzeptieren |
Für alle übrigen Paare (zum Beispiel liest , liest ) gilt : Die Maschine verwirft.
So ist überall definiert, wie verlangt. Ein Wort, das nicht die Form hat, scheitert spätestens in : Bei hakt die Maschine und ab, wechselt nach und liest dort .
Ablaufprotokoll für
Ablaufprotokoll für
Die Spalte "Übergang" nennt das Paar aus Zustand und gelesenem Zeichen, dessen Zeile angewandt wurde.
| Schritt | Konfiguration | Übergang |
|---|---|---|
| 0 | Start | |
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 | ||
| 9 | ||
| 10 | ||
| 11 | ||
| 12 | ||
| 13 |
Nach 13 Schritten hält die Maschine in : wird akzeptiert.
Zum Vergleich : Nach 5 Schritten steht da, die zweite Runde hakt das zweite ab, und läuft bis . Für gibt es keine Zeile, die Maschine verwirft nach 8 Schritten. Für braucht sie genau Schritte, denn jede Runde läuft hin und zurück über etwa Felder.
Die Maschine aus der Tabelle bekommt das Wort . Wie endet der Lauf?
Eine Maschine, die nicht immer hält
Eine Maschine, die nicht immer hält
Sei und die Maschine mit , und .
Bei einem Wort, das mit beginnt, akzeptiert nach einem Schritt. Beim leeren Wort verwirft sie. Bei einem Wort, das mit beginnt, bleibt sie ewig in auf demselben Feld stehen: Sie hält nicht.
Es gilt , dieselbe Sprache wie bei einer Maschine, die bei verwirft. Die Sprache verrät also nicht, ob eine Maschine außerhalb von 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.
Nicht-Halten ist kein Verwerfen
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."
Verwerfen heißt: Die Maschine erreicht und hält. Nicht-Halten ist ein dritter Ausgang. Für 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.
Mehrband-Turingmaschine
Eine -Band-Turingmaschine hat Bänder mit je einem eigenen Kopf. Die Übergangsfunktion liest die Zeichen unter allen Köpfen gleichzeitig und schreibt, bewegt jeden Kopf einzeln:
.
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 : Kopiere jedes auf Band 2, gehe dort zurück an den Anfang der Kopie und hake dann für jedes auf Band 1 ein auf Band 2 ab. Das braucht ungefähr Schritte statt .
Mehrband-Maschinen sind nicht stärker
Zu jeder -Band-Turingmaschine gibt es eine Turingmaschine mit einem Band, die auf jeder Eingabe genau dann akzeptiert, verwirft oder nicht hält, wenn es tut. Insbesondere ist . Macht auf einer Eingabe der Länge genau Schritte, so braucht höchstens Schritte mit einer Konstanten , für also .
Beweisidee: Das eine Band bekommt Spuren, wie die Zeilen einer Tabelle. Spur trägt den Inhalt von Band , Spur eine Marke an der Stelle des Kopfes .
Formal ist ein Feld von ein Tupel: Das neue Bandalphabet enthält (je Band ein Zeichen und eine Marke, heißt "Kopf steht hier") und zusätzlich selbst, damit die Eingabe darauf stehen kann. Das ist eine endliche Menge, also ein erlaubtes Bandalphabet. Ein Feld mit dem gewöhnlichen Blank behandelt wie das Tupel aus lauter Blanks ohne Marken. Zuerst schreibt jedes Eingabezeichen um in das Tupel "Band 1 trägt , alle anderen " und setzt alle Marken auf das erste Feld.
Einen Schritt von simuliert in zwei Durchläufen. Im ersten merkt sie sich die Zeichen unter den Marken in ihrem Zustand; dafür genügen endlich viele Zustände, weil es nur Möglichkeiten gibt. Danach kennt sie den Wert von . Im zweiten Durchlauf schreibt sie an jeder Marke das neue Zeichen und verschiebt die Marke. Erreicht einen Haltezustand, hält im gleichnamigen.
Laufzeit: In Schritten bewegt sich jeder Kopf höchstens Felder, der benutzte Abschnitt ist also höchstens Felder lang. Jeder simulierte Schritt kostet einige Durchläufe darüber, also , alle zusammen , dazu für das Umschreiben der Eingabe.
Nichtdeterministische Turingmaschine
Wie beim NEA darf eine nichtdeterministische Turingmaschine (NTM) in einer Situation mehrere Möglichkeiten haben. Statt eines Tripels liefert eine endliche Menge von Tripeln:
,
wobei die Potenzmenge bezeichnet. Aus einer Konfiguration können also mehrere Folgekonfigurationen hervorgehen. Alle möglichen Rechnungen bilden den Berechnungsbaum. Die NTM akzeptiert , wenn mindestens ein Pfad in 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.
Nichtdeterminismus erkennt keine neuen Sprachen
Zu jeder nichtdeterministischen Turingmaschine gibt es eine deterministische Turingmaschine mit .
Beweisidee: durchsucht den Berechnungsbaum von Ebene für Ebene (Breitensuche) und akzeptiert, sobald sie einen akzeptierenden Pfad findet.
Sei die größte Anzahl von Möglichkeiten, die von in irgendeiner Situation hat; ist endlich, weil und endlich sind. Nummeriere die Möglichkeiten jeder Situation mit . Dann beschreibt jedes Wort über höchstens einen Anfangsabschnitt eines Pfades: Die -te Ziffer sagt, welche Möglichkeit im -ten Schritt gewählt wird (gibt es sie nicht, ist das Wort ungültig).
hat drei Bänder: Band 1 hält die Eingabe fest, Band 2 ist das Arbeitsband für die Simulation, Band 3 enthält das aktuelle Auswahlwort. geht die Auswahlwörter der Länge nach durch (, dann alle der Länge 1, dann alle der Länge 2, ...). Für jedes kopiert sie die Eingabe auf Band 2 und simuliert genau nach den Ziffern. Landet die Simulation in , akzeptiert .
Akzeptiert das Wort , gibt es einen akzeptierenden Pfad endlicher Länge . Sein Auswahlwort hat Länge und kommt nach endlich vielen anderen an die Reihe, also akzeptiert . Akzeptiert nicht, endet keine Simulation in , und akzeptiert nie. Also . Mit dem Satz über Mehrband-Maschinen gibt es dazu auch eine Maschine mit einem Band.
Warum durchsucht im Beweis den Berechnungsbaum ebenenweise und nicht, indem sie einen Pfad bis zum Ende verfolgt (Tiefensuche)?
Zusammenfassung
Eine Turingmaschine ist ein endlicher Automat mit einem unbegrenzten Band zum Lesen und Schreiben.
: im Zustand das Zeichen lesen, schreiben, nach wechseln, den Kopf nach bewegen.
Eine Konfiguration hält Bandinhalt, Zustand und Kopfposition fest; 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
Die Maschine aus der Lektion ist in der Konfiguration . Welche Konfiguration folgt?
Wie viele Rechenschritte macht die Maschine aus der Lektion auf der Eingabe , bis sie in hält?
Eine Maschine addiert zu einer Binärzahl. Startzustand , Haltezustand (akzeptierend):
| Zustand | gelesen | neuer Zustand | geschrieben | Bewegung |
|---|---|---|---|---|
Was steht nach dem Halten auf dem Band, wenn die Eingabe war?
Zeige: Zu jeder Turingmaschine gibt es eine Turingmaschine mit , die niemals verwirft, also auf jedem Wort außerhalb von nicht hält.
Gib eine Turingmaschine mit einem Band an, die genau die Palindrome über akzeptiert (Wörter, die vorwärts und rückwärts gleich gelesen werden, einschließlich ) und auf jedem Wort hält. Schreibe die Übergänge als Tabelle und erkläre die Bedeutung jedes Zustands.
Welche Aussage über eine nichtdeterministische Turingmaschine und die deterministische Maschine aus dem Simulationsbeweis stimmt?