Beweisarchiv: Theoretische Informatik: Berechenbarkeit: Halteproblem

Das spezielle Halteproblem

Beschreibung

$K=\lbrace$ < $M$ > | $M$ ist eine Turingmaschine, die bei Eingabe < $M$ > hält $\rbrace$

Anmerkung

$<\cdot >:{\mathcal {TM}}\to \Sigma ^{*}$ ist eine Kodierungsfunktion, die jeder Turingmaschine eine eindeutige Kodierung zuordnet. Und umgekehrt beschreibt jedes $x\in \Sigma ^{*}$ eine gültige Turingmaschine.

Behauptung

$K$ ist nicht entscheidbar.

Beweis

Angenommen $K$ sei entscheidbar, sagen wir durch eine Turingmaschine (TM) $M_{K}$ . Dann lässt sich zu einer gegebenen TM $M$ eine TM ${\tilde {M}}$ konstruieren, die (bei Eingabe < $M$ >) genau dann hält, wenn $M$ nicht hält. Konstruktion der Maschine ${\tilde {M}}$ : Zu einer gegebenen Maschine $M$ entscheidet man zunächst mittels $M_{K}$ ob $M$ (bei Eingabe < $M$ >) hält. Falls dem so ist, gehe in eine Endlosschleife. Andernfalls halte.

Formal also:

Angenommen $M_{K}$ löse das spezielle Halteproblem.

Definiere ${\tilde {M}}$ für Eingabe < $x$ > als $\mathrm {if} \ M_{K}$ (mit Eingabe x mit Eingabe < $x$ >) $\ \mathrm {then}$ Endlosschleife $\mathrm {else}$ terminiere

Oder in Pseudocode: ${\tilde {M}}(x)=\mathrm {if} \ M_{K}(x(x))\ \mathrm {then} \ \mathrm {LOOP} \ \mathrm {else} \ \mathrm {terminate}$

Es gilt für alle $M$ also: ${\tilde {M}}$ mit Eingabe < $M$ > hält $\Leftrightarrow$ $M$ (mit Eingabe < $M$ >) hält nicht (*)

Aus Anwendung von ${\tilde {M}}$ mit < ${\tilde {M}}$ > gilt (vgl. (*)):

${\tilde {M}}$ (mit Eingabe < ${\tilde {M}}$ >) hält $\Leftrightarrow$ ${\tilde {M}}$ (mit Eingabe < ${\tilde {M}}$ >) hält nicht.

Widerspruch!

\Box

Das allgemeine Halteproblem

Beschreibung

$H=\{$ < $M$ ># $w$ | $M$ hält bei Eingabe $w$ $\}$

Behauptung

H ist unentscheidbar

Beweis

Angenommen, H sei entscheidbar, dann wäre auch K entscheidbar. Widerspruch!

\Box

Das Halteproblem bei leerem Wort

Beschreibung

$H_{\epsilon }=\{$ < $M$ > | $M$ ist eine TM, die beim leerem Wort als Eingabe hält $\}$

Behauptung

$H_{\epsilon }$ ist unentscheidbar.

Beweis

Angenommen, $H_{\epsilon }$ sei entscheidbar. Sagen wir durch eine TM $M_{\epsilon }$ . Wir erzeugen einen Widerspruch, indem wir zeigen, dass dann $H$ entscheidbar wäre. Sei also < $M$ ># $w$ eine Probleminstanz von $H$ . Wir erzeugen eine Maschine ${\tilde {M}}$ die sich bei leerer Eingabe genau so verhält, wie $M$ bei Eingabe $w$ . Konstruktion von ${\tilde {M}}$ : ${\tilde {M}}$ schreibt zunächst $w$ auf das Band und simuliert dann die TM $M$ . Setzt man nun $M_{\epsilon }$ auf ${\tilde {M}}$ so gilt:

${\tilde {M}}$ mit leerer Eingabe hält $\Leftrightarrow$ $M$ hält mit Eingabe $w$

bzw. mengentheoretisch

< ${\tilde {M}}$ > $\in H_{\epsilon }\Leftrightarrow$ < $M$ ># $w$ $\in H$

Da die Konstruktion von ${\tilde {M}}$ aus $M$ von einer TM übernommen werden kann, ist damit $H$ entscheidbar. Widerspruch!

\Box