https://md.fachschaften.org/ba9RY_KYRWKeHm9tlZJJdA

Reduktionsmaschine M_2 (S.15/16)

Pn21fere_Automaton_uu_deduplification.json

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)