"(bis eine Haltebedingung erreicht wird)"
Nein. Eine Turing-Maschine hat keine Haltebedingung.
Eine Turing-Maschine haelt, wenn sie keinen Befehl in ihrem
Befehlssatz mehr ausfuehren kann (meistens ist dann die
Maschine in einem Zustand, indem keine weiteren Zeichen
gelesen werden).
Wenn eine Turing-Maschine Haltebedingungen haette, muessten
diese in irgendeiner Logik beschrieben werden. Sollte das
irgendeine Praedikatenlogik mit Argumenten der Turing-Maschine
sein, wuerde das die Berechenbarkeitsmaechtigkeit von
Turing-Maschinen veraendern, und zwar dahingehen, dass Dinge
wie das Halteproblem, welches gerade das Problem aufzeigt, dass
man mit den Mittel der Turing-Maschinen nicht feststellen kann,
ob eine Turing-Maschine, angesetzt auf einen beliebigen, aber
festen Input ueberhaupt in endlicher Zeit anhaelt, witzlos waeren.
Koennte man Haltebedingungen formulieren, waere das Halteproblem
trivial, und damit alle anderen auf das Halteproblem reduziblen
Probleme ebenso.
O'Brien
Nein. Eine Turing-Maschine hat keine Haltebedingung.
Eine Turing-Maschine haelt, wenn sie keinen Befehl in ihrem
Befehlssatz mehr ausfuehren kann (meistens ist dann die
Maschine in einem Zustand, indem keine weiteren Zeichen
gelesen werden).
Wenn eine Turing-Maschine Haltebedingungen haette, muessten
diese in irgendeiner Logik beschrieben werden. Sollte das
irgendeine Praedikatenlogik mit Argumenten der Turing-Maschine
sein, wuerde das die Berechenbarkeitsmaechtigkeit von
Turing-Maschinen veraendern, und zwar dahingehen, dass Dinge
wie das Halteproblem, welches gerade das Problem aufzeigt, dass
man mit den Mittel der Turing-Maschinen nicht feststellen kann,
ob eine Turing-Maschine, angesetzt auf einen beliebigen, aber
festen Input ueberhaupt in endlicher Zeit anhaelt, witzlos waeren.
Koennte man Haltebedingungen formulieren, waere das Halteproblem
trivial, und damit alle anderen auf das Halteproblem reduziblen
Probleme ebenso.
O'Brien