Halteproblem ::: Theoretische Informatik

Die Sprache

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

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 auf¹³.

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 auftaucht¹⁴, 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 laufen¹⁵.

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 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 entscheidet.
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 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:

wird mit Hilfe von $H_{\epsilon}$ gelöst ( wird so umgeformt, daß es $H_{\epsilon}$ ist):

$\begin{displaymath}H\leq H_{\epsilon}\end{displaymath}$
wird auf reduziert. Der Algorithmus wird mit Hilfe von gelöst. Jede aussagelogische Formel in kann in eine aussagelogische Formel in 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}$
wird auf zurückgeführt. ist ein Spezialfall von . 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 ist¹⁶ . 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 DTM¹⁷ 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 an
$\Leftrightarrow$	$w\not\in L(\tau)$

Widerspruch

Fußnoten

... auf ¹³: Jeder Algorithmus ist formulierbar in endlich vielen Programmzeilen.
... auftaucht ¹⁴: Der Halteproblemalgorithmus ist ein Algorithmus und in der Tabelle sind alle Algorithmen aufgelistet.
... laufen ¹⁵: In der Tabelle müßten ein ,,J'' und ein ,,N'' gleichzeitig stehen.
... ist ¹⁶: 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.
... DTM ¹⁷: Diese gibt es eigentlich gar nicht, aber wir nehmen einfach mal an, daß es sie gibt.

Rekursive Aufzählbarkeit Entscheidbarkeit Andere unentscheidbare Probleme

Ψ Die Informatikseite

Halteproblem

Die Sprache des Halteproblems und des speziellen Halteproblems