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).
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:
Klausur-Tipp: Schreibe im Beweis die Konstruktion von explizit hin (die invertierende Selbstanwendung) und führe beide Fälle von zum Widerspruch. Genau diese Struktur gibt die Punkte.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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:
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.
| 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".
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) ruft H(P, P) auf.H "P(P) hält", geht D in eine Endlosschleife.H "P(P) hält nicht", hält D sofort.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.
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.
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.
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.
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.
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.
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.
Klausurfragen mit Lösungen (6)
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.
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.
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
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.
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.
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.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
Lösungen pro Lücke:
Erklärung: Das Halteproblem ist unentscheidbar, aber semi-entscheidbar. Andere Probleme werden durch Reduktion vom Halteproblem als unentscheidbar bewiesen.
Typ: Lückentext
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
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.