Satz Halteproblem für Turingmaschinen ist unentscheidbar

Einfache Sprache

Def. Satz Halteproblem für Turingmaschinen ist unentscheidbar

HALT-TM ist nicht entscheidbar.

Beweisidee: Es wird eine Reduktion von HALT-TM auf WORD-TM und der Fakt, dass WORD-TM nicht entscheidbar ist, genuzt.

Beweis: Der Beiweis ist in drei Schritte geteilt mit dem Ziel ein Widerspruch zu erhalten.

Schritt 1.: Sei $\mathcal M$ eine TM. Dann sei $\mathcal M'$ die TM, die aus $\mathcal M$ entsteht, wenn $q_{rej}$ durch einen neuen Zustand $q$, der eine unendliche Schleife bildet, ersetzt wird. Also ist $\mathcal M'$ erstmal im Zustand $q$, ist ihr einziger Folgezustand $q$. Genauer $\forall a\in\Gamma:\delta'(q,a) =(q,a,N)$. Wenn $\mathcal M$ verwirft, dann terminiert $\mathcal M'$ nicht. Sei $w\in A^*$, dann gilt:

• falls $\mathcal M$ $w$ akzeptiert, dann akzeptiert $\mathcal M'$ $w$ und
• falls $\mathcal M$ auf $w$ verwirft oder nicht terminiert, dann terminiert $\mathcal M'$ auf $w$ nicht. Also $$\langle\mathcal M,w\rangle\in\mathrm{WORD_TM}\quad\mathrm{gdw.}\quad\langle\mathcal M',w\rangle\in\mathrm{WORD_TM}\;.$$

Schritt 2.: Bemerke, dass sich aus ein Wort der Form $\langle\mathcal M,w\rangle$ ein Wort der Form $\langle\mathcal M',w\rangle$ konstruieren lässt. Dazu muss lediglich, abhängig von der konkreten Kodierung, klein Änderungen vorgenommen werden.

Schritt 3.: Zweck Widerspruch wird angenommen, dass $\mathrm{HALT_TM}$ entscheidbar ist, z.B. durch die TM $\mathcal T$. Wir zeigen, dass dann auch WORD-TM entscheidbar ist, und zwar durch die TM $\mathcal T'$, wobei $\mathcal T'$ wie folgt für die Eingabe $x$ funktioniert:

1. Überprüfe ob $x = \langle\mathcal M,w\rangle$ für eine geeignete TM $\mathcal M$ und ein geeignetes Wort $w$ (geeignet im Sinne, dass z.B. $x$ ein Wort über dem Eingabealphabet ist). Falls nicht, verwirf.
2. Konstruiere $\langle\mathcal M',w\rangle$ nach Schritt 2..
3. Simuliere $\mathcal T$ auf $\langle\mathcal M',w\rangle$

Nach Schritt 1. gilt:

1. für jedes $x$, was nicht der Form $\langle\mathcal M,w\rangle$ entspricht: $\mathcal T'$ verwirft $x$
2. für jedes $x$, was der Form $\langle\mathcal M,w\rangle$ entspricht:
   1. falls $\mathcal M$ $w$ akzeptiert, akzeptiert $\mathcal T'$ $w$
   2. falls $\mathcal M$ $w$ verwirft, verwirft $\mathcal T'$ $w$.

Damit entscheidet $\mathcal T'$ das Allgemeines Wortproblem für Turingmaschinen, was nach dem Satz Allgemeine Wortproblem für Turingmaschinen ist unentscheidbar ein Widerspruch ergibt.