das zu jedem anderen Programm P in endlicher Zeit sagt,
ob dieses, wenn man es mit einer Eingabe E startet,
sich irgendwann beendet oder unendlich lange weiterläuft,
vorausgesetzt, es steht ihm beliebig viel Speicher zur Verfügung?
Oder:
Kann man ein Programm H schreiben, das für alle E, P in endlicher Zeit ausgibt, ob P(E) terminiert.
Oder:
Gibt es ein Programm H mit:
1. H(P,E) = true für P(E) terminiert
2. H(P,E) = false für P(E) läuft endlos
Zu 1.: Wenn H P(E) startet und P(E) sich beendet, gibt H true aus.
Zu 2.: Wann aber soll H false ausgeben? H weiß ja nicht, ob P(E) sich in Zukunft noch beenden wird oder nicht.
Halteproblem
, anschaulich erklärt