Skip to content

7. Turing Maschine

Thema 8: Turing-Maschine & Kontextsensitive Grammatik

🚀 1. Turing-Maschine (TM) – Grundlagen

📌 Definition:

Eine Turing-Maschine (TM) ist ein abstraktes Berechnungsmodell, das über eine unendliche Bandstruktur arbeitet und zur Definition der Berechenbarkeit genutzt wird.

🛠️ Bestandteile:

  • Band (∞ in beide Richtungen): Unendlich lang, speichert Eingabe und Zwischenzustände.

  • Lese-/Schreibkopf: Kann Zeichen lesen, überschreiben und sich bewegen (L = Links, R = Rechts).

  • Zustandsmenge **Q**: Menge von Zuständen inklusive eines Startzustands **q_0** und eines Haltezustands **q_h**.

  • Übergangsfunktion δ: Bestimmt für jede Kombination von aktuellem Zustand und gelesenem Zeichen die neue Bandbeschriftung, Bewegung, und den Folgezustand.

Formal:

  • Σ = Eingabealphabet (ohne das Blank-Zeichen ⊔),

  • Γ = Bandalphabet (inklusive ⊔),

  • δ = Übergangsfunktion: Q × Γ → Q × Γ × {L, R}.

📊 2. Arbeitsweise einer TM

  1. Start: TM beginnt im Startzustand **q_0** und liest das erste Zeichen auf dem Band.

  2. Übergangsfunktion **δ** wendet Regeln an:

    • Bandinhalt ändern (Überschreiben eines Symbols).

    • Kopf bewegen (nach Links oder Rechts).

    • Neuen Zustand annehmen (wechseln in Q).

  3. Haltbedingung: TM stoppt, wenn sie in q_h übergeht oder keine gültigen Übergänge mehr existieren.

🔄 3. Beispiel einer einfachen TM für L = { aⁿbⁿ | n ≥ 1 }

Übergangsregeln:

# = leer N = Lesekopf Neutral Richtung L, R = Lesekopf Links, Rechts Richtung a(#,N) = 1. Element zu lesend, 2. Element ersetzen mit, 3. Element Lesekopf Richtung

turing_machine.svg

🔗 4. Zusammenhang zur Chomsky-Hierarchie

  • Reguläre Sprachen (Typ-3) → Endliche Automaten (DFA, NFA)

  • Kontextfreie Sprachen (Typ-2) → Kellerautomaten (PDA)

  • Kontextsensitive Sprachen (Typ-1) → Linear beschränkte TM

  • Rekursiv aufzählbare Sprachen (Typ-0) → Turing-Maschinen (volle Berechenbarkeit)

➡️ Turing-Maschinen sind mächtiger als alle anderen Modelle, da sie jede berechenbare Funktion simulieren können.

📝 5. Typische Prüfungsaufgaben

  1. Konstruieren einer TM für eine gegebene Sprache (z. B. Palindrome oder einfache arithmetische Operationen).

  2. Entscheidbarkeit von Problemen analysieren (z. B. Halteproblem ist nicht entscheidbar).

  3. Übergangsfunktion einer TM angeben und simulieren.

Falls du ein Beispiel detaillierter durchgehen möchtest, sag einfach Bescheid! 😊🚀