Problemreduktion

Reduktion

Aufgabe 6.3

Z.z.: Unentscheidbarkeit der Menge L_{\Sigma^*}=\{\langle M\rangle\mid L(M)=\Sigma^*\}.
Methode: Reduktion des Halteproblems L_H=\{<M>w|L(M)=M(w)\} auf L_{\Sigma^*}
Beweis: M_2 erzeugt aus <M>w das Wort <M'>. Die TM M' erwartet ein Eingabewort y, das sie aber vollständig ignoriert: M' löscht y und schreibt w auf das Band. Anschließend verhält sich M' genau so, wie M angesetzt auf w.