Halteproblem
Das Halteproblem ist das grundlegende Beispiel für ein unentscheidbares Problem in der Theoretischen Informatik, das auf Alan M. Turing zurückgeht. 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.
Solange man jedoch nicht genau spezifiziert, für welches Algorithmenmodell der Beweis geführt werden soll, lässt sich nur die Beweissidee angeben. Hierzu wird hier Pseudocode verwendet.
Angenommen, es gibt eine Funktion haltetest:
function haltetest(Programm,Eingabe):
if (Programm(Eingabe) terminiert) then return JA;
else return NEIN;
end haltetest;
Dann lässt sich daraus folgendes Programm test bilden:
procedure test(Programm):
while (haltetest(Programm,Programm) == JA) {}
// Wenn das Programm bei Eingabe seiner eigenen Kodierung
// terminiert, dann terminiert die Prozedur test nicht.
end test;
Wenn man nun der Prozedur test sich selbst als Eingabedaten übergibt und sie somit 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.
Es gibt aber eine Turingmaschine, die immer dann Ja ausgibt, wenn M auf w hält, aber endlos arbeitet, wenn M nicht auf w hält. Diese muss lediglich die Berechnung der Turingmaschine simulieren, und Ja ausgeben, nachdem diese Simulation ggf. hält. Das Halteproblem gehört deshalb zu den semi-entscheidbaren Problemen.
Bemerkenswert ist, dass im Beweis die hypothetische Funktion haltetest nur in der Form haltetest(Programm,Programm) benutzt wird. Dies bedeutet, dass man die Lösbarkeit des Halteproblems in seiner vollen Allgemeinheit gar nicht zu unterstellen braucht, um zu einem Widerspruch zu gelangen. Es lässt sich mit derselben Idee beweisen, dass das spezielle Halteproblem, bei dem nur entschieden werden soll, ob ein Programm bei Eingabe seiner eigenen Kodierung hält, unentscheidbar ist.
Viele weitere Variationen des Halteproblems sind ebenfalls nicht entscheidbar, so zum Beispiel die Frage, ob eine Turingmaschine bei der leeren Eingabe hält. Die Unentscheidbarkeit des (speziellen) Halteproblems ist die Grundlage vieler weiterer Unentscheidbarkeitsaussagen, kulminierend in der Aussage des Satz von Rice, nach dem die Frage, ob die von einem Algorithmus berechnete Funktion eine nichttriviale Eigenschaft hat, nicht entscheidbar ist.
Konsequenzen
Die Entdeckung der Unlösbarkeit des Halteproblems (und des Gödelschen Unvollständigkeitssatzes) hatte 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 immer möglich festzustellen, ob ein gegebenes Programm jemals anhalten wird.
Siehe auch: Berechenbarkeit, Kausalität, Determinismus, Indeterminismus
Siehe auch
- Berechenbarkeit
- Entscheidungsproblem
- Gödelscher Unvollständigkeitssatz
- Erfüllbarkeit
- Abzählbarkeit
- Satz von Rice