Aus ProgrammingWiki

https://md.fachschaften.org/ba9RY_KYRWKeHm9tlZJJdA

Inhaltsverzeichnis 1 Satz von Rice 2 Reduktionsmaschine $M_2$ (S.15/16) 3 $P$ unentscheidbar $\wedge\ P \geq P' \Rightarrow P'$ unentscheidbar (S.17) 4 Unentscheidbarkeitsbeweis (S. 25)

Satz von Rice

"Die Sprache $L_E$ ist im Allgemeinen nicht entscheidbar, wenn $E$ eine nichttriviale Eigenschaft von $L(M)$ ist."

Behauptung (Bedeutung "im Allgemeinen"): "Die Menge der nichttrivialen Eigenschaften $E$, für die $L_E$ nicht entscheidbar ist, ist mächtiger als die Menge der nichttrivialen Eigenschaften, für die $L_E$ entscheidbar ist." $\hspace{5mm}{\Large\unicode{x21af}}$

"Wir können keine quantitativen Aussagen über die Menge der entscheidbaren oder nicht entscheidbaren Sprachen $L_E$ treffen."

Warum dann Unterscheidung zu "Es gibt nichttriviale Eigenschaften $E$, für die $L_E$ entscheidbar ist."?

Reduktionsmaschine $M_2$ (S.15/16)

$P$ unentscheidbar $\wedge\ P \geq P' \Rightarrow P'$ unentscheidbar (S.17)

Kontraposition: $(A \wedge B) \rightarrow C \Leftrightarrow (\neg C \wedge B) \rightarrow \neg A$

$\begin{alignat*}{3} A \wedge B &\longrightarrow C &&|\ \neg\\ \neg A \vee \neg B &\longleftarrow \neg C &&|\ B = false?\\ A \vee \neg A &\longleftarrow \neg C \wedge \neg B &\hspace{1cm} &|\ B = true?\\ \neg A &\longleftarrow \neg C \wedge B &\square\ & \end{alignat*}$

Unentscheidbarkeitsbeweis (S. 25)

$L(M) = \Sigma^\ast$ (→ $M$ akzeptiert jedes mögliche Eingabewort)

$L_{\Sigma^\ast}$ (→ Sprache/Menge aller Turingmaschinen-Kodierungen, für die die obige Eigenschaft gilt)

Behauptung: $L_{\Sigma^\ast}$ unentscheidbar

→ Beweis durch Reduktion des $L_H$ (Halteproblem) auf $L_{\Sigma^\ast}$

$L_H := \{\langle M \rangle w ~|~ M$ hält für die Eingabe $w \}$

• Higher Order Procedures (Kodierung des Wortes in die Maschine $M'$ selbst, Ignorieren eines Folgewortes)