Halting Problem

Kann man ein Programm schreiben (nennen wir es HaltChecker), das Code prüft? Du gibst ihm Programm X. Er sagt: "X wird fertig (terminiert)." Oder: "X läuft ewig (Endlosschleife)." Alan Turing bewies 1936: Nein, das geht nicht. Es ist logisch unmöglich. Denn wenn es HaltChecker gäbe, könnte ich ein Programm bauen, das genau das Gegenteil tut von dem, was HaltChecker vorhersagt. (Das Lügner-Paradoxon als Code). Das Halteproblem ist unentscheidbar.

Merksatz: Das von Alan Turing bewiesene Entscheidungsproblem, ob ein gegebenes Computerprogramm bei einer bestimmten Eingabe jemals anhält oder unendlich weiterläuft; es ist algorithmisch nicht lösbar (unentscheidbar).

Wenn dein Compiler oder deine IDE sich aufhängt ("Analyzing..."), ist sie vielleicht in eine Falle gelaufen. Kein Tool (Linter, Static Analysis) kann perfekt vorhersagen, was Code tut. Es muss immer raten ("Timeout nach 10 Sekunden") oder abschätzen. Die totale Sicherheit gibt es nicht.

1. Der Beweis (Sketch)

Angenommenfunktion Halt(P, I) -> True/False. Baue Funktion Paradox(P): Wenn Halt(P, P) == True: Laufe ewig (while true). Wenn Halt(P, P) == False: Halte an (return). Starte Paradox(Paradox). Wenn es hält -> Läuft es ewig. Wenn es ewig läuft -> Hält es. Widerspruch! Also kann es Halt() nicht geben.

2. Busy Beaver

Da wir nicht wissen, ob Programme halten: Was ist das Programm mit 5 Zuständen, das am längsten läuft, aber noch hält? Das ist die Busy Beaver Function. Sie wächst schneller als jede berechenbare Funktion (schneller als Ackermann, schneller als Grahams Zahl).

1. Satz von Rice

Das Halteproblem ist nur die Spitze des Eisbergs. Der Satz von Rice verallgemeinert dies: Jede semantische Eigenschaft eines Programms ist unentscheidbar. "Wird das Programm jemals die Zahl 42 ausgeben?" -> Unentscheidbar. "Wird es mehr als 100kb RAM verbrauchen?" -> Unentscheidbar. "Ist es ein Virus?" -> Unentscheidbar. Man kann zwar für einzelne Programme Beweise führen, aber es gibt keinen universellen Algorithmus, der für alle Programme entscheidet, ob sie eine bestimmte Eigenschaft (außer trivialen Dingen wie "Enthält es das Wort 'if'?") haben.

2. Turing-Grade & Reduzierbarkeit

Mathematiker nutzen das Halteproblem als Referenzpunkt. Man sagt: Problem A ist "genauso schwer" wie das Halteproblem, wenn man A lösen könnte, falls man ein Orakel für das Halteproblem hätte. Dies führt zu den Turing-Graden. Das Halteproblem hat den Grad $0'$. Es gibt Probleme, die noch "unentscheidbarer" sind (z. B. das Halteproblem für Computer, die bereits das Halteproblem lösen können). Diese Hierarchie zeigt, dass das Universum der Logik nach oben hin unendlich komplex ist und wir mit unseren Computern nur die unterste Stufe ("berechenbar") bewohnen.

3. Kolmogorov-Komplexität

Es gibt eine tiefe Verbindung zwischen Halten und Kompression. Die Kolmogorov-Komplexität eines Strings ist das kürzeste Programm, das diesen String erzeugt. Ob ein String $S$ durch ein Programm $P$ der Länge $L$ erzeugt werden kann, hängt davon ab, ob $P$ jemals anhält und $S$ ausgibt. Da wir nicht wissen, ob Programme anhalten, ist die Kolmogorov-Komplexität nicht berechenbar. Wir können nie sicher wissen, ob wir eine Datei "maximal" komprimiert haben oder ob es ein noch kürzeres Programm gäbe, das sie erzeugt, aber vielleicht 1000 Jahre zum Rechnen braucht.