Berechenbarkeitstheorie/Problemreduktion

Wiki-Quelltext dieser Seite.

== Reduktion ==
=== Aufgabe 6.3 ===
Z.z.: Unentscheidbarkeit der Menge $L_{\Sigma^*}=\{\langle M\rangle\mid L(M)=\Sigma^*\}$.<br />
Methode: Reduktion des Halteproblems $L_H=\{\langle M\rangle w\mid L(M)=M(w)\}$ auf $L_{\Sigma^*}$<br />
Beweis: $M_2$ erzeugt aus $<M>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. Anschließend verhält sich $M'$ genau so, wie $M$ angesetzt auf $w$.<br />
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 <nowiki>wahr</nowiki> aus, wenn $M(w)$ stoppt, anderenfalls <nowiki>falsch</nowiki>. <br />
Damit entscheidet die Verkettung $M_1\circle M_2$ gerade die Menge $L_H$. Da das Halteproblem nicht lösbar ist, ist auch $L_{\Sigma^*}$ unentscheidbar.