Beweisarchiv: Theoretische Informatik: Berechenbarkeit: Halteproblem

Beweisarchiv: Theoretische Informatik

Sprachen: Pumping-Lemma

Berechenbarkeit: Halteproblem

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

Anmerkung

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

${\displaystyle K}$ ist nicht entscheidbar.

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

Formal also:

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

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

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

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

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

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

Widerspruch!

${\displaystyle \Box }$

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

H ist unentscheidbar

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

${\displaystyle \Box }$

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

${\displaystyle H_{\epsilon }}$ ist unentscheidbar.

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

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

bzw. mengentheoretisch

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

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

${\displaystyle \Box }$