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 ist 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

Das die Unlösbarkeit des Halteproblems (und der Gödelsche Unvollständigkeitssatz) hatten bei ihrer Entdeckung eine erschütternde Wirkung auf das damals herrschende mathematische Weltbild. Damals versuchte man gerade, die Mathematik durch eine strikte Formalisierung zu vereinheitlichen und den Regeln der Logik zu unterwerfen (siehe Hilberts Programm). Man ging davon aus, dass sich jedes mathematische Problem durch eine geeignete Formalisierung lösen lässt, dass es also immer möglich sei, eine Aussage so zu formulieren, dass man durch die Regeln der Logik und Mathematik erkennen kann, ob sie wahr oder falsch ist - gesucht war also ein vollständiges und widerspruchfreies System. Nach den Erkenntnissen von Turing und Gödel ist so etwas jedoch grundsätzlich nicht möglich: in jedem System, das turingmächtig ist (bzw. die Mächtigkeit der Arithmetik besitzt) lassen sich Aussagen formulieren, die weder bewiesen noch widerlegt werden können: solche Systeme sind grundsätzlich unvollständig. Oder anders ausgedrückt: es gibt Funktionen, die zwar wohldefiniert sind, deren Wert sich dennoch im Allgemeinen nicht berechnen lässt.

Setzt man nun die churchsche These als wahr voraus, so können Maschinen und letztlich Menschen das Halteproblem (und viele andere Probleme) grundsätzlich nicht lösen. Das führt zu der philosophisch weitreichenden Aussage, dass nicht jedes Problem lösbar ist, selbst dann nicht, wenn man eigentlich alle relevanten Informationen kennt und sich streng an einen mächtigen Formalismus hält.

Für die Softwareentwicklung bedeutet das Halteproblem, dass im Allgemeinen eine automatische Überprüfung einer Programmlogik nicht möglich ist (siehe auch Verifikation). Insbesondere ist es nicht möglich festzustellen, ob ein gegebenes Programm jemals anhalten wird.

Siehe auch: Berechenbarkeit, Kausalität, Determinismus, Indeterminismus

Siehe auch