Es gibt keine Turing- Maschine, die entscheiden kann, ob eine beliebige andere Turing-Maschine je anhält oder nicht.

As Alan Turing proved in 1936, a computer program can never tell you for sure whether another program might end up calculating forever without end—except by simulating the operation of that program and thus potentially going off the deep end itself.

Als Eingabe wird das Halteproblem "gefüttert" mit dem Text eines zulässigen Programms A in unserer ausgewählten Programmiersprache Spr und einer möglichen Eingabe X (die nichts anderes als eine Folge von Symbolen ist). Das Problem fragt danach, ob A anhalten würde, wenn wir es mit der Eingabe X laufen liessen.

Der erbrachte Beweis dafür, daß das Halteproblem ein mathematisch formulierbares Problem ist, das sich maschinell nicht lösen läßt, hat ungemein tiefgreifende Bedeutung für das wissenschaftliche Selbstverständnis der Mathematik.

Das Halteproblem kann, wie auch das anspruchsvollere Verifikationsproblem, nicht auf algorithmischem Wege gelöst werden: Es ist unentscheidbar. Es gibt also keine allgemeine Möglichkeit, in endlicher Zeit zu bestimmen, ob die Ausführung eines bestimmten Programmes mit einer bestimmten Eingabe anhalten wird oder nicht.

Die allgemeine Lösung dieses Problems mit Hilfe eines Aigorithmus, wenn es einen solchen Algorithmus gäbe, hätte enorme praktische Relevanz für die zuverlässige Programmierung von Computern. Die definitive Einsicht, daß es eine algorithmische Lösung indessen nicht gibt, hat gravierende theoretische Konsequenzen für die prinzipiellen Leistungsgrenzen von Programmen.

Man ist versucht, das Problem durch einen Simulationsalgorithmus lösen zu wollen, der einfach das mit der Eingabe X laufende Programm A nachahmt und schaut, was passiert. Wenn das simulierte A anhält. Dann können wir selbst begründetermaf3en anhalten und schliessen, da die Antwort "ja" ist. Die Schwierigkeit liegt darin wann wir mit dem Warten aufhören sollen, um " nein" zu sagen, Wir können nicht einfach nach einer langen Zeitspanne aufgeben und beschliessen, da die Simulation nie anhalten wird, weil sie es bislang nicht getan hat. Vielleicht müssten wir sie nur ein klein bisschen weiter laufen lassen. vielleicht sogar nur eine Mikrosekunde. Und sie würde anhalten. Daher ist es nicht ausreichend, das Verhalten des gegebenen Programmes mit der gegebenen Eingabe zu simulieren.