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

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

Die philosophischen Konsequenzen des Halteproblems sind besonders interressant in Verbindung mit der philosophischen Denkrichtung des Determinismus. Dort geht man davon aus, dass jedes Ereignis durch vorhergegangene Ereignisse fest vorbestimmt ist, sich also das Universum als Kausalkette entwickelt. Das bezieht sich auf alle Ebenen, auch auf die Elementarteilchen von Energie und Materie. Da nun das menschliche Gehirn auch aus Materie besteht, müsste es sich demnach ebenfalls deterministisch verhalten, also in einer Weise, die durch eine Turingmaschine (theoretisch) berechnet und vorherbestimmt werden kann. Das würde aber bedeuten, dass es keinen freien Willen gibt: jeder unserer Gedanken war im Augenblick des Urknalls bereits festgelegt. Desweiteren würde es auch bedeuten, dass einerseits der Mensch nicht in der Lage ist, Probleme zu lösen, die nicht auch von einer Turingmaschine (oder einem anderen Computer) berechnet werden könnten. Und andererseits, dass alles, was Menschen tun, denken und fühlen, von einem Programm simuliert werden könnte, Künstliche Intelligenz und auch künstliches Bewusstsein also möglich ist. Die Grenze zwischen bewusstem, ziegerichtetem Handeln und bloßem mechanischen Abarbeiten eines Regelwerks verschwindet damit völlig, Wille und Bewusstsein wären eine Illusion. Albert Einstein vertrat diese Meinung unter Verweis auf die Unfreiheit des Willens nach Arthur Schopenhauer. Er verlieh seiner Einstellung mit einem viel zitierten Satz Ausdruck: Gott würfelt nicht.

Akzeptiert man die deterministische Weltanschauung aber nicht, so muss man sich fragen, was, wenn nicht feste Regeln, die durch physikalische Modelle abgebildet werden können, denn das Universum regiert. Eine Möglichkeit wären Schicksal und göttliche Intervention, was allerdings dem Menschen ebenfalls den freien Willen abspricht. Eine andere wäre die Existenz des "echten" Zufalls, also die Tatsache, dass es Ereignisse gibt, deren Ausgang auch dann nicht vorherzusehen ist, wenn alle Einflüsse und Faktoren bekannt sind. Diese Denkweise scheint von der Quantenmechanik bestätigt zu werden - aber auch sie hat unliebsame Konsequenzen für den freien Willen: er wäre nun ein bloßes Würfelspiel.

Siehe auch: Philosophischer Determinismus, Indeterminismus

Siehe auch

• Berechenbarkeit
• Entscheidungsproblem
• Gödelscher Unvollständigkeitssatz
• Erfüllbarkeit
• Abzählbarkeit