Problemreduktion

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.