\begin{slide}{Logik und Unentscheidbarkeit (I)}

Def: das Gültigkeitsproblem der Prädikatenlogik:
\begin{itemize} \itemsep 2pt
\item 
Eingabe: eine prädikatenlogische Formel $F$ über $\Sigma$,
\item
Frage: ist $F$ in $\Term(\Sigma)$ allgemeingültig
\end{itemize}

Beispiel: $\Sigma$: zwei einstellige Funktionsymbole $f,g$, \\
ein nullstelliges Funktionssymbol $a$, \\
ein zweistelliges Prädikatsymbol $R$. 
%
\begin{eqnarray*}
& & \forall x,y: R(x,y) \rightarrow
\left(\begin{array}{lr}
& R(f(x),g(f(f(y)))) \\
\wedge & R(g(x),f(y))\\
 \wedge & R(g(f(f(x))),g(y)) 
\end{array}
\right) \\
& \wedge & R(a,a) \wedge \exists z: R(g(z),g(z))
\end{eqnarray*}

\end{slide}

\begin{slide}{Logik und Unentscheidbarkeit (II)}
Satz: Das Gültigkeitsproblem der Prädikatenlogik ist unentscheidbar.

(Kurt Gödel, Alan Turing.
\url{http://thocp.net/biographies/papers/turing_oncomputablenumbers_1936.pdf})


\bigskip
Beweis:
\begin{itemize}
\item 
  Halteproblem für TM ist unentscheidbar
\item
  Halteproblem $\le$ Postsches Korrespondenzproblem (PCP)
\item
  PCP $\le$ Gültigkeitsproblem
\end{itemize}
verwendet \emph{Reduktion} $A \le B :\iff$ \\
$\exists \text{TM-berechenbares} f: 
\forall x: x\in A \iff f(x)\in B$.



\end{slide}
