[ < ]
Beispiel - Halteproblem
Sei A die Menge aller Algorithmen und E dieMenge aller Eingabedaten. Die Funktion
fH : A x E -> {true, false}
mit fH(A, e) := true, falls der Algorithmus A Element A, angewendet auf die Eingabe e, nach endlich vielen Schritten hält (terminiert), sonst false.
Es gib keinen Algorithmus, der fH berechnet, also als Eingabe einen beliebigen anderen Algorithmus und dessen Daten erhält und feststellt, ob die Berechnung terminieren wird.
Beweis für die Nicht-Existenz eines Algorithmus für das Halteproblem:
Sei fH : AxE -> {true,false}(A : Menge aller Algorithmen, E : Menge aller Eingabedaten)
mit fH (A,e) : = true falls der Algorithmus A angewendet
auf die Eingabe e hält.
und fH(A,e) : = false falls der Algorithmus A angewendet
auf die Eingabe e nicht hält.
Annahme:Es existiert so ein fH (ein Algorithmus der
das Halteproblem berechnet)
Man definiere den Algorithmus fP:
mit fP(A) : = (hält nicht) falls fH(A,A) = true
und fP(A) : = (hält) falls fH(A,A) = false
Bei einem Aufruf von fP (fP) ergeben sich zwei Möglichkeiten:
In beiden Fällen ergibt sich ein Widerspruch. Es kann also keinen solchen Algorithmus fH geben.