Problemreduktion

Aus ProgrammingWiki

Nachweis der Unentscheidbarkeit einer Sprache

Aufgabe 6.3

Z.z.: Unentscheidbarkeit der Menge $L_{\Sigma^*}=\{\langle M\rangle\mid L(M)=\Sigma^*\}$.
Methode: Reduktion des Halteproblems $L_H=\{\langle M\rangle w\mid L(M)=M(w)\}$ auf $L_{\Sigma^*}$
Beweis: Die Reduktionsmaschine $M_2$ erzeugt aus $\langle M\rangle w$ das Wort $\langle M'\rangle$. Die TM $M'$ erwartet ein Eingabewort $y$, das sie aber vollständig ignoriert: $M'$ löscht $y$ und schreibt $w$ auf das Band und stellt den Kopf auf das erste Zeichen von $w$. Anschließend verhält sich $M'$ genau so, wie $M$ angesetzt auf $w$.
Sei $M_1$ die TM, die die Sprache $L_{\Sigma^*}$ entscheidet (und deren Existenz wir zunächst annehmen). $M_1$ gibt für das Eingabewort $\langle M'\rangle$ genau dann wahr aus, wenn $M'(y)$ stoppt, d.h. wenn $M(w)$ stoppt, anderenfalls falsch.
Damit entscheidet die Verkettung $M_1\circ M_2$ gerade die Menge $L_H$. Da das Halteproblem jedoch nicht lösbar ist, ist auch $L_{\Sigma^*}$ unentscheidbar.