Berechenbarkeitstheorie/Problemreduktion

Wiki-Quelltext dieser Seite.

== Reduktion ==
=== Aufgabe 6.3 ===
Z.z.: Unentscheidbarkeit der Menge $L_{\Sigma^*}=\{<M>|L(M)=\Sigma^*\}$.<br />
Methode: Reduktion des Halteproblems $L_H=\{<M>w|L(M)=M(w)\}$ auf $L_{\Sigma^*}$<br />
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$.