Halteproblem
Das Halteproblem ist eine Problemstellung der Theoretischen Informatik und beschäftigt sich mit der Frage, ob eine Turingmaschine existiert, die als Eingabe eine eine zweite Turingmaschine in Textform und dessen Eingabe erhält, und entscheiden kann, ob die Turingmaschine terminiert (vollständig ausgeführt wird).
In der angewandten Informatik lautet die Frage: Kann man ein Programm entwickeln, das als Eingabe den Quelltext eines zweiten Programms sowie deren Eingabewerte erhält, welches entscheiden kann, ob das zweite Programm terminiert, d.h. nicht in einer Endlosschleife hängen bleibt.
Beweis
Durch einen Widerspruchsbeweis lässt sich eindeutig zeigen, dass eine solche Turingmaschine nicht existiert.
Angenommen es gibt eine Methode haltetest (Programmcode in Jana):
boolean haltetest(↓char[] p, ↓char[] e)// Liefert true wenn das durch die Zeichenkette p dargestellte Programm bei den durch die Zeichenkette e dargestellten Eingabedaten terminiert.sowie eine zu testende Methode programm:
programm(↓char[] e) {// e ... Eingabedaten als Zeichenkette
while (haltetest(e,e)) {}
}Wenn man nun der Methode programm sich selbst als Eingabedaten übergibt und sie von der Methode haltetest auf Terminierung prüfen lässt, kann diese kein richtiges Ergebnis liefern:
- liefert sie false, terminiert die Methode programm => Falsch
- liefert sie true, terminiert die Methode programm nicht => Ebenfalls falsch
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. Dies ist sogar trivial: natürlich kann unsere geforderte Turingmaschine einfach warten, bis M eventuell hält und dann Ja ausgeben.
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 Church'sche These als bewiesen voraus, so können auch Maschinen und letztlich Menschen das Halteproblem nicht lösen.
Das Halteproblem bedeutet für die Softwareentwicklung, dass eine automatische Überprüfung von Programmlogik nicht möglich ist.
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.