Ψ Die Informatikseite

Menü
Unterabschnitte

Halteproblem

Die Sprache des Halteproblems und des speziellen Halteproblems

Die Sprache $H$ des Halteproblems ist

\begin{displaymath}H=\{w\char93 x:w,x\in\{0,1\}^{*}:\tau_{w}\,h\uml {a}lt\, f\uml {u}r\, das\, Eingabewort\, x\, an\}\end{displaymath}

Die Sprache $H'$ für das spezielle Halteproblem ist

\begin{displaymath}H'=\{w;w\in \{0,1\}^{*}:\tau_{w}\,h\uml {a}lt\,f\uml {u}r\,die\,eingabe\,w\,an\}\end{displaymath}

Satz: Das Halteproblem ist unentscheidbar

Die Sprache H des Halteproblems ist unentscheidbar, d.h. es gibt keine Turingmaschine die H entscheidet.

Informeller Beweis des Halteproblems mittels Halteproblemtabelle

Wir erstellen eine Tabelle.
  • Auf der x-Achse tragen wir jede mögliche Eingabe auf, die ein Algorithmus haben kann.
  • Auf der y-Achse tragen wir alle möglichen Algorithmen auf13.
Jede Halteproblemtabellenzelle enthält ein
  • ,,JA'': Wenn der angegebene Algorithmus für die Eingabe terminiert.
  • ,,NEIN'': Wenn der angegebene Algorithmus für die Eingabe nicht terminiert, d.h endlos läuft.
Der Halteproblemalgorithmus muß sich komplementär zur Tabelle verhalten. Wenn
  • Der Algorithmus terminiert, also ein ,,JA'' dort steht, muß er endlos laufen.
  • Der Algorithmus endlos läuft, also ein ,,NEIN'' dort steht, muß er verwerfen.
Nun betrachten wir das Komplement der Diagonalen der Tabelle. Da der Halteproblemalgorithmus irgendwann selbst in der Tabelle auftaucht14, muß er selbst entscheiden, ob er anhält. Wenn der der Halteproblemalgorithmus endlos läuft, muß er gleichzeitig terminieren, wenn er terminiert, muß er endlos laufen15.

Das Halteproblem ist Semientscheidbar

Wir können eine universelle Turingmaschine $\tau$ konstruieren, die die Turingmaschine $\tau'$ simuliert. Der Algorithmus, den $\tau'$ ausführt, soll überprüft werden, ob er bei der enthaltenen Eingabe terminiert. Die Turingmaschine $\tau$ akzeptiert, sobald der $\tau'$ die Berechnung beendet hat. Wenn aber $\tau'$ endlos läuft, dann akzeptiert auch $\tau$ nie. $\Rightarrow$ Semientscheidbarkeit

Spezielles Halteproblem

Die Sprache $H'$ des speziellen Halteproblems lautet:

\begin{displaymath}H'=\{w;w\in\{0,1\}^{*}\tau_{w}\,h\uml {a}lt\,bei\,der\,eingabe\,w\,an\}\end{displaymath}

Definitionen:
  • $\tau'$ ist die DTM von der angenommen wird, daß sie die Sprache $H'$ entscheidet.
  • $\tau$ ist die DTM des Halteproblemalgorithmusses:
    • Läuft $\tau'$ endlos, so akzeptiert $\tau$.
    • Akzeptiert $\tau'$, so läuft $\tau$ endlos.
Sei $\tau=\tau_{w}$. D.h. der Halteproblemalgorithmus wird auf sich selbst angewendet.
1.Fall:
  $\tau$ läuft endlos
$\Leftrightarrow$ $\tau'$ akzeptiert
$\Leftrightarrow$ $w\in H'$
$\Leftrightarrow$ $\tau_{w}=\tau$ hält an
  Widerspruch!

2.Fall:

  $\tau$ akzeptiert
$\Leftrightarrow$ $\tau'$ läuft endlos
$\Leftrightarrow$ $w\not\in H'$
$\Leftrightarrow$ $\tau_{w}=\tau$ läuft endlos
  Widerspruch!

Reduktion

L heißt auf K reduzierbar ($L\leq K$), wenn es eine Funktion $f(x)$ gibt, so daß gilt

\begin{displaymath}x\in L \Leftrightarrow f(x) \in K\end{displaymath}

d.h. daß es eine totale Übergangsfunktion gibt, die aus jeder Eingabe für L eine Eingabe für K macht und daß L und K für die gleiche (für K vorher transformierte) Eingabe akzeptieren, verwerfen oder endlos laufen.


\begin{displaymath}L\,reduzierbar\,auf\,K\Leftrightarrow L\leq K \end{displaymath}

  • Ein Algorithmus für L wird erstellt, indem ein Algorithmus K benutzt wird.
  • Weiterhin kann auch L als ein Spezialfall von K betrachtet werden. Dies ist keine Reduktion mehr, sondern eine Einbettung in das Problem K.
Beispiele für den ersten Punkt:
  • $H$ wird mit Hilfe von $H_{\epsilon}$ gelöst ($H$ wird so umgeformt, daß es $H_{\epsilon}$ ist):

    \begin{displaymath}H\leq H_{\epsilon}\end{displaymath}

  • $SAT$ wird auf $3SAT$ reduziert. Der $SAT$ Algorithmus wird mit Hilfe von $3SAT$ gelöst. Jede aussagelogische Formel in $SAT$ kann in eine aussagelogische Formel in $3SAT$ mit dem selben ,,Output'' überführt werden:

    \begin{displaymath}SAT\leq_{poly}3SAT\end{displaymath}

Beispiele für den letzten Punkt:
  • Das spezielle Halteproblem wird in das allgemeine Halteproblem eingebettet. Hiermit zeigen wird, daß auch das allgemeine Halteproblem unentscheidbar ist.

    \begin{displaymath}H'\leq h\end{displaymath}

  • $3SAT$ wird auf $SAT$ zurückgeführt. $3SAT$ ist ein Spezialfall von $SAT$. Somit gilt diese polynomielle Reduktion, da wir sogar überhaupt gar keine Umformung durchführen müssen.

    \begin{displaymath}3SAT\leq_{poly}SAT\end{displaymath}

Reduktionsprinzip


\begin{displaymath}L\leq K\end{displaymath}

K entscheidbar $\Rightarrow$ L entscheidbar
K semientscheidbar $\Rightarrow$ L semientscheidbar
K unentscheidbar $\Rightarrow$ L unentscheidbar

Unentscheidbarkeit des Halteproblems

Wir zeigen, daß das spezielle Halteproblem auf das Halteproblem reduzierbar ist $H'\leq h$. Offenbar kann man das spezielle Halteproblem mit der Funktion

\begin{displaymath}f(x)=x\char93 x\end{displaymath}

in das allgemeine Halteproblem überführen (da die DTM $\tau$ ja auf sich selbst angewendet wird). Somit ist dann genauso wie das spezielle Halteproblem auch das allgemeine Halteproblem unentscheidbar, da das spezielle Halteproblem ein Spezialfall des allgemeinen Halteproblem ist16 . Wir erhalten: Die Sprache H

\begin{displaymath}H=\{w\char93 x:w,x\in\{0,1\}^{*}\,\tau_{w}\,h\uml {a}lt\,f\uml {u}r\,die\,Eingabe\,x\,an\}\end{displaymath}

ist unentscheidbar.

Die Nicht-Semientscheidbarkeit des Komplements des Halteproblems: Satz

Die Sprache $\overline{H}$ (das Komplement des Halteproblems)

\begin{displaymath}\overline{H}=\{w\char93 x:w,x\in\{0,1\}^{*}:\,\tau_{w}\,h\uml {a}lt\,f\uml {u}r\,die\,Eingabe\,x\,nicht\,an\}\end{displaymath}

ist nicht semientscheidbar.

Die Nicht-Semientscheidbarkeit des Komplements des Halteproblems: Informell

  • Zunächst beinhaltet die Komplementsprache $\overline{H}$ auch alle Worte, die nicht der Form $w\char93 x$ $(w,x\in\{0,1\}^{*})$ sind. Diese schließen wir jedoch aus.
  • Das spezielle Halteproblem war unentscheidbar (haben wir bewiesen), d.h. daß es keine DTM gibt, die H' entscheidet, mit anderen Worten, es gibt keine DTM, die alle Wörter $w\not\in H'$ verwirft.
  • Das Komplement des speziellen Halteproblems ist noch schärfer. Da das Verhalten der DTM17 genau umgedreht sein muß, ist es nicht sicher, ob die DTM alle Wörter $w\in\overline{H}'$ akzeptiert.
$\Rightarrow$ nicht semientscheidbar

Die Nicht-Semientscheidbarkeit des Komplements des Halteproblems: Formal

Angenommen $\overline{H}'$ ist semientscheidbar. Wir definieren eine DTM $\tau$, so daß gilt:

\begin{displaymath}L(\tau)=\overline{H}'\end{displaymath}

Unsere DTM $\tau$ akzeptiert oder läuft nur endlos. Verwerfen tut sie nicht.
Sei $w=code(\tau)$.
Wir setzen weiterhin $\tau=\tau_{w}$: Es gilt:
  $w\in\overline{H}'$
$\Leftrightarrow$ $w\in L(\tau)$
$\Leftrightarrow$ Berechnung für $\tau=\tau_{w}$ akzeptierend
$\Leftrightarrow$ $\tau=\tau_{w}$ hält bei der Eingabe $w$ an
$\Leftrightarrow$ $w\not\in L(\tau)$
Widerspruch

Fußnoten

... auf13
Jeder Algorithmus ist formulierbar in endlich vielen Programmzeilen.
... auftaucht14
Der Halteproblemalgorithmus ist ein Algorithmus und in der Tabelle sind alle Algorithmen aufgelistet.
... laufen15
In der Tabelle müßten ein ,,J'' und ein ,,N'' gleichzeitig stehen.
... ist16
Wir machen hier nicht den Rückschluß, daß man ein unbekanntes Problem L auf ein bekanntes Problem K zurückführt, sondern wir sehen das spezielle Halteproblem als einen Spezialfall des Halteproblems an. Deshalb schreiben wir $H'\leq h$, obwohl H eigentlich noch gar nicht bekannt ist.
... DTM17
Diese gibt es eigentlich gar nicht, aber wir nehmen einfach mal an, daß es sie gibt.