Problemreduktion

Reduktion

Aufgabe 6.3

Z.z.: Unentscheidbarkeit der Menge L_{\Sigma^*}=\{<M>|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.