Home -> Themen -> Halteproblem


Turing-Werkstatt

Theoretische Informatik am PC


O.Pletsch 1862 Halteprobleme für Turing-Maschinen

Definition
allgemeinesHalteproblem
Beim allgemeinen Halteproblem für Turing-Maschinen stellt man die Frage nach einem Algorithmus, der entscheiden kann, ob eine Turing-Maschine M mit einem Band und {' ','I'} als Alphabet bei Eingabe eines Wortes w halten wird. Die Entscheidung müßte durch eine Maschine U herbeigeführt werden. Eingabe für U wäre dann M in Form der Befehlstafel TM und das Anfangswort w für M. U müsste mit ja oder nein antworten.
Das spezielle Halteproblem ist ein Teilproblem des allgemeinen Halteproblems. Hierbei wird nur gefragt, ob M bei Start auf dem leeren Band stoppt.

Das Halteproblem ist nicht entscheidbar
Wäre das spezielle Halteproblem entscheidbar, so könnte die Sigma-Funktion auf folgendem Weg berechnet werden :
Um Sigma(n) zu berechnen geht man jede Maschine M über {' ','I'} mit n Zuständen durch. Man entscheidet zuerst ob M beim Start auf dem leeren Band hält. Wenn das der Fall ist, startet man M mit leerem Band. Nach dem Stopp wird die Anzahl der produzierten Striche festgestellt. Sigma(n) ist das Maximum aller Strichzahlen.
Da die Sigma-Funktion nicht berechenbar ist, kann das spezielle Halteproblem auch nicht entscheidbar sein. Das umfassendere allgemeine Halteproblem ist damit auch nicht entscheidbar.

Das spezielle Halteproblem ist aufzählbar
allgemeinesHalteproblem
Die Menge aller Turingmaschinen mit einem Band und {' ','I'} als Alphabet, die nach einem Start auf dem leeren Band halten, sollen durch eine Maschine U aufgezählt werden. Um U zu realisieren sind verschiedene Teilalgorithmen nötig. Der zentrale Kern besteht aus einer Maschine U1= Schritte-Test.tm , die entscheidet ob eine Maschine M nach genau s Schritten stoppt.
Wie erhält man U1 ?
Man erweitert die universelle Turing-Maschine Universell.tm durch einen Zähler, der beim Start auf die Zahl s gesetzt wird und der bei jeder Simulation eines Befehls von M um 1 reduziert wird. Wenn der Zähler auf 0 reduziert und gleichzeitig der Stoppbefehl der simulierten Maschine M ausgeführt wurde, so ist das Ergebnis : ja M stoppt nach genau s Schritten. Andernfalls ist das Ergebnis negativ. Mit U1 werden später alle möglichen Maschinen Mr auf alle möglichen Schrittzahlen s getestet.
Als nächstes braucht man eine Maschine U2= alle-Tafeln.tm, die alle Turing-Tafeln von Maschinen mit einem Band und dem Alphabet {' ','I'} aufzählt.
Letzter Teil-Algorithmus ist eine Maschine U3= alle-Paare.tm, die alle Paare (r,s) natürlicher Zahlen nach dem Diagonalverfahren aufzählt.
Zusammenwirken aller Teilalgorithmen in U = H-aufzaehlen.tm :

Da jede Maschine Mr auf diese Weise mit jeder Schrittzahl s getestet wird, werden alle haltenden Maschinen erkannt und ausgegeben.
Das spezielle Halteproblem ist aufzählbar aber nicht entscheidbar.

Anmerkungen zur Simulation mit Turing-Werkstatt :
Die angegebenen Teilmaschinen U1 bis U3 sind in ihrem Wirken gut zu erkennen wenn man sie isoliert betrachtet. Beim Zusammenbau aller Teile zu U geht die Übersichtlichkeit jedoch verloren. Eine ausführliche Beschreibung jeder Einzelheit wäre eine ermüdende Sache, die ich mir und dem User ersparen möchte. Lassen Sie H-aufzaehlen.tm laufen und beobachten Sie welche Maschinen auf Band1 nach links ausgegeben werden.
H-aufzaehlen2.tm arbeitet wie H-aufzaehlen.tm. Allerdings werden Maschinen übergangen, die direkt nach dem Start stoppen, und solche die keinen Stoppbefehl in der Tafel haben. Die Ausgabe besteht dann nur aus Maschinen, die mindestens 2 Schritte machen bevor sie anhalten. Es dauert dafür länger bis Maschinen ausgegeben werden.

Eine nicht-aufzählbare Menge
Das Komplement des speziellen Halteproblems besteht aus allen Maschinen mit einem Band und dem Alphabet {' ','I'}, die bei Start auf dem leeren Band nicht anhalten.
Das Komplement des speziellen Halteproblems ist nicht aufzählbar.
Begründung :
Ist eine Menge A und ihr Komplement aufzählbar, so ist A entscheidbar. Man kann aus beiden Algorithmen zum Aufzählen von A und vom Komplement von A einen Entscheidungsalgorithmus für A konstruieren.