Moin,
immer mal wieder taucht irgendwo eine Doku, ein Video, ein Artikel, oder sonstiges über das Halteproblem auf (auch vor ein paar Wochen in der SB, wo ich etwas ähnliches geschrieben habe wie hier im Thread). Leider bin ich nicht in der Lage zu verstehen warum das Halteproblem ein Problem ist. Und inzwischen geht mir jede Erklärung die ich irgendwo sehe auf den Zeiger, weil ich sie einfach nicht verstehe (bzw. jede beliebige Erklärung sofort mit den unten genannten 2 Punkten widerlegen kann).
Definition (stark vereinfacht. Aber ich gehe davon aus, dass jeder das Problem kennt):
Das Programm H entscheidet ob Programm P mit input X (also P(X)) hält, oder nicht.
Das Programm R mit Input H(...) hält, wenn H(...) entscheidet, dass "..." nicht hält, das Programm R geht in eine Endlosschleife, wenn H(...) entscheidet, dass "..." hält.
H soll entscheiden ob R hält.
R hält, wenn H entscheidet, dass R nicht hält und umgekehrt -> Problem.
Meine Probleme damit:
1. Instanzen. ALLES ist instanziiert. Die Aussage "R hält, wenn H entscheidet, dass R nicht hält" ist Unfug, da H für einen vollständigen Input (P(X), oder eben R(...)) entscheidet ob P(X) hält. Die Parameter mit denen H gestartet werden sind also zum Zeitpunkt wenn H gestartet wird fixiert. Also können die Parameter sich im Nachhinein nicht mehr ändern und das Ergebnis von H beeinflussen. Und selbst wenn man annimmt, dass es keine Instanzen gibt, dann werden H, R, P und X alle auf einem endlichen Computer (mit endlichem Speicherplatz) ausgeführt, sodass Punkt 2 zur Geltung kommt.
2. Endlichkeit. ALLES ist endlich. Jedes Programm (wie auch immer es aussehen mag) hat eine endliche Anzahl innerer Zustände (alle bits die das Programm beeinflussen kann). Ein Programm H könnte jetzt jeden inneren Zustand von P(X) mitschreiben. Wenn P(X) in einen inneren Zustand eintritt den es früher schonmal hatte (weil P(X) deterministisch arbeitet), ist P(X) in einer Endlosschleife. Wenn P(X) vorheriges nicht erfüllt wird es nach endlicher Zeit seine endlichen inneren Zustände durchlaufen haben und halten. -> Problem gelöst.
Kann es sein, dass das Halteproblem nur für "unendliche" Maschinen sinnvoll definiert ist?
Ich bin einfach zu blöd dafür und Wikipedia hilft mir auch nicht weiter...
Falls jemand eine "einfache" Erklärung hat wie der Hase läuft, her damit. 
Vielleicht habe ich auch einen Denkfehler. Auch in diesem Fall: Her damit.
Edit: Kaum hab ich die englische Wikipedia angeschaut habe ich meinen eigenen Satz auf englisch gefunden...
The halting problem is theoretically decidable for linear bounded automata (LBAs) or deterministic machines with finite memory. A machine with finite memory has a finite number of configurations, and thus any deterministic program on it must eventually either halt or repeat a previous configuration
Na super... Dann bleibt nur noch die Frage übrig, warum das offensichtlich für "nicht existierende Computer" definierte Problem andauernd falsch dargestellt wird...
lg
M
