Algorithmisch unlösbare Probleme (3)

Id: halte.tex,v 1.1 2006-10-09 13:24:19 waldmann Exp

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


Das Halteproblem ist:

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 Px auf y starten. Aber ...wann können wir sie abbrechen?



Johannes Waldmann 2007-01-23