BuK/IIm20/Vorlesung 7 Nerlich

Wiki-Quelltext dieser Seite.

<language>Python</language>
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) =

[[Datei:Pn21fere_Uu_deduplification.svg]]


= $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)