Algorithmisch unlösbare Probleme (3)

Id: halte.tex,v 1.4 2004/11/11 06:26:13 waldmann Exp

Es gibt Rechnungen, die halten, und Rechnungen, die nicht halten (z. B. ,,Endlos-Schleifen``).

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 nicht entscheidbar ist: es gibt keinen Algorithmus, der diese Frage für alle Eingaben (x, y) korrekt beantwortet.

Diskussion: wir könnten einfach die Rechnug von P_x auf y starten. Aber ...wann können wir sie abbrechen?