Berechenbarkeitstheorie/Problemreduktion

Wiki-Quelltext dieser Seite.

=== Nachweis der Unentscheidbarkeit einer Sprache ===
==== 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: 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$.<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 <tt>wahr</tt> aus, wenn $M'(y)$ stoppt, d.h. wenn $M(w)$ stoppt, anderenfalls <tt>falsch</tt>. <br />
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.