Satz Allgemeine Wortproblem für Turingmaschinen ist unentscheidbar

Einfache Sprache

Def. Satz Allgemeine Wortproblem für Turingmaschinen ist unentscheidbar

WORD-TM ist nicht entscheidbar.

Beweisidee: Beweis durch Widerspruch. Beweis: Angenommen $\text{WORD}_\text{TM}$ ist entscheidbar. Dann existiert eine TM $\mathcal T$ so, dass $\mathcal T$ $\text{WORD}_\text{TM}$ entscheidet. Wir konstruieren nun eine TM $\mathcal D$ (D wie Diagonalisierung), die wie folgt für die Eingabe $\langle\mathcal M\rangle$ funktioniert:

1. Erstelle $\langle\mathcal M,\langle\mathcal M\rangle\rangle$.
2. Simuliere $\mathcal T$ auf $\langle\mathcal M,\langle\mathcal M\rangle\rangle$.
3. Verwirf, wenn $\mathcal T$ akzeptiert, sonst akzeptiere.

Der Widerspruch ergibt sich, wenn wir $\mathcal D$ die Eingabe $\langle\mathcal D\rangle$ geben.

Falls $\mathcal D$ $\langle\mathcal D\rangle$ akzeptiert dann folgen:

1. $\langle\mathcal D\rangle\in L(\mathcal D)$
2. $\mathcal D$ akzeptiert, weil $\mathcal T$ die Eingabe $\langle\mathcal D,\langle\mathcal D\rangle\rangle$ verwirft, was aber nach der Definition von $\text{WORD}_\text{TM}$ $\langle\mathcal D\rangle\not\in L(\mathcal D)$ impliziert.
3. Widerspruch!

Falls $\mathcal D$ $\langle\mathcal D\rangle$ verwirft dann folgen:

1. $\langle\mathcal D\rangle\not\in L(\mathcal D)$
2. $\mathcal D$ verwirft, weil $\mathcal T$ die Eingabe $\langle\mathcal D,\langle\mathcal D\rangle\rangle$ akzeptiert, was aber nach der Definition von $\text{WORD}_\text{TM}$ $\langle\mathcal D\rangle\in L(\mathcal D)$ impliziert.
3. Widerspruch!