Das Haltepoblem

• Definition: H alle (x, y) $\in$ $\mathbb {N}$² mit der Eigenschaft: die Turingmaschine Nr. x führt bei Eingabe y nur endliche viele Schritte aus
• Satz: (Church, Turing, 193*): Die Menge H ist nicht entscheidbar.

Das ist kein Fehler der Turingmaschinen, sondern diese Aussage gilt für alle vernünftigen Berechnungsmodelle.