Das Halteproblem

Wie schon bei der universellen Registermaschine gesehen, kann man Programme schreiben, die wiederum Dinge mit anderen Programmen machen, zum Beispiel sie auszuführen. Man könnte sie aber auch anderweitig analysieren.

Nun ist ein wichtiges Problem bei solchen Maschinen, ob sie jemals halten werden, also jemals eine End-Anweisung erreichen. Alan Turing stellte sich die Frage, ob man dies im Allgemeinen lösen könnte. Das Problem nennt sich Halteproblem.

Formaler ist die Frage, ob es ein Programm $M$ mit Eingaben $R_1$ und $R_2$ gibt, sodass in $R_1$ ein codierter Programmcode steht (wie vorhin bei der universellen Registermaschine), und in $R_2$ eine codierte Folge von Registern als Eingabe (ebenfalls analog zur universellen Registermaschine), sodass $M$ genau dann $R_3$ auf $0$ gesetzt lässt, wenn dieses Programm mit den gegebenen Eingaben terminiert.

Nehmen wir an, ein solches Programm $M$ würde existieren. Wir können daraus ein Programm $N$ generieren, das folgendes tut:

   "führe M aus"
   if R[3] == 0 then goto Loop
   End
   Loop: goto Loop

Dieses Programm würde genau dann terminieren, wenn das in $R_1$ codierte Programm mit den in $R_2$ codierten Registerbelegungen nicht terminiert. Nun modifizieren wir das Programm erneut, und erhalten das Programm $O$:

   "setze R[2] auf <R[1]>"
   "führe M aus"
   if R[3] == 0 then goto Loop
   End
   Loop: goto Loop

$O$ terminiert genau dann, wenn das in $R_1$ codierte Programm mit sich selbst als Eingabe terminiert. Man nennt solche Programme self-accepting. Sei nun $O$ codiert durch $o$. Dann können wir $O(o)$ berechnen, also $O$ mit $R_1=o$. Die Frage ist nun, ob $O(o)$ terminiert.