Algorithmisch unlösbare Probleme (2)

$$Id: halte.tex,v 1.2 2003/10/24 13:16:42 joe Exp $$

Das Halteproblem ist:

• Eingabe: ein Zahl $x$ und eine Zahl $y$
• Frage: hält das Programm $P_x$ bei Eingabe $y$?

Wir beweisen, daß das algorithmisch unlösbar ist: es gibt keinen Algorithmus, der die Frage für alle Eingaben korrekt beantwortet.