%% -*- mode: latex; TeX-master: "informatik.tex"; -*-


\begin{slide}{Algorithmisch unlösbare Probleme (1)}

\kopf{$ $Id: halte.tex,v 1.1 2006-10-09 13:24:19 waldmann Exp $ $}

Behauptung: es gibt algorithmisch unlösbare Probleme.

Das sind wohldefinierte Aufgabenstellungen
mit wohldefinierter Lösung, welche aber \emph{nicht}
durch Algorithmus gefunden werden kann.

\end{slide}

\begin{slide}{Alg. unlösb. Probleme (2)}

Hilfsmittel: Aufzählung (Numerierung) aller Programme

(\dots, die aus \emph{einer} Eingabe \emph{eine} Ausgabe berechnen.)

Da Algorithmen (Programme) beschreibungs-endlich sind,
können wir sie auch durchnumerieren:

Z. B. Java-Quelltexte erst der Länge nach
und innerhalb der Länge alphabetisch.
Die syntax- und typ-fehlerbehafteten Texte streichen wir,
übrig bleibt eine Anordnung 
$$ P_0, P_1, \ldots $$
aller tatsächlich kompilier- und ausführbaren Programm-Texte.

\end{slide}

\begin{slide}{Algorithmisch unlösbare Probleme (3)}

\kopf{$ $Id: halte.tex,v 1.1 2006-10-09 13:24:19 waldmann Exp $ $}

Es gibt Rechnungen, die \emph{halten},
und Rechnungen, die \emph{nicht halten}
(z. B. \glqq Endlos-Schleifen\grqq).

\bigskip

Das \emph{Halteproblem} ist:
\begin{itemize}
\item Eingabe: ein Zahl $x$ und eine Zahl $y$ 
\item Frage: hält das Programm $P_x$ bei Eingabe $y$?
\end{itemize}
Wir beweisen, daß das \emph{nicht entscheidbar} ist:
es gibt keinen Algorithmus, 
der diese Frage für alle Eingaben $(x,y)$ korrekt beantwortet.

\bigskip

Diskussion: wir könnten einfach die Rechnug von $P_x$ auf $y$
starten. Aber \dots wann können wir sie abbrechen?

\end{slide}

\begin{slide}{Algorithmisch unlösbare Probleme (4)}

Indirekter Beweis: Falls das Halteproblem doch algorithmisch
lösbar ist:

Dann definieren wir das Programm 

$H: x \mapsto
\left\{
\begin{minipage}{0.8\textwidth}
  \begin{tabular}{lp{0.8\textwidth}}
    \textbf{falls} & $P_x(x)$ (Rechnung des Programms mit Nummer $x$
    für Eingabe $x$) \textbf{hält}, \\
    \textbf{dann} & irgendeine nicht haltende  Rechnung (Schleife), \\
    \textbf{sonst} & ein haltende Rechung (return 0).
  \end{tabular}
\end{minipage}  
\right.$

Das Programm $H$ hat auch eine Nummer, diese sei $n$. 

Also $H = P_n$.

Hält $H(n)$? 

\newpage 

Wegen der Fallunterscheidung gilt

$H(n)$ hält $\iff$ $H(n)=0$ 
$\iff$ $P_n(n)$ hält nicht $\iff$ $H(n)$ hält nicht!

Das ist ein Widerspruch, d. h. (wenigstens) eine Annahme war falsch:

Die Funktion $H$ ist völlig korrekt definiert,
aber \emph{es gibt keinen Algorithmus, der $H$ berechnet}.

\end{slide}

\begin{slide}{Alg. unl. Probleme (5)}

der gegebene Beweis beruht auf Ideen von
\begin{itemize}
\item
  Georg Cantor (Diagonalisierung, es gibt überabzählbare Mengen)
\item
  Kurt Gödel (Unvollständigkeitssätze, Grenzen der Formalen Logik)
\item
  Alan Turing (allgemeines Maschinenmodell, Grenzen von Algorithmen)
\end{itemize}

\bigskip

Die Aussage gilt für \emph{jede} Programmiersprache

(\dots, in der man die Funktion $x \mapsto P_x(x)$ programmieren kann)


\end{slide}

\begin{slide}{PCPs und Programme}

Betrachte
\( 
\begin{array}{c|c|c|c}
  abbb & ccc & ddd & d  \\ \hline
  a    & b   & c   & dd
\end{array}
\)

$\Rightarrow$ mit PCPs kann man \glqq rechnen\grqq.

$\Rightarrow$ man kann jedes Programm in PCPs übersetzen.

Eigenschaften von PCPs (z. B. Lösbarkeit) 
sind  (wenigstens) genauso schwer 
wie Eigenschaften von Programmen (z. B. Halteproblem).


Halteproblem algorithmisch unlösbar \\
$\Rightarrow$ PCP algorithmisch unlösbar.

Indiz: sehr kleine
und trotzdem schwere PCP-Instanzen
(d. h. mit sehr langer Lösung).

\url{http://www.theory.informatik.uni-kassel.de/~stamer/pcp/}

\end{slide}
