Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Turing-Maschinen
Was kann ein Computer prinzipiell berechnen, und was nicht? Diese Frage beantwortet die Turing-Maschine, das mächtigste und allgemeinste Berechnungsmodell der Informatik. Alan Turing erfand sie 1936, lange vor dem ersten Computer. Klausurpflicht in 8/8 Theo-Inf-Modulen.
Die Idee in einem Satz
Eine Turing-Maschine besteht aus einem unendlichen Band, einem Lese-/Schreibkopf und endlich vielen Zuständen. Sie liest ein Symbol, schreibt eines, bewegt den Kopf und wechselt den Zustand, gesteuert von einer festen Regeltabelle.
Die formale Definition (7-Tupel)
Eine Turing-Maschine ist M = (Q, Σ, Γ, δ, q₀, □, F):
| Symbol | Bedeutung |
|---|---|
| Q | endliche Zustandsmenge |
| Σ | Eingabe-Alphabet |
| Γ (Gamma) | Band-Alphabet (Σ ⊆ Γ, enthält □) |
| δ | Übergangsfunktion δ: Q × Γ → Q × Γ × {L, R, N} |
| q₀ | Startzustand |
| □ | Blank-Symbol (leere Bandzelle) |
| F | akzeptierende Endzustände |
Die Bestandteile
- Band: beidseitig unendlich, in Zellen unterteilt, anfangs mit der Eingabe beschrieben, sonst Blanks.
- Lese-/Schreibkopf: steht über genau einer Zelle, kann lesen und überschreiben.
- Zustände: das endliche „Gehirn“ der Maschine.
Ein Schritt (δ)
Die Übergangsfunktion nimmt (Zustand, gelesenes Symbol) und liefert (neuer Zustand, zu schreibendes Symbol, Bewegung). Bewegung ist L (links), R (rechts) oder N (stehen bleiben). Anders als der endliche Automat kann die TM also schreiben und sich in beide Richtungen bewegen, das macht sie so mächtig.
Konfiguration und Berechnung
- Eine Konfiguration beschreibt den Gesamtzustand: (aktueller Zustand, Bandinhalt, Kopfposition).
- Eine Berechnung ist die Folge von Konfigurationen vom Start bis zum Halt.
Drei mögliche Ausgänge
- Akzeptieren: die TM hält in einem akzeptierenden Zustand.
- Verwerfen: die TM hält in einem nicht-akzeptierenden Zustand.
- Nicht halten: die TM läuft endlos weiter (das ist der entscheidende Unterschied zu Automaten und der Kern des Halteproblems).
Die Church-Turing-These
Alles, was überhaupt „berechenbar“ ist, kann von einer Turing-Maschine berechnet werden.
Das ist keine beweisbare Aussage, sondern eine These (Definition von „berechenbar“). Alle bekannten Rechenmodelle (RAM, While-Programme, Lambda-Kalkül, reale Computer) sind genau so mächtig wie die TM, nicht mächtiger.
TM und die Chomsky-Hierarchie
Turing-Maschinen erkennen die Typ-0-Sprachen (rekursiv aufzählbare Sprachen), die größte Klasse der Chomsky-Hierarchie. Damit stehen sie an der Spitze:
regulär (Typ 3) ⊊ kontextfrei (Typ 2) ⊊ kontextsensitiv (Typ 1) ⊊ rekursiv aufzählbar (Typ 0).
Varianten sind gleich mächtig
Mehrband-TM, TM mit halbseitig unendlichem Band, nichtdeterministische TM: all diese Varianten erkennen DIESELBE Sprachklasse wie die Standard-TM. Sie können höchstens schneller sein, aber nicht mehr berechnen.
Klausur-Faustregeln
1. TM = 7-Tupel (Q, Σ, Γ, δ, q₀, □, F).
2. δ: Q × Γ → Q × Γ × {L, R, N} (Zustand + Symbol → Zustand, schreiben, bewegen).
3. Konfiguration = (Zustand, Band, Kopfposition).
4. Drei Ausgänge: akzeptieren, verwerfen, nicht halten.
5. Church-Turing-These: TM = alles Berechenbare.
6. TM erkennt Typ-0 (rekursiv aufzählbar), oberste Stufe der Hierarchie.
Häufige Stolpersteine
1. Band als endlich annehmen. Das TM-Band ist UNENDLICH (nach Bedarf beliebig erweiterbar), das unterscheidet sie vom endlichen Automaten.
2. „Nicht halten“ vergessen. Eine TM muss nicht halten. Genau das macht das Halteproblem unentscheidbar.
3. Eingabe- und Band-Alphabet verwechseln. Σ ist die Eingabe, Γ ist das Band-Alphabet (enthält zusätzlich das Blank □ und Hilfssymbole). Es gilt Σ ⊆ Γ.
4. TM für „nur ein bisschen stärker“ als Automaten halten. Der Sprung ist riesig: die TM kann beliebig schreiben und sich frei bewegen, sie ist universell (Church-Turing).
5. Church-Turing-These für ein Theorem halten. Sie ist eine (unbeweisbare) These, kein Satz.
6. Mehrband-TM für mächtiger halten. Mehr Bänder = evtl. schneller, aber NICHT mehr berechenbar. Gleiche Sprachklasse.
Interaktiv verstehen
Turing-Maschine, interaktiv
Führe eine Turing-Maschine Schritt für Schritt aus, die eine Binärzahl um 1 erhöht (1011 → 1100). Beobachte, wie der Kopf über das Band läuft, Symbole überschreibt und der Zustand wechselt. Die Übergangstabelle δ zeigt bei jedem Schritt die aktive Regel.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Verfolge die Konfiguration (Zustand, Band, Kopfposition) Schritt für Schritt. In Klausuren musst du oft eine Konfigurationsfolge angeben oder eine kleine TM für eine einfache Aufgabe (Inkrement, Symbol kopieren, Erkenner) selbst konstruieren.
Praxis-Übung
Turing-Maschinen, Praxis-Übung
6 Aufgaben zu Aufbau, Schritten und Ausgängen.
Klausurfragen mit Lösungen (6)
- F1.Was liefert die Übergangsfunktion δ einer Turing-Maschine?
Antwort: Neuer Zustand, zu schreibendes Symbol und Kopfbewegung (L/R/N)
Erklärung: δ: Q × Γ → Q × Γ × {L, R, N}. Aus (aktueller Zustand, gelesenes Symbol) folgt ein Tripel: neuer Zustand, zu schreibendes Symbol, Kopfbewegung (links/rechts/stehen). Das Schreiben und die freie Bewegung machen die TM viel mächtiger als einen endlichen Automaten. Klausur-Pflichtform.
- F2.Wie groß ist das Band einer Turing-Maschine?
Antwort: Unendlich (nach Bedarf erweiterbar)
Erklärung: Das Band ist unendlich (theoretisch beidseitig, nach Bedarf beliebig erweiterbar). Anfangs steht die Eingabe darauf, der Rest sind Blanks (□). Das unbegrenzte Band ist der entscheidende Unterschied zum endlichen Automaten und ermöglicht beliebige Berechnungen. Klausur-Grundlage.
- F3.Ordne die TM-Komponente ihrer Rolle zu.
Zuordnungen:
- Γ (Band-Alphabet) → Symbole auf dem Band, inkl. Blank
- δ → Übergangsfunktion (lesen, schreiben, bewegen)
- □ (Blank) → leere Bandzelle
- Konfiguration → Zustand + Band + Kopfposition
Erklärung: Γ = Band-Alphabet (enthält die Eingabesymbole Σ plus Blank und Hilfssymbole). δ = Übergangsfunktion. □ = Blank (leere Zelle). Konfiguration = Momentaufnahme aus Zustand, Bandinhalt und Kopfposition. Klausur-Pflicht-Zuordnung.
Typ: Zuordnung
- F4.Welche drei Ausgänge kann die Verarbeitung einer Turing-Maschine haben?
Antwort: Akzeptieren, verwerfen, nicht halten
Erklärung: Eine TM kann: akzeptieren (hält in akzeptierendem Zustand), verwerfen (hält in nicht-akzeptierendem Zustand) oder NICHT HALTEN (läuft endlos). Der dritte Fall (Endlosschleife) existiert bei endlichen Automaten nicht und ist der Kern des Halteproblems. Klausur-Pflichtwissen.
- F5.Eine Mehrband-Turing-Maschine kann Sprachen erkennen, die eine Einband-TM nicht erkennen kann.
Antwort: Falsch
Erklärung: FALSCH. Mehrband-TMs, nichtdeterministische TMs und andere Varianten erkennen DIESELBE Sprachklasse wie die Standard-Einband-TM (die rekursiv aufzählbaren Sprachen). Mehr Bänder können die Berechnung beschleunigen, aber nicht mehr berechnen. Klausur-Stolperstein.
Typ: Wahr/Falsch
- F6.Die Inkrement-TM steht im Zustand q1 und liest eine 1. Laut δ schreibt sie 0 und geht nach links. Warum?
Antwort: 1 + 1 = 0 mit Übertrag: die Stelle wird 0, der Übertrag wandert nach links
Erklärung: Beim binären Inkrementieren bedeutet 1 + 1 (Übertrag) = 0 mit Übertrag in die nächste Stelle. Die TM schreibt also 0 und geht nach links, um den Übertrag dort zu verarbeiten. Trifft sie eine 0 (oder Blank), schreibt sie 1 (Übertrag aufgelöst) und hält. Klausur-Nachvollziehen einer TM-Regel.
Klausur-Quiz
Turing-Maschinen, Klausur-Quiz
6 Klausur-Fragen zu Church-Turing, Hierarchie und Varianten.
Klausurfragen mit Lösungen (6)
- F1.Was besagt die Church-Turing-These?
Antwort: Alles intuitiv Berechenbare kann von einer Turing-Maschine berechnet werden
Erklärung: Die Church-Turing-These besagt: alles, was im intuitiven Sinn „berechenbar“ ist, kann von einer Turing-Maschine berechnet werden. Sie ist nicht beweisbar (sie definiert „berechenbar“), wird aber durch die Äquivalenz aller bekannten Rechenmodelle (RAM, Lambda-Kalkül, While-Programme) gestützt. Klausur-Kernthese.
- F2.Welche Sprachklasse der Chomsky-Hierarchie erkennen Turing-Maschinen?
Antwort: Typ 0 (rekursiv aufzählbar)
Erklärung: Turing-Maschinen erkennen die Typ-0-Sprachen (rekursiv aufzählbare Sprachen), die größte und allgemeinste Klasse der Chomsky-Hierarchie. Darunter liegen kontextsensitiv (Typ 1), kontextfrei (Typ 2) und regulär (Typ 3). Klausur-Einordnung.
- F3.Ordne das Maschinenmodell seiner Sprachklasse zu.
Zuordnungen:
- Endlicher Automat → regulär (Typ 3)
- Kellerautomat → kontextfrei (Typ 2)
- Turing-Maschine → rekursiv aufzählbar (Typ 0)
- zusätzliches Gedächtnis der TM → unendliches Band
Erklärung: Endlicher Automat = regulär (kein Zusatzspeicher). Kellerautomat = kontextfrei (Stack). Turing-Maschine = rekursiv aufzählbar (unendliches Band, frei beschreib- und bewegbar). Das unbegrenzte Band ist der Grund für die Mächtigkeit der TM. Klausur-Pflicht-Zuordnung.
Typ: Zuordnung
- F4.Was beschreibt eine Konfiguration einer Turing-Maschine?
Antwort: Den aktuellen Zustand, den Bandinhalt und die Kopfposition
Erklärung: Eine Konfiguration ist die vollständige Momentaufnahme der TM: aktueller Zustand, gesamter Bandinhalt und Position des Kopfes. Die Berechnung ist die Folge von Konfigurationen vom Start bis zum Halt. Klausur-Begriff (oft als Konfigurationsfolge abgefragt).
- F5.Eine Turing-Maschine kann bei manchen Eingaben unendlich lange laufen, ohne je zu halten.
Antwort: Wahr
Erklärung: RICHTIG. Im Gegensatz zu endlichen Automaten (die nach |w| Schritten fertig sind) kann eine TM endlos laufen (Endlosschleife). Genau deshalb ist das Halteproblem (hält M bei Eingabe w?) unentscheidbar, man kann es im Allgemeinen nicht algorithmisch vorhersagen. Klausur-Schlüsselkonzept.
Typ: Wahr/Falsch
- F6.Warum gilt eine nichtdeterministische Turing-Maschine (NTM) als gleich mächtig wie eine deterministische?
Antwort: Weil eine deterministische TM alle Berechnungspfade der NTM nacheinander durchsimulieren kann
Erklärung: Eine deterministische TM kann alle möglichen Berechnungspfade einer NTM systematisch durchprobieren (z.B. per Breitensuche über den Berechnungsbaum). Sie erkennt damit dieselben Sprachen, nur evtl. exponentiell langsamer. Bei der BERECHENBARKEIT sind NTM und DTM gleich mächtig (bei der Komplexität ist die Frage P vs. NP offen). Klausur-Transferfrage.
