https://md.fachschaften.org/ba9RY_KYRWKeHm9tlZJJdA

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)