Algorithmisch unlösbare Probleme (2)

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.