Beweisarchiv: Theoretische Informatik: Berechenbarkeit: Halteproblem

Das spezielle Halteproblem

Beschreibung

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

Anmerkung

$<\cdot >:𝒯ℳ\to {\mathrm{\Sigma }}^{*}$ ist eine Kodierungsfunktion, die jeder Turingmaschine eine eindeutige Kodierung zuordnet. Und umgekehrt beschreibt jedes $x\in {\mathrm{\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{i}\mathrm{f}{M}_K$(mit Eingabe x mit Eingabe <$x$>)$\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}$ Endlosschleife $\mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}$ terminiere

Oder in Pseudocode: $\tilde{M}(x)=\mathrm{i}\mathrm{f}{M}_K(x(x))\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{L}\mathrm{O}\mathrm{O}\mathrm{P}\mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{e}$

Es gilt für alle $M$ also: $\tilde{M}$ mit Eingabe <$M$> hält $\iff$ $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 $\iff$ $\tilde{M}$ (mit Eingabe <$\tilde{M}$>) hält nicht.

Widerspruch!

$◻$

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!

$◻$

Das Halteproblem bei leerem Wort

Beschreibung

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

Behauptung

$H_{ϵ}$ ist unentscheidbar.

Beweis

Angenommen, $H_{ϵ}$ sei entscheidbar. Sagen wir durch eine TM $M_{ϵ}$. 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_{ϵ}$ auf $\tilde{M}$ so gilt:

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

bzw. mengentheoretisch

<$\tilde{M}$> $\in H_{ϵ}\iff$ <$M$>#$w$$\in H$

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

$◻$