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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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.
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.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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.
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.
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 Ü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.
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.
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).
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.
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.
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.
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.
6 Aufgaben zu Aufbau, Schritten und Ausgängen.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
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.
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
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.
6 Klausur-Fragen zu Church-Turing, Hierarchie und Varianten.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
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).
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
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.