Beweisarchiv: Theoretische Informatik: Berechenbarkeit: Halteproblem

Beweisarchiv: Theoretische Informatik

Sprachen: Pumping-Lemma

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$