Halteproblem

Das Halteproblem ist das grundlegende Beispiel für ein unentscheidbares Problem in der Theoretischen Informatik. Es beschäftigt sich mit der Frage, ob eine in einer geeigneten Kodierung gegebene Turingmaschine auf einer gegebenen Eingabe anhält, d.h. dass sie nicht unendlich lange läuft. Man kann anstelle der Turingmaschine auch ein Programm in einer üblichen Programmiersprache betrachten, dies ist ein im wesentlichen äquivalentes Problem.

Die wichtigste Fragestellung bezüglich des Halteproblems ist nun, ob es entscheidbar ist, d.h. ob eine Turingmaschine existiert, die für jedes Paar aus kodierter Turingmaschine und Eingabe berechnen kann, ob die kodierte Maschine auf dieser Eingabe anhält. In der angewandten Informatik lautet die Frage: Kann man ein Programm entwickeln, das als Eingabe den Quelltext eines zweiten Programms sowie dessen Eingabewerte erhält, welches entscheiden kann, ob das zweite Programm terminiert, d.h. nicht endlos weiterläuft.

Diese Fragestellung ist eng verknüpft mit dem Entscheidungsproblem; ihre Lösung, bzw. der unten angeführte Beweis ihrer Unlösbarkeit, ist seinerseits eng verwandt mit dem Gödelschen Unvollständigkeitssatz.

Alan Turing bewies 1936, dass es keinen Algorithmus geben kann, der das Halteproblem für alle Eingaben löst:

Beweis

Durch einen Widerspruchsbeweis lässt sich eindeutig zeigen, dass eine solche Turingmaschine nicht existiert.

Angenommen es gibt eine Funktion haltetest (in Pseudocode):

function haltetest(Programm,Eingabe):
    if (Programm(Eingabe) terminiert) then return JA;
    else return NEIN;
end haltetest;

sowie eine Programm test, das von haltetest getestet werden soll:

function test(Programm):
    while (haltetest(Programm,Programm)) {}
    // Wenn das Programm terminiert, wenn es sich selbst als Eingabe bekommt,
    // dann terminiert die Funktion test nicht. 
end testprogramm;

Wenn man nun der Funktion test sich selbst als Eingabedaten übergibt und sie von der Methode haltetest auf Terminierung prüfen lässt, kann diese kein richtiges Ergebnis liefern:

test(test); //Dieser Aufruf terminiert genau dann, wenn er nicht terminiert. (Widerspruch!)

liefert haltetest(test,test) JA, so hieße dies, dass test(test) terminiert -- aber die Bedingung haltetest(Programm,Programm) innerhalb von test ist gerade dann immer wahr, so dass test(test) eben nicht terminiert, weil die while-Schleife niemals beendet wird. Das ist ein Widerspruch!

liefert haltetest(test,test) NEIN, so ist die Bedingung der while-Schleife niemals wahr, und test(test) terminiert sofort. Das iste ebenfalls ein Widerspruch!

Das heißt nun, es gibt keine Turingmaschine, die, erhält sie als Eingabe die Codierung einer Turingmaschine M und eine zugehörige Eingabe w, Ja ausgibt, wenn M auf w hält und Nein ausgibt, wenn M nicht auf w hält.

Jedoch gibt es eine Turingmaschine, die zumindest immer Ja ausgibt, wenn M auf w hält, möglicherweise aber endlos arbeitet, wenn M nicht auf w hält. Bereits ein Spezialfall des Halteproblems, die Frage, ob eine Turingmaschine auf der leeren Eingabe hält, genannt H0, ist nicht entscheidbar.

Konsequenzen

Mathematische Konsequenzen

Dieses zunächst unscheinbare Problem und seine Beantwortung hat weitreichende Konsequenzen:

Die mathematisch präzise formulierte Aufgabe des Halteproblems ist für eine Turingmaschine unlösbar. Setzt man die churchsche These als wahr voraus, so können auch Maschinen und letztlich Menschen das Halteproblem nicht lösen.

Das Halteproblem bedeutet für die Softwareentwicklung, dass im Allgemeinen eine automatische Überprüfung von Programmlogik nicht möglich ist (siehe auch Verifikation).

Philosophisch-weltanschauliche Konsequenz

Geht man von der Existenz einer Gottheit aus und unterstellt man ihr, sie sei allwissend und stehe nicht im Widerspruch zu allem Vorhandenen, so hieße das, dass sie prinzipiell auch das Halteproblem entscheiden können müsse. So muss diese Gottheit also die Fähigkeiten von Menschen und Maschinen im Sinn von Berechenbarkeit übersteigen.

Geht man davon aus, dass eine Gottheit keiner Turingmaschine im oben angenommenen Sinn entspricht, also übersinnliche Fähigkeiten hätte, so wäre ihre Nichtexistenz nicht bewiesen.

Geht man aber davon aus, dass die Existenz einer Gottheit in Widerspruch zu Bekanntem steht, also unlogisch ist, weil niemand ein bewiesenermaßen unlösbares Problem lösen kann, so gäbe es keine Gottheit! Dies gilt insbesondere unter Voraussetzung der Vorstellung mancher Gläubiger, nach der Menschen, deren mathematischen Fähigkeiten das Halteproblem nicht zu lösen vermögen, Ebenbilder einer Gottheit sind. Dann könnte eine Gottheit nicht existieren! Die Nichtexistenz Gottes wäre bewiesen. Zumindest aber wäre bewiesen, dass eine Gottheit keine Maschine ist.

Diese philosophisch-weltanschauliche Konsequenz setzt allerdings die Korrektheit der churchschen These voraus.

Am Ende beweist diese These aber weder die Existenz noch die Nichtexistenz von Gott, denn Gott wäre kein abzählbar potentiell unendlicher Automat, wie die Turingmaschine.

Man muss beachten, dass die Turingmaschine streng determiniert ist, nur abzählbare Mengen bearbeitet und keinen Zufall kennt. Sie ist eine theoretische Maschine. Jede praktische Maschine hält, zumindest, wenn der Strom ausfällt (allgemeiner, wenn ein zufallsbedingter Zustand eintritt). Gott könnte die Reset-Taste drücken. Die Frage, ob dann die Welt hält, ist nicht entscheidbar.

Siehe auch: Gottesbeweis