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
Berechenbarkeit und das Halteproblem
Kann ein Programm zuverlässig vorhersagen, ob ein anderes Programm jemals anhält oder in einer Endlosschleife hängt? Die überraschende Antwort von Alan Turing (1936): Nein, kein Algorithmus kann das für alle Programme leisten. Das Halteproblem ist das berühmteste unentscheidbare Problem der Informatik.
Was du in der Klausur können musst:
- entscheidbar, semi-entscheidbar und unentscheidbar sauber unterscheiden
- den Widerspruchsbeweis des Halteproblems (Selbstanwendung) nachvollziehen
- mit Reduktionen weitere Probleme als unentscheidbar zeigen
- den Satz von Rice anwenden
Die Idee in einem Satz
Es gibt klar formulierte Probleme, die kein Algorithmus lösen kann. Das Halteproblem ("hält Programm
Pbei Eingabex?") ist unentscheidbar: es gibt keinen immer haltenden Algorithmus, der das für alle Paare(P, x)korrekt beantwortet.
Drei Stufen der Entscheidbarkeit
| Begriff | Bedeutung |
|---|---|
| entscheidbar (rekursiv) | Es gibt einen Algorithmus, der immer hält und für jede Eingabe korrekt "ja" oder "nein" ausgibt. |
| semi-entscheidbar (rekursiv aufzählbar) | Es gibt einen Algorithmus, der bei "ja" hält und "ja" sagt, bei "nein" aber endlos laufen darf. |
| unentscheidbar | Es gibt keinen Algorithmus, der das Problem für alle Eingaben entscheidet. |
Das Halteproblem ist semi-entscheidbar, aber nicht entscheidbar: simuliert man P(x) und es hält, weiß man "ja". Hält es nicht, wartet man ewig und erfährt nie sicher "nein".
Der Beweis: Widerspruch durch Selbstanwendung
Angenommen, es gäbe einen Entscheider H(P, x), der korrekt sagt, ob P(x) hält. Dann baut man ein Gegenprogramm D:
D(P)ruftH(P, P)auf.- Sagt
H"P(P)hält", gehtDin eine Endlosschleife. - Sagt
H"P(P)hält nicht", hältDsofort.
Jetzt die tödliche Frage: Was macht D(D)? Beide möglichen Antworten führen in den Widerspruch. Probiere es im Visualizer:
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Diagonalisierung
Diese Beweistechnik heißt Diagonalisierung und ist dieselbe, mit der Cantor zeigte, dass die reellen Zahlen überabzählbar sind. Man konstruiert ein Objekt (D), das sich von jedem Programm in der "Diagonale" (der Selbstanwendung) unterscheidet, und erzeugt so einen Widerspruch.
Weitere Probleme: Reduktion
Hat man ein unentscheidbares Problem, zeigt man die Unentscheidbarkeit anderer durch Reduktion:
A ≤ B("Areduziert aufB"): Kann man jede Instanz vonAin eine vonBübersetzen, und istAunentscheidbar, dann ist auchBunentscheidbar.
Wäre B entscheidbar, könnte man über den Umweg auch A entscheiden, Widerspruch. So sind das Wortproblem, das Äquivalenzproblem von Programmen und viele mehr als unentscheidbar bewiesen.
Satz von Rice
Jede nicht-triviale semantische (verhaltensbezogene) Eigenschaft von Programmen ist unentscheidbar.
"Nicht-trivial" heißt: manche Programme haben die Eigenschaft, andere nicht. Beispiele für unentscheidbare Fragen: "Berechnet P die konstante Funktion 0?", "Hält P bei jeder Eingabe?". Das erklärt, warum es keinen perfekten statischen Analysator oder allgemeinen Terminierungs-Checker geben kann.
Klausur-Faustregeln
1. Entscheidbar bedeutet: ein immer haltender Algorithmus gibt korrekt ja/nein aus.
2. Das Halteproblem ist unentscheidbar (Turing 1936). Kein Algorithmus entscheidet für alle (P, x), ob P(x) hält.
3. Der Beweis ist ein Widerspruch durch Selbstanwendung: D(D) führt unter jeder Annahme zum Widerspruch.
4. Das Halteproblem ist semi-entscheidbar, sein Komplement nicht. Semi-entscheidbar ≠ entscheidbar.
5. Reduktion A ≤ B: ist A unentscheidbar und auf B reduzierbar, ist B unentscheidbar. Richtung beachten.
6. Satz von Rice: jede nicht-triviale semantische Eigenschaft von Programmen ist unentscheidbar.
Häufige Stolpersteine
1. "Unentscheidbar" mit "schwer" verwechseln. Es heißt nicht "rechenintensiv", sondern: es existiert gar kein Algorithmus, der das Problem für alle Eingaben löst.
2. Konkret vs. allgemein. Für viele einzelne Programme kann man durchaus entscheiden, ob sie halten. Unentscheidbar ist nur das allgemeine Problem über alle Programme.
3. Semi-entscheidbar für entscheidbar halten. Das Halteproblem ist semi-entscheidbar (man findet die "ja"-Fälle), aber nicht entscheidbar (die "nein"-Fälle erkennt man nie sicher).
4. Reduktionsrichtung verdrehen. Um B als unentscheidbar zu zeigen, reduziert man ein bekanntes unentscheidbares A auf B (A ≤ B), nicht B auf A.
5. Rice auf syntaktische Eigenschaften anwenden. Rice gilt nur für semantische (Verhaltens-)Eigenschaften. "Hat das Programm genau 100 Zeilen?" ist syntaktisch und entscheidbar.
6. Diagonalisierung als Trick abtun. Sie ist eine fundamentale Technik (Cantor, Gödel, Turing) und der Kern, warum Selbstanwendung den Widerspruch erzeugt.
Interaktiv verstehen
Den Widerspruch selbst auslösen
Wähle eine Annahme über D(D) und verfolge die Schlusskette. Egal ob du "hält" oder "hält nicht" annimmst, du landest beim Gegenteil. Genau das beweist, dass der Entscheider H nicht existieren kann.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Schreibe im Beweis die Konstruktion von D explizit hin (die invertierende Selbstanwendung) und führe beide Fälle von D(D) zum Widerspruch. Genau diese Struktur gibt die Punkte.
Praxis-Übung
Klausurfragen mit Lösungen (6)
- F1.Was besagt das Halteproblem?
Antwort: Es gibt keinen Algorithmus, der für alle Programme und Eingaben entscheidet, ob sie halten
Erklärung: Das Halteproblem ist unentscheidbar: kein Algorithmus kann für jedes Paar (Programm, Eingabe) korrekt und immer haltend entscheiden, ob das Programm bei dieser Eingabe anhält. Bewiesen von Turing 1936.
- F2.Was bedeutet 'entscheidbar' (rekursiv)?
Antwort: Es gibt einen Algorithmus, der immer hält und korrekt ja/nein ausgibt
Erklärung: Entscheidbar heißt: ein Algorithmus existiert, der bei jeder Eingabe nach endlicher Zeit hält und die korrekte Antwort (ja oder nein) liefert. Das Halteproblem hat genau diese Eigenschaft NICHT.
- F3.Das Halteproblem ist semi-entscheidbar (rekursiv aufzählbar).
Antwort: Wahr
Erklärung: Richtig. Simuliert man P(x) und es hält, gibt man 'ja' aus. Hält P(x) nicht, läuft die Simulation ewig. Die 'ja'-Fälle sind also erkennbar (semi-entscheidbar), die 'nein'-Fälle nicht. Daher semi-entscheidbar, aber nicht entscheidbar.
Typ: Wahr/Falsch
- F4.Im Widerspruchsbeweis: Was macht das Gegenprogramm D, wenn der Entscheider H sagt, dass D(D) hält?
Antwort: D geht in eine Endlosschleife (hält also NICHT)
Erklärung: D ist genau so konstruiert, dass es das Gegenteil tut: sagt H 'hält', geht D in eine Endlosschleife. Damit hält D(D) nicht, obwohl H 'hält' gesagt hat, der Widerspruch.
- F5.Wie zeigt man, dass ein neues Problem B unentscheidbar ist?
Antwort: Man reduziert ein bekanntes unentscheidbares Problem A auf B (A ≤ B)
Erklärung: Man reduziert ein bekanntes unentscheidbares A auf B: A ≤ B. Wäre B entscheidbar, könnte man über die Reduktion auch A entscheiden, Widerspruch. Die Richtung (bekannt-unentscheidbar auf neu) ist entscheidend.
- F6.Welche Frage ist nach dem Satz von Rice unentscheidbar?
Antwort: Berechnet das Programm die konstante Funktion 0?
Erklärung: 'Berechnet P die konstante Funktion 0?' ist eine nicht-triviale SEMANTISCHE (Verhaltens-)Eigenschaft, nach Rice unentscheidbar. Die anderen drei sind syntaktische Eigenschaften des Quelltexts und damit entscheidbar.
Klausur-Quiz
Klausurfragen mit Lösungen (6)
- F1.Wer bewies die Unentscheidbarkeit des Halteproblems?
Antwort: Alan Turing (1936)
Erklärung: Alan Turing bewies 1936 die Unentscheidbarkeit des Halteproblems, im selben Werk, in dem er die Turing-Maschine einführte. Die Technik (Diagonalisierung) geht auf Cantor zurück, Gödel nutzte Verwandtes für seine Unvollständigkeitssätze.
- F2.Welche Beweistechnik steckt hinter dem Halteproblem-Beweis?
Antwort: Diagonalisierung / Selbstanwendung mit Widerspruch
Erklärung: Der Beweis nutzt Diagonalisierung: man konstruiert ein Programm D, das sich bei Selbstanwendung D(D) widersprüchlich verhält. Dieselbe Technik verwendete Cantor für die Überabzählbarkeit der reellen Zahlen.
- F3.Ordne jeden Begriff der richtigen Beschreibung zu.
Zuordnungen:
- entscheidbar → Algorithmus hält immer, gibt ja/nein korrekt
- semi-entscheidbar → hält und bestätigt bei 'ja', darf bei 'nein' ewig laufen
- unentscheidbar → kein Algorithmus löst es für alle Eingaben
Erklärung: Entscheidbar: immer haltender korrekter Algorithmus. Semi-entscheidbar: nur die 'ja'-Fälle sicher erkennbar. Unentscheidbar: gar kein Entscheider existiert. Das Halteproblem ist semi-entscheidbar, aber unentscheidbar.
Typ: Zuordnung
- F4.Das Halteproblem ist {{1}} (kein Entscheider existiert), aber {{2}} (die haltenden Fälle sind durch Simulation erkennbar). Weitere Probleme zeigt man per {{3}} als unentscheidbar.
Lösungen pro Lücke:
- {{1}}: unentscheidbar
- {{2}}: semi-entscheidbar / semientscheidbar / rekursiv aufzählbar / rekursiv aufzaehlbar
- {{3}}: Reduktion / Reduktionen
Erklärung: Das Halteproblem ist unentscheidbar, aber semi-entscheidbar. Andere Probleme werden durch Reduktion vom Halteproblem als unentscheidbar bewiesen.
Typ: Lückentext
- F5.Für ein konkretes, einzelnes Programm kann man nie entscheiden, ob es hält.
Antwort: Falsch
Erklärung: Falsch. Für viele konkrete Programme ist das sehr wohl entscheidbar (z.B. ein Programm ohne Schleifen hält immer). Unentscheidbar ist nur das ALLGEMEINE Halteproblem über alle Programme und Eingaben.
Typ: Wahr/Falsch
- F6.Warum kann es keinen perfekten allgemeinen Terminierungs-Checker für Programme geben?
Antwort: Weil 'Hält P bei jeder Eingabe?' eine nicht-triviale semantische Eigenschaft ist und nach Rice / dem Halteproblem unentscheidbar
Erklärung: Ein allgemeiner Terminierungs-Checker würde das Halteproblem lösen, das ist unentscheidbar. Allgemeiner folgt aus dem Satz von Rice, dass jede nicht-triviale semantische Eigenschaft (wie 'terminiert immer') unentscheidbar ist. Deshalb arbeiten reale Analysatoren nur approximativ.
