Halteproblem

Kern des Halteproblems

Das Halteproblem ist eine Frage der theoretischen Informatik: Kann man für jeden Algorithmus und jede beliebige Eingabe entscheiden, ob die Ausführung nach endlich vielen Schritten anhält oder endlos weiterläuft? Algorithmen werden dabei mit abstrakten Maschinen modelliert, besonders mit Turingmaschinen.

Alan Turing bewies 1937, dass es keinen Algorithmus und keine Turingmaschine gibt, die diese Frage für alle möglichen Turingmaschinen und Eingaben beantwortet. Das Halteproblem ist daher algorithmisch nicht entscheidbar. Es ist ein grundlegendes Ergebnis der Berechenbarkeitstheorie, also des Fachgebiets, das untersucht, was Maschinen grundsätzlich berechnen können.

Bedeutung und praktische Grenzen

In ausreichend komplexen formalen Systemen gibt es Aussagen, die weder beweisbar noch widerlegbar sind. Kurt Gödel veröffentlichte 1931 einen Beweis dafür; sein Gödelscher Unvollständigkeitssatz zeigte die Unmöglichkeit des Hilbertprogramms. Auch das Halteproblem beschreibt in formalen Systemen, die Turingmaschinen enthalten, eine Aussage, die weder bewiesen noch widerlegt werden kann.

Aus seiner Unlösbarkeit folgt, dass es wohldefinierte mathematische Funktionen gibt, deren Werte nicht für jeden Parameter berechnet werden können; die Radó-Funktion ist ein Beispiel. Nach der Church-Turing-These ist alles intuitiv Berechenbare auch von einer Turingmaschine berechenbar. Falls diese These wahr ist, kann das Halteproblem grundsätzlich nicht algorithmisch entschieden werden.

Eine allgemeine Programmlogik kann deshalb nicht automatisiert für alle Programme feststellen, ob sie jemals enden; dies heißt Terminierungsbeweis. Für bestimmte Klassen ist das Halteproblem jedoch entscheidbar, etwa für Programme ohne Schleifen. Praktische Programme und Verfahren können daher so aufgebaut sein, dass für sie aufgrund ihrer Struktur ein automatisierter Terminierungsbeweis möglich ist.

Beispiel mit der Collatz-Vermutung

Bei vielen Programmen lässt sich leicht feststellen, ob sie anhalten. Schwieriger ist dies bei Programmen, deren Verhalten mit ungelösten mathematischen Fragen verbunden ist. Für jede natürliche Zahl n > 0 betrachtet das folgende Programm wiederholt n/2 für gerade n und (3 · n) + 1 für ungerade n, bis n = 1 gilt:

„wiederhole; falls n gerade: n := n / 2; sonst: n := (3 * n) + 1; bis n = 1“.

Das Programm hält für jede Eingabe n, wenn die bisher unbewiesene Collatz-Vermutung richtig ist. Diese Vermutung besagt, dass die Folge früher oder später 4, 2, 1 erreicht; wegen der Abbruchbedingung würde das Programm dann anhalten.

Diagonalargument und Semi-Entscheidbarkeit

Angenommen, es gäbe eine Turingmaschine H, die zu einer codierten Maschinenbeschreibung b(T) und einer Eingabe w entscheidet, ob T mit w anhält oder endlos weiterläuft. Der Beweis zeigt, dass eine solche Maschine nicht existieren kann.

Das Halteproblem ist semi-entscheidbar: Eine universelle Turingmaschine kann T mit w simulieren und hält genau dann, wenn T mit w hält. Semi-entscheidbar bedeutet hier: Für Fälle, die zur Menge gehören, kann die Maschine anhalten und ein Ergebnis liefern; für andere Fälle darf sie endlos laufen. Das Halteproblem wäre genau dann entscheidbar, wenn auch sein Komplement semi-entscheidbar wäre.

Nimmt man an, eine Maschine G semi-entscheide das Komplement, dann berechnet sie die partielle Funktion g(i,w) = 1, falls die Turingmaschine i bei Eingabe w nicht hält, und ist sonst undefiniert. Ihre Diagonale wäre f(i) = 1, falls die Turingmaschine i bei Eingabe i nicht hält, und sonst undefiniert. Hat F, die f berechnet, die Nummer n_f, entsteht bei f(n_f) ein Widerspruch: Hält F auf n_f, müsste f dort undefiniert sein; hält F nicht, müsste sie halten und 1 ausgeben. Also ist das Komplement nicht semi-entscheidbar.

Beweisschritte und leeres Eingabeband

Die Diagonalsprache besteht aus allen Turingmaschinen, die nicht halten, wenn sie ihre eigene Kodierung als Eingabe erhalten. Wäre sie semi-entscheidbar, würde eine Maschine F bei b(F) genau dann halten und 1 ausgeben, wenn F bei b(F) nicht hält. Dies ist ein Widerspruch.

Wäre das Komplement des Halteproblems semi-entscheidbar, könnte eine Maschine G für b(T)*w bei nicht haltendem T den Wert 1 ausgeben. Dabei ist * eine Zeichenkette, die weder in b(T) noch in w vorkommt. Eine Maschine F könnte G dann mit b(T)*b(T) starten und so die Diagonalsprache semi-entscheiden. Da dies unmöglich ist, ist auch das Komplement nicht semi-entscheidbar. Eine entscheidende Maschine H würde bei nicht haltendem T 0 und bei haltendem T 1 ausgeben. Daraus ließe sich G bauen, die bei 0 eine 1 ausgibt und bei 1 endlos läuft. Folglich kann H nicht existieren.

Eine gleich schwere Variante ist das Halteproblem mit leerem Eingabeband, das blank-tape halting problem (BTHP) oder Null-Halteproblem. Es fragt, ob eine Turingmaschine T bei leerem Band anhält. Eine Maschine für das allgemeine Halteproblem löst unmittelbar das BTHP. Umgekehrt kann eine BTHP-Maschine das allgemeine Problem lösen: Zu T und w konstruiert man T_w, die zuerst w auf das Band schreibt und sich anschließend wie T verhält. T_w hält auf leerem Band genau dann, wenn T mit Eingabe w hält.