Das universelle Berechnungsmodell — endliche Steuerung, unendliches Band, formale Grundlage der Berechenbarkeit.
Klausur-Relevanz: sehr hoch — Lesen UND RechnenTL;DR
- Eine Turingmaschine (TM) ist ein 7-Tupel $$M = (Z, \Sigma, \Gamma, \delta, z_0, \square, E)$$ mit endlicher Zustandsmenge, Eingabealphabet, Bandalphabet, Übergangsfunktion, Startzustand, Blank-Symbol und Endzuständen.
- Die Übergangsfunktion einer deterministischen TM hat die Signatur $\delta: Z \times \Gamma \to Z \times \Gamma \times \{L, R, N\}$: lies Symbol, schreibe Symbol, bewege den Kopf.
- Eine Konfiguration beschreibt den kompletten Systemzustand als $\alpha z \beta$ — linkes Bandsegment, aktueller Zustand, rechtes Bandsegment mit Kopf auf dem ersten Zeichen von $\beta$.
- Akzeptiert wird durch Erreichen eines Endzustands (oder alternativ durch Halten). Die Sprache $L(M)$ ist genau die Menge akzeptierter Wörter — Turing-erkennbare Sprachen heißen rekursiv aufzählbar.
- Mehrband- und nichtdeterministische TM sind ausdrucksstark äquivalent zur DTM. Das Halteproblem ist unentscheidbar — die harte Grenze der Berechenbarkeit.
- Diese Seite enthält jetzt auch durchgerechnete Rechenaufgaben. Nutze sie im Klausur-Modus: erst selbst probieren, dann Lösung aufklappen.
1. Definitionen & Formalismen
Deterministische Turingmaschine (DTM)
Eine DTM ist ein 7-Tupel $$M = (Z, \Sigma, \Gamma, \delta, z_0, \square, E)$$ mit:
- $Z$ — endliche, nicht-leere Zustandsmenge
- $\Sigma$ — endliches Eingabealphabet
- $\Gamma$ — endliches Bandalphabet mit $\Sigma \subseteq \Gamma$
- $\square \in \Gamma \setminus \Sigma$ — Blank-Symbol, füllt die unbeschriebenen Bandzellen
- $z_0 \in Z$ — Startzustand
- $E \subseteq Z$ — Menge der Endzustände
- $\delta: Z \times \Gamma \to Z \times \Gamma \times \{L, R, N\}$ — partielle Übergangsfunktion
Konfiguration
Eine Konfiguration ist ein Wort $k = \alpha z \beta$ mit $\alpha, \beta \in \Gamma^*$ und $z \in Z$. Interpretation: links vom Kopf steht $\alpha$, die Steuerung ist im Zustand $z$, rechts vom Kopf beginnt $\beta$ und der Kopf liest das erste Zeichen von $\beta$. Ist $\beta$ leer, wird ein $\square$ gelesen.
Die Startkonfiguration zu einer Eingabe $w \in \Sigma^*$ ist $z_0 w$.
Konfigurationsübergang $\vdash$
Aus $\delta(z, a) = (z', b, X)$ ergibt sich der Ein-Schritt-Übergang $k \vdash k'$. Für die Bewegung $X$ gilt: bei $R$ rückt der Kopf um eins nach rechts, bei $L$ nach links, bei $N$ bleibt er stehen. Formal, mit $\alpha = \alpha' c$:
- $\alpha' c \, z \, a \beta \vdash \alpha' c b \, z' \, \beta$ falls $X = N$ (Notation vereinfacht)
- bei $X = R$ wandert der Kopf über das geschriebene $b$ hinaus nach rechts
- $\alpha' c \, z \, a \beta \vdash \alpha' \, z' \, c b \beta$ falls $X = L$
Die Relation $\vdash^*$ ist die reflexiv-transitive Hülle: beliebig viele Schritte, einschließlich null.
Akzeptierte Sprache
$$L(M) = \{ w \in \Sigma^* \mid z_0 w \vdash^* \alpha z \beta \text{ mit } z \in E \}$$ Ein Wort wird akzeptiert, wenn die Berechnung irgendwann in einen Endzustand gelangt. Für Wörter außerhalb von $L(M)$ darf die TM auch endlos laufen — sie muss nicht ablehnen, sie muss nur nicht akzeptieren.
Turing-berechenbar / rekursiv aufzählbar
Eine Sprache $L$ heißt rekursiv aufzählbar (r.e., Typ 0), wenn es eine TM $M$ gibt mit $L = L(M)$. Sie heißt rekursiv (entscheidbar), wenn zusätzlich $M$ auf jeder Eingabe hält. Eine Funktion $f: \Sigma^* \to \Sigma^*$ heißt turing-berechenbar, wenn eine TM sie realisiert, indem sie auf Eingabe $w$ hält und $f(w)$ auf dem Band hinterlässt.
Church-Turing-These
Die intuitive Vorstellung von algorithmisch berechenbar stimmt genau mit dem Begriff turing-berechenbar überein. Diese These ist kein Satz — sie ist eine mathematisch nicht beweisbare Übereinkunft, gestützt durch die Äquivalenz aller bislang vorgeschlagenen Berechnungsmodelle ($\lambda$-Kalkül, $\mu$-rekursive Funktionen, WHILE-Programme, Registermaschinen).
Varianten mit gleicher Ausdrucksstärke
Mehrband-TM: $k$ Bänder, $k$ Köpfe, $\delta: Z \times \Gamma^k \to Z \times \Gamma^k \times \{L, R, N\}^k$. Simuliert eine DTM mit polynomiellem Overhead. Nichtdeterministische TM (NTM): $\delta$ liefert eine Teilmenge möglicher Nachfolger. Sie akzeptiert, wenn mindestens ein Berechnungspfad in einem Endzustand endet. Beide Varianten erkennen genau die Klasse der rekursiv aufzählbaren Sprachen — nicht mehr, nicht weniger.
2. Kernkonzepte & Vorgehen
Beim Umgang mit einer TM in der Klausur bewegt man sich fast immer auf einer von zwei Ebenen: Konfigurationsfolge nachvollziehen oder Sprache klassifizieren. Für beides braucht es Disziplin.
- Tupel identifizieren. Vor jeder Analyse: welche Elemente sind $\Sigma$, welche gehören zu $\Gamma \setminus \Sigma$ (also Hilfssymbole)? Wo endet die Eingabe, wo beginnt das Blank? Ohne diese Trennung liest man Bandinhalte falsch.
- Startkonfiguration hinschreiben. Immer $z_0 w$, wobei der Kopf über dem ersten Zeichen von $w$ steht. Ist die Eingabe leer, ist es $z_0 \square$.
- Übergang für Übergang. Jeder Schritt wird durch eine Anwendung von $\delta$ auf das aktuell gelesene Symbol im aktuellen Zustand bestimmt. Kopfbewegung ist der letzte Effekt eines Schritts, nicht der erste.
- Bandränder ehrlich behandeln. Läuft der Kopf über das bisher beschriebene Band hinaus, liest er $\square$. Vergisst man das, endet die Berechnung fälschlich in einem undefinierten $\delta$-Eintrag.
- Halten vs. Akzeptieren unterscheiden. Halten heißt: $\delta$ ist im aktuellen Konfigurationspaar undefiniert. Akzeptieren heißt: die Konfiguration enthält einen Zustand aus $E$. Beides kann getrennt auftreten (halten ohne akzeptieren = ablehnen).
- Sprache benennen. Beim Klassifizieren nicht raten. Beschreibe zuerst, was auf einer akzeptierenden Berechnung wirklich passiert: Wird gezählt? Vergleicht die Maschine Präfixe? Erst dann formuliere $L(M)$.
3. Beispiel durchgerechnet
Beispiel: TM für $L = \{ a^n b^n \mid n \geq 1 \}$
Idee: Streiche abwechselnd das linkeste $a$ und das linkeste $b$, indem sie durch Hilfssymbole $X$ und $Y$ ersetzt werden. Akzeptiere, wenn nur noch $X$ und $Y$ auf dem Band stehen.
Gegeben: $Z = \{z_0, z_1, z_2, z_3, z_e\}$, $\Sigma = \{a, b\}$, $\Gamma = \{a, b, X, Y, \square\}$, $E = \{z_e\}$.
| Zustand | gelesen | → neuer Zustand | schreibt | bewegt |
|---|---|---|---|---|
| $z_0$ | $a$ | $z_1$ | $X$ | R |
| $z_0$ | $Y$ | $z_3$ | $Y$ | R |
| $z_1$ | $a$ | $z_1$ | $a$ | R |
| $z_1$ | $Y$ | $z_1$ | $Y$ | R |
| $z_1$ | $b$ | $z_2$ | $Y$ | L |
| $z_2$ | $a$ | $z_2$ | $a$ | L |
| $z_2$ | $Y$ | $z_2$ | $Y$ | L |
| $z_2$ | $X$ | $z_0$ | $X$ | R |
| $z_3$ | $Y$ | $z_3$ | $Y$ | R |
| $z_3$ | $\square$ | $z_e$ | $\square$ | N |
Konfigurationsfolge auf Eingabe $w = aabb$ (Kopfposition durch Zustand vor dem gelesenen Symbol):
z_0 a a b b Start: z_0 liest a X z_1 a b b δ(z_0,a) = (z_1,X,R) X a z_1 b b δ(z_1,a) = (z_1,a,R) X a z_2 Y b δ(z_1,b) = (z_2,Y,L); Kopf steht jetzt auf a X z_2 a Y b δ(z_2,a) = (z_2,a,L) z_2 X a Y b δ(z_2,a) = (z_2,a,L); Kopf auf X X z_0 a Y b δ(z_2,X) = (z_0,X,R) X X z_1 Y b δ(z_0,a) = (z_1,X,R) X X Y z_1 b δ(z_1,Y) = (z_1,Y,R) X X z_2 Y Y δ(z_1,b) = (z_2,Y,L) X z_2 X Y Y δ(z_2,Y) = (z_2,Y,L) X X z_0 Y Y δ(z_2,X) = (z_0,X,R) X X Y z_3 Y δ(z_0,Y) = (z_3,Y,R) X X Y Y z_3 □ δ(z_3,Y) = (z_3,Y,R) X X Y Y z_e □ δ(z_3,□) = (z_e,□,N) → akzeptiert
Beobachtung: pro Durchlauf verschwindet genau ein $a$ und ein $b$. Ungleich lange Blöcke führen dazu, dass entweder $z_1$ ein $\square$ liest oder $z_0$ ein $b$ liest — beides ist undefiniert und die Maschine hält ohne zu akzeptieren.
Rechenaufgaben mit Lösung
Trainiere hier den Klausur-Modus: Aufgabe lesen, selbst probieren, dann Lösung aufklappen.
Gegeben ist die DTM $M = (\{z_0, z_1, z_e\}, \{a\}, \{a, \square\}, \delta, z_0, \square, \{z_e\})$ mit
$$\delta(z_0, a) = (z_0, a, R), \quad \delta(z_0, \square) = (z_e, \square, N).$$
Führe auf Eingabe $aaa$ die vollständige Konfigurationsfolge in $\alpha z \beta$-Notation aus und begründe, ob $M$ das Wort akzeptiert.
Lösung anzeigen
Idee: $M$ läuft vom Startzustand $z_0$ so lange nach rechts, wie sie ein $a$ sieht, und wechselt beim ersten $\square$ hinter der Eingabe in den Endzustand $z_e$. Die Maschine akzeptiert also jedes Wort aus $a^*$ (ausgenommen der Fall, dass $\delta(z_0,a)$ irgendwo scheitern würde — tut es hier nicht).
| Schritt | Konfiguration $\alpha z \beta$ | Angewandte Regel |
|---|---|---|
| 0 | $z_0\, a\, a\, a$ | Startkonfiguration |
| 1 | $a\, z_0\, a\, a$ | $\delta(z_0, a) = (z_0, a, R)$ |
| 2 | $a\, a\, z_0\, a$ | $\delta(z_0, a) = (z_0, a, R)$ |
| 3 | $a\, a\, a\, z_0\, \square$ | $\delta(z_0, a) = (z_0, a, R)$ |
| 4 | $a\, a\, a\, z_e\, \square$ | $\delta(z_0, \square) = (z_e, \square, N)$ |
Konstruiere eine DTM $M$, die auf Eingabe $w \in \{a, b\}^*$ jedes Vorkommen von $a$ durch $\square$ ersetzt. Nach Halten soll auf dem Band nur noch das Wort ohne $a$'s stehen.
Gib das 7-Tupel und die vollständige $\delta$-Tabelle an und führe die Berechnung auf Eingabe $aba$ als Konfigurationsfolge durch.
Lösung anzeigen
Übergangsfunktion:
| Zustand | gelesen | $\to$ neuer Zustand | schreibt | bewegt |
|---|---|---|---|---|
| $z_0$ | $a$ | $z_0$ | $\square$ | R |
| $z_0$ | $b$ | $z_0$ | $b$ | R |
| $z_0$ | $\square$ | $z_e$ | $\square$ | N |
Konfigurationsfolge auf Eingabe $aba$:
| Schritt | Konfiguration | Angewandte Regel |
|---|---|---|
| 0 | $z_0\, a\, b\, a$ | Start |
| 1 | $\square\, z_0\, b\, a$ | $\delta(z_0, a) = (z_0, \square, R)$ |
| 2 | $\square\, b\, z_0\, a$ | $\delta(z_0, b) = (z_0, b, R)$ |
| 3 | $\square\, b\, \square\, z_0\, \square$ | $\delta(z_0, a) = (z_0, \square, R)$ |
| 4 | $\square\, b\, \square\, z_e\, \square$ | $\delta(z_0, \square) = (z_e, \square, N)$ |
Skizziere eine DTM für die Sprache $L = \{ a^n b^n c^n \mid n \geq 1 \}$. Beschreibe die Zustandsphasen so genau, dass die Klausur-Argumentation vollständig ist (eine explizite $\delta$-Tabelle ist nicht nötig). Erkläre außerdem, warum ein Kellerautomat (PDA) diese Sprache nicht erkennen kann.
Lösung anzeigen
Phasen einer Runde:
- Phase 1 — linkestes $a$ markieren. Startzustand $z_0$ liest von links, findet das erste $a$ und ersetzt es durch $A$. Wechsel in $z_1$, Kopf nach rechts.
- Phase 2 — über restliche $a$'s laufen. $z_1$ überliest alle weiteren $a$'s (und ggf. bereits markierte $B$'s) bis zum ersten $b$.
- Phase 3 — linkestes $b$ markieren. Das erste $b$ wird zu $B$ ersetzt. Wechsel in $z_2$, Kopf nach rechts.
- Phase 4 — über restliche $b$'s laufen. $z_2$ überliest alle weiteren $b$'s (und ggf. $C$'s) bis zum ersten $c$.
- Phase 5 — linkestes $c$ markieren. Das erste $c$ wird zu $C$ ersetzt. Wechsel in $z_3$.
- Phase 6 — Rücklauf. $z_3$ läuft nach links über alle Zeichen bis zum letzten $A$ zurück. Rechts davon beginnt die nächste $a$-Position: zurück in $z_0$, Runde wiederholen.
- Phase 7 — Endprüfung. Trifft $z_0$ statt auf $a$ auf $B$ (kein $a$ mehr da), muss die Struktur $A^n B^n C^n \square$ vorliegen. Ein Prüfzustand $z_4$ läuft nach rechts, akzeptiert nur bei Muster $B^* C^* \square$ und geht in den Endzustand $z_e$.
Skizziere eine DTM, die eine Binärzahl auf dem Band um $1$ erhöht. Zum Beispiel: aus $1011$ (dezimal $11$) soll $1100$ (dezimal $12$) werden. Beschreibe die drei Phasen und führe eine konkrete Konfigurationsfolge auf Eingabe $10$ (dezimal $2$, Ziel $11$ = dezimal $3$) durch.
Lösung anzeigen
- Phase 1 — an den rechten Rand fahren. Startzustand $z_0$ läuft nach rechts über alle $0$'s und $1$'s, bis er das erste $\square$ hinter der Zahl erreicht. Wechsel in $z_1$, Kopf um eins nach links (auf das niederwertigste Bit).
- Phase 2 — Inkrement mit Übertrag. $z_1$ verarbeitet Bits von rechts nach links: solange eine $1$ gelesen wird, ersetzt sie durch $0$ (Übertrag weiter propagieren) und bewegt sich nach links. Sobald eine $0$ gelesen wird, wird sie durch $1$ ersetzt (Übertrag aufgesogen) und die Maschine wechselt in den Haltezustand $z_e$.
- Phase 3 — Sonderfall Überlauf. Wenn $z_1$ ganz nach links läuft, ohne je eine $0$ zu treffen (Eingabe war $111\dots1$), liest sie ein $\square$. Dann schreibt sie an dieser Stelle ein $1$ (neues höchstwertiges Bit) und wechselt in $z_e$. Beispiel: $111 + 1 = 1000$.
Übergangsfunktion (Skizze):
| Zustand | gelesen | $\to$ neuer Zustand | schreibt | bewegt |
|---|---|---|---|---|
| $z_0$ | $0$ | $z_0$ | $0$ | R |
| $z_0$ | $1$ | $z_0$ | $1$ | R |
| $z_0$ | $\square$ | $z_1$ | $\square$ | L |
| $z_1$ | $0$ | $z_e$ | $1$ | N |
| $z_1$ | $1$ | $z_1$ | $0$ | L |
| $z_1$ | $\square$ | $z_e$ | $1$ | N |
Konfigurationsfolge auf Eingabe $10$ (Ziel $11$):
| Schritt | Konfiguration | Angewandte Regel |
|---|---|---|
| 0 | $z_0\, 1\, 0$ | Start |
| 1 | $1\, z_0\, 0$ | $\delta(z_0, 1) = (z_0, 1, R)$ |
| 2 | $1\, 0\, z_0\, \square$ | $\delta(z_0, 0) = (z_0, 0, R)$ |
| 3 | $1\, z_1\, 0\, \square$ | $\delta(z_0, \square) = (z_1, \square, L)$ |
| 4 | $1\, z_e\, 1\, \square$ | $\delta(z_1, 0) = (z_e, 1, N)$ |
4. Typische Klausurfragen (Lesen!)
Konfigurationsfolge nachvollziehen
Gegeben eine Übergangstabelle und ein Wort — schreibe die vollständige Konfigurationsfolge auf. Was wird gelesen? Immer nur das eine Symbol unter dem Kopf. Wo ist die Falle? Bandende: sobald der Kopf rechts oder links über den beschriebenen Bereich hinausläuft, liest er ein Blank. Man muss dann prüfen, ob $\delta$ auf $(z, \square)$ definiert ist.
Sprache einer gegebenen TM bestimmen
Man liest die Übergangstabelle wie einen Ablaufplan: welche Symbole werden markiert, in welcher Reihenfolge, unter welcher Bedingung wird der Endzustand erreicht? Häufige Falle: eine Nebenschleife übersehen, in der die Maschine auch für ungültige Wörter hängen bleibt statt ablehnend zu halten.
Zwei Sprachklassen unterscheiden
Beispielaufgabe: ist $L$ rekursiv oder nur rekursiv aufzählbar? Argumentiere über Halten: kannst du eine TM angeben, die auf jeder Eingabe hält? Wenn ja, ist $L$ entscheidbar. Wenn nicht, versuche eine Reduktion vom Halteproblem — findest du eine, ist $L$ nicht entscheidbar.
Beweisidee bewerten
Ein Beweisskizzentext ist gegeben; Aufgabe: welche Zeile ist der eigentliche Widerspruchsschritt? Genau lesen — Annahme, Konstruktion, Widerspruch, Fazit müssen sauber trennbar sein.
5. Halteproblem — Ausblick
Das Halteproblem $H = \{ \langle M, w \rangle \mid M \text{ hält auf } w \}$ ist rekursiv aufzählbar, aber nicht entscheidbar. Kurzskizze des klassischen Widerspruchsbeweises:
- Vorannahme. Es gäbe eine TM $H^*$, die für jedes Paar $\langle M, w \rangle$ entscheidet, ob $M$ auf $w$ hält.
- Konstruktion. Baue eine TM $D$, die auf Eingabe $\langle M \rangle$ intern $H^*(\langle M, \langle M \rangle \rangle)$ aufruft: hält $M$ auf sich selbst, dann geht $D$ in eine Endlosschleife; hält $M$ nicht, dann akzeptiert $D$.
- Widerspruch. Wende $D$ auf sich selbst an. $D$ hält auf $\langle D \rangle$ genau dann, wenn $D$ auf $\langle D \rangle$ nicht hält.
- Fazit. $H^*$ kann nicht existieren. Das Halteproblem ist unentscheidbar.
In der Klausur reicht diese informelle Struktur — Annahme, Diagonalisierung, Widerspruch, Fazit — solange die Rollen von $M$, $w$ und der Selbstanwendung sauber benannt sind.
6. Fragen zum Selbsttest
Aus wie vielen Komponenten besteht das Tupel einer DTM und was leistet jede?
Sieben: $Z, \Sigma, \Gamma, \delta, z_0, \square, E$. $Z$ ist die endliche Steuerung; $\Sigma$ das Eingabealphabet; $\Gamma$ das Bandalphabet, das $\Sigma$ und das Blank enthält; $\delta$ die Übergangsfunktion; $z_0$ der Startzustand; $\square$ das ausgezeichnete Leersymbol; $E$ die Endzustände. Ohne jede dieser Komponenten ist die Maschine nicht vollständig spezifiziert — Klausurantworten, die z. B. das Blank vergessen, sind formell falsch.
Warum verlangt man $\Sigma \subseteq \Gamma$ und $\square \notin \Sigma$?
Die Eingabe steht am Anfang zusammenhängend auf dem Band — sie muss also mit Bandsymbolen darstellbar sein, folglich $\Sigma \subseteq \Gamma$. Das Blank markiert unbeschriebene Zellen und darf nicht mit einem Eingabezeichen kollidieren, sonst könnte die Maschine das Ende der Eingabe nicht erkennen. Deshalb ist $\square$ per Definition kein Eingabezeichen.
Was bedeutet die Konfiguration $aa\, z_1\, bb$ konkret?
Auf dem Band steht (ohne Blanks) $aabb$. Die Steuerung ist im Zustand $z_1$. Der Kopf steht auf dem ersten Zeichen von $\beta$ — also auf dem ersten $b$. Alles links von diesem $b$ (also $aa$) ist schon gelesen und bewegt, alles rechts (das zweite $b$ und danach Blanks) noch nicht.
Wo liegt der Unterschied zwischen halten und akzeptieren?
Halten heißt technisch, dass $\delta$ im aktuellen Paar (Zustand, gelesenes Symbol) nicht definiert ist — die Maschine kommt zum Stillstand. Akzeptieren heißt, dass der aktuelle Zustand in $E$ liegt. Beides ist unabhängig: die Maschine kann in einem Endzustand halten (Akzeptanz), in einem Nicht-Endzustand halten (Ablehnung) oder gar nicht halten (dann liegt das Wort nicht in $L(M)$).
Warum ist eine nichtdeterministische TM nicht mächtiger als eine deterministische?
Weil man jede NTM durch eine DTM simulieren kann — etwa mit Breitensuche über alle Berechnungsbäume. Die DTM zählt Konfigurationen systematisch auf und prüft jede. Dadurch erkennt sie genau dieselbe Sprache. Der Preis ist ein möglicher exponentieller Zeit-Overhead — die Sprachklasse bleibt aber die rekursiv aufzählbaren Sprachen.
Was ist der Unterschied zwischen rekursiv und rekursiv aufzählbar?
Rekursiv aufzählbar: es gibt eine TM, die genau die Wörter der Sprache akzeptiert. Auf Wörtern außerhalb der Sprache darf sie endlos laufen. Rekursiv (entscheidbar): zusätzlich hält die TM auf jeder Eingabe und gibt akzeptierend oder ablehnend Bescheid. Jede rekursive Sprache ist auch rekursiv aufzählbar; die Umkehrung gilt nicht — das Halteproblem ist das Standardbeispiel.
Wie liest man die Sprache $L(M)$ aus einer gegebenen Übergangstabelle ab?
Erst die Rolle jedes Zustands identifizieren: Wird gerade nach links gelaufen? Wird ein Symbol markiert? Dann verfolge, unter welcher Bedingung ein Endzustand erreicht wird. Beschreibe in Worten, welche strukturellen Eigenschaften ein Wort haben muss, damit die Berechnung genau dort landet — daraus formuliere die Menge. Nur an einer Beispieleingabe hangeln reicht in der Klausur meist nicht, weil man dabei Sonderfälle übersieht.
Was besagt die Church-Turing-These, und ist sie ein Satz?
Sie besagt: alles, was intuitiv algorithmisch berechenbar ist, ist auch turing-berechenbar. Das ist keine mathematische Aussage über zwei formale Begriffe, sondern eine Behauptung über den informellen Begriff Algorithmus. Deshalb ist sie prinzipiell nicht beweisbar, wird aber breit akzeptiert, weil alle bislang vorgeschlagenen Berechnungsmodelle exakt dieselbe Klasse erfassen.
Skizziere die Beweisidee, dass das Halteproblem unentscheidbar ist.
Annahme: es gibt eine TM $H^*$, die für jedes $\langle M, w \rangle$ korrekt entscheidet, ob $M$ auf $w$ hält. Konstruiere eine TM $D$, die auf Eingabe $\langle M \rangle$ intern $H^*$ auf $\langle M, \langle M \rangle \rangle$ befragt und dann genau das Gegenteil tut (hält, wenn $M$ auf sich nicht hält; läuft ewig, wenn $M$ auf sich hält). Wende $D$ auf sich selbst an — $D$ hält auf $\langle D \rangle$ genau dann, wenn $D$ auf $\langle D \rangle$ nicht hält. Widerspruch, also existiert $H^*$ nicht.
Ist eine Mehrband-TM mächtiger als eine Einband-TM?
Nein, nur bequemer und potenziell schneller. Jede $k$-Band-TM kann durch eine Einband-TM simuliert werden, indem man die $k$ Bandinhalte auf einem Band mit erweitertem Alphabet interleavt darstellt und Kopfpositionen markiert. Die erkennbare Sprachklasse bleibt identisch (rekursiv aufzählbar). Der Zeit-Overhead ist meist polynomial, oft quadratisch.
7. Dos & Donts in der Klausur
Dos
- Konfigurationsfolge Schritt für Schritt aufschreiben — auch wenn zehn Zeilen entstehen.
- Vor jedem Übergang das gelesene Symbol laut aufsagen (mental) — verhindert Verwechslungen zwischen Kopfposition und Nachbarzelle.
- Bandende immer als $\square$ behandeln, nicht als undefiniert.
- Endzustandsmenge $E$ explizit prüfen, bevor du akzeptierst.
- Beim Halteproblem-Beweis: Annahme, Konstruktion, Widerspruch, Fazit sauber trennen.
Donts
- Nicht die Bewegungsrichtung vergessen — $L, R, N$ sind Pflichtangaben in $\delta$.
- Halten und Akzeptieren nicht vermischen. Halten allein ist keine Akzeptanz.
- Keine Sprachdefinition nur aus einem Beispiel raten — Sonderfälle (leeres Wort, Länge 1) prüfen.
- Nicht behaupten, eine NTM erkenne mehr Sprachen als eine DTM.
- Nicht schreiben, das Halteproblem sei unentscheidbar, weil es zu schwer ist — der Grund ist die Diagonalisierung.