Turingmaschine

Das mächtigste Automatenmodell: ein endlicher Automat mit unbeschränktem Arbeitsband, auf dem er lesen, schreiben und sich frei bewegen kann. Es präzisiert, was „berechenbar“ bedeutet, und ist das theoretische Modell jedes Computers.

Aufbau

TA = (Σ, S, Γ, δ, s₀, #, F) mit Eingabealphabet Σ, Zuständen S, Arbeitsalphabet Γ ⊇ Σ, Überführung δ, Startzustand s₀, Blanksymbol # und Endzuständen F (Quelle - Automatentheorie Zusammenfassung).

• Das Eingabeband dient zugleich als Arbeitsspeicher. Der Schreib-/Lesekopf kann jede Zelle erreichen, ohne den Inhalt zu zerstören (quasi wahlfreier Zugriff). Das ist der Unterschied zum Keller.
• Pro Schritt: Symbol lesen → Zustand wechseln, Symbol schreiben, Kopf nach links oder rechts bewegen.
• Beispiele der Quelle (S. 36–38, jeweils mit vollständiger Übergangsfunktion):
  • aⁿbⁿcⁿ: Der Kopf läuft nach rechts und ersetzt pro Durchgang je ein a, b und c durch A, B, C. Dann kehrt er an den Bandanfang zurück. Sind am Ende alle Buchstaben ersetzt und in richtiger Reihenfolge, wird der Endzustand erreicht.
  • {wcw | w ∈ {a,b}*} (TA₁): vergleicht symbolweise w₁ vor dem c mit w₂ dahinter. Verglichene Symbole werden durch | gestrichen. Endzustand nur, wenn beide komplett gestrichen sind.
  • {ww} (TA₂): Hier fehlt das Trennsymbol. TA₂ rät nichtdeterministisch die Mitte, fügt dort ein c ein (der Rest wird eine Position nach rechts geschoben) und läuft dann TA₁. Rät er falsch, gibt es keine akzeptierende Rechnung (Backtracking). Ein schönes Beispiel dafür, wie Nichtdeterminismus „Raten“ modelliert.
  • Beide Sprachen sind nicht kontextfrei.

Robustheit des Modells

Die folgenden Erweiterungen ändern die Mächtigkeit nicht (Quelle - Automatentheorie Zusammenfassung):

• beidseitig unendliches Band statt einseitig begrenztem
• mehrere Köpfe, mehrere oder mehrdimensionale Bänder
• Nichtdeterminismus: NTM lassen sich in deterministische TM umwandeln, aber mit exponentiellem Zeitaufwand → Komplexitätstheorie
• Ein Kellerautomat mit zwei Kellern kann jede Turingmaschine simulieren.

Turingmaschinen akzeptieren genau die Typ-0-Sprachen. Die Variante mit auf die Eingabelänge beschränktem Band (LBA) akzeptiert genau Typ 1 → Chomsky-Hierarchie.

Universelle Turingmaschine (UTM)

Eine UTM erhält die Codierung einer beliebigen Turingmaschine plus deren Eingabe und simuliert sie, auch sich selbst. Sie ist das theoretische Fundament des programmierbaren Universalrechners: Das Programm ist Teil der Daten. Die Codierung als Wörter liefert zugleich eine Abzählung aller Turingmaschinen. Das ist die Grundlage für Unentscheidbarkeitsbeweise → Berechenbarkeit.

Turing-Berechenbarkeit

Eine Funktion ist Turing-berechenbar, wenn eine Turingmaschine sie berechnet. Zahlen werden dafür codiert, z.B. in Strichnotation: (3, 2, 5) → |||0||0|||||. Das formalisiert das Rechnen „mit Bleistift und Papier“ (Quelle - Automatentheorie Zusammenfassung).

Verwandt

• Berechenbarkeit – was Turingmaschinen können und was nicht
• Chomsky-Hierarchie – Typ 0 und LBA
• Komplexitätstheorie – Zeitbedarf deterministischer und nichtdeterministischer TM
• Endlicher Automat – der Kern jeder Turingmaschine
• Kellerautomat – schwächeres Modell mit Stack statt Band