BuK/IIm20/Vorlesung 7 Nerlich

Wiki-Quelltext dieser Seite.

<language>Python</language>
https://md.fachschaften.org/ba9RY_KYRWKeHm9tlZJJdA

= Reduktionsmaschine $M_2$ (S.15/16) =

[[Datei:Pn21fere_Automaton_uu_deduplification.json]]

[[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)