\section{Eine totale WHILE-, aber nicht LOOP-berechenbare Funktion} \inhalta{2-8} \begin{frame} \only
{ Wir haben in den letzten Kapiteln gesehen, dass f\"ur Zahlenfunktionen die Begriffe der Turing-Berechenbarkeit, der WHILE-Berechenbarkeit, der GOTO-Berechenbarkeit und der $\mu$-Rekursivit\"at alle \"aquivalent sind. Au"serdem sind auch die beiden Begriffe der LOOP-Berechenbarkeit und der primitiven Rekursivit\"at \"aquivalent. Ferner ist jede LOOP-berechenbare Funktion WHILE-berechenbar. Der Begriff der WHILE-Berechenbarkeit ist nat\"urlich allgemeiner als der der LOOP-Berechenbarkeit, da es WHILE-berechenbare Funktionen gibt, die nicht f\"ur alle Eingaben definiert sind, w\"ahrend alle LOOP-berechenbaren Funktionen total sind. In diesem Abschnitt wollen wir zeigen, dass auch f\"ur totale Funktionen der Begriff der WHILE-Berechenbarkeit ein umfassenderer Begriff als der der LOOP-Berechenbarkeit ist. Das hei"st, wir wollen eine totale Zahlenfunktion konstruieren, die WHILE-berechenbar, aber nicht LOOP-berechenbar ist. Eine ber\"uhmte, sehr einfach zu definierende totale Funktion, die WHILE-berechenbar, aber nicht LOOP-berechenbar ist, ist 1928 von Ackermann angegeben worden. Sie tr\"agt heute den Namen Ackermannfunktion. Allerdings erfordert der Nachweis, dass sie nicht LOOP-berechenbar ist, eine Reihe von Induktionsbeweisen und Absch\"atzungen. Eine \"ubersichtliche Darstellung findet man in dem Buch `Theoretische Informatik- kurzgefasst' von Sch\"oning. Wir werden in diesem Kapitel eine andere Funktion konstruieren. Die Konstruktion basiert auf einem in der Berechenbarkeitstheorie und Komplexit\"atstheorie wichtigen Konstruktionsprinzip, der Diagonalisierung. } \only{ Zwei übliche Beweise: \begin{itemize} \item Betrachte $A:\nz^2\rightarrow\nz$ (Ackermann, 1926, Rozsa Peter, 1955) mit\pause \GLA A(0,y)&=& y+1\pause\\ A(x{+}1,0)&=& A(x,1)\pause\\ A(x{+}1,y{+}1)&=&A(x,A(x{+}1,y)) \GLE \pause$A$ wächst schnell: \pause$A(4,2)$ hat bereits $\approx$20000 Dezimalstellen...\pause Nachweis der WHILE-Berechenbarkeit: relativ einfach\pause Nachweis der Nicht-LOOP-Berechenbarkeit: komplex \pause (vgl Schöning, S.108-113)\pause \item Alternativer Beweis: \pause Verwende \Fb{Diagonalisierung} als Beweis-/Konstruktionsprinzip \end{itemize} } \end{frame} \begin{frame} \only
{ Zuerst m\"ochten wir alle LOOP-Programme durch endliche W\"orter \"uber einem endlichen Alphabet codieren, zum Beispiel \"uber dem folgenden Alphabet \[A= \{ ~ + ~ - ~ := ~ ; ~ \texttt{LOOP} ~ \texttt{DO} ~ \texttt{END} ~ x ~ 0 ~ 1 ~ \}\] mit 10 Symbolen (hier betrachten wir z.B. \texttt{LOOP} als ein Symbol). Dazu k\"onnen wir Variablen $x_i$ durch '$x~bin(i)$' codieren und Konstanten $c$ durch $bin(c)$. Alle anderen syntaktischen Komponenten von LOOP-Programmen k\"onnen wir einfach \"ubernehmen. Es ist klar, dass dadurch jedes LOOP-Programm durch ein endliches Wort \"uber dem Alphabet $A$ codiert wird. Fortan werden wir diese endlichen W\"orter selbst als LOOP-Programme bezeichnen. Nun k\"onnen wir all diese LOOP-Programme (d.h. alle endlichen W\"orter \"uber dem Alphabet $A$, die LOOP-Programme codieren) nach ihrer L\"ange sortieren und W\"orter gleicher L\"ange alphabetisch sortieren (oder erst alle W\"orter \"uber dem Alphabet $A$ nach der L\"ange sortieren und W\"orter gleicher L\"ange alphabetisch sortieren und aus der entstehenden Liste dann alle W\"orter herausstreichen, die kein LOOP-Programm sind). Dazu m\"ussen wir nur vorab irgendeine Ordnung auf dem Alphabet $A$ festlegen. Wir bekommen dadurch eine Liste aller LOOP-Programme: \[P_0, P_1, P_2, P_3, \ldots\] } \only{Betrachte 10-elementiges Alphabet $A$:\pause \[A:= \{ ~ + ~ - ~ := ~ ; ~ \texttt{LOOP} ~ \texttt{DO} ~ \texttt{END} ~ x ~ 0 ~ 1 ~ \}\] \pause$\Rightarrow$ jedes LOOP-Programm ist als Wort über $A$ schreibbar!\pause (dabei Variable $x_i$ durch '$x~bin(i)$' und Konstante $c$ durch $bin(c)$ ) \pause Bilde Liste $P_0, P_1, P_2, P_3, \ldots$ \emph{aller} LOOP-Programme durch \pause \begin{itemize} \item Sortierung nach Länge des Programmes und \pause \item bei gleicher Länge: Alphabetische Sortierung (mit beliebiger Ordnung auf $A$) \pause \end{itemize} } \begin{lemma}\label{universelles Loop} Die folgende Funktion $g:\nz^2 \rightarrow \nz$ ist WHILE-(Turing-) berechenbar: \pause \begin{quote}$g(i,n) := $ der Wert der einstelligen Zahlenfunktion, \pause\\ die von $P_i$ berechnet wird, \pause bei Eingabe von $n$. \end{quote} \end{lemma} \end{frame} \begin{frame} \only
{ Zum Beweis merken wir an, dass die obige Definition der Liste $P_0, P_1, P_2, P_3, \ldots$ aller LOOP-Programme sicher in dem Sinne effektiv ist, dass man aus dem Index $i $ das Wort $P_i $ berechnen kann, z.B. mit einer Turingmaschine. Um $g(i,n)$ zu berechnen, muss man also bei Eingabe von $i $ und $n $ erst das LOOP-Programm $P_i $ berechnen, dann $P_i $ mit der Eingabe $(0, n , 0, 0, \ldots)$ in den Variablen $x_0, x_1, x_2, x_3, \ldots$ simulieren und den Ausgabewert am Ende der Simulation aus der Variablen $x_0$ herauslesen. Es ist intuitiv einleuchtend, dass man einen entsprechenden Algorithmus entwerfen kann. Dann wird man es auch mit einer Turingmaschine hinbekommen. Also ist die Funktion $g $ Turing-berechenbar und daher auch WHILE-berechenbar. Wir halten au"serdem fest, dass $g$ eine totale Funktion ist, d.h. dass $g(i, n)$ f\"ur alle $i$ und $n$ definiert ist, da das LOOP-Programm $P_i$ bei Eingabe von $n$ nach endlich vielen Schritten anh\"alt. } \only{ Beweis: \pause \begin{itemize} \item aus $i$ kann $P_i$ berechnet werden (mit einer Turingmaschine): \pause \texttt{\small~~~~\begin{tabular}{|l|} \hline$m:=0$\\ \pause FOR $k:=0,1,2,\ldots$ DO \pause\\ ~~FOR $w\in A^*$ mit $|w|=k$ DO \pause \\ ~~~~IF $w$ codiert LOOP-Programm THEN \pause\\ ~~~~~~IF $m=i$ THEN RETURN $w$ END \pause\\ ~~~~~~$m:=m+1$ \pause\\ ~~~~END\\ ~~END\\ END \\\hline \end{tabular}} \item \pause Wenn $P_i$ und $n$ gegeben sind: \pause Die Berechnung von $P_i$ auf $(0,n,0,0,...)$ in den Variablen $x_0,x_1,...$ kann simuliert werden \pause (wieder mit einer Mehrband-Turingmaschine)\pause \item Dabei z.B. $P_i$ auf einen Band gespeichert \pause und alle Variablen, die $P_i$ nutzt, auf einem anderen Band\pause \item Es ist nicht möglich, für jede Variable ein eigenes Band vorzusehen \pause (da die Zahl der Variablen von $P_i$ abhängt)\pause \end{itemize} Also: \pause aus $i$ und $n$ kann das Resultat von $P_i$ auf $n$ berechnet werden\pause\\ $\Rightarrow$ $g$ ist berechenbare (totale) Funktion! } \end{frame} \begin{frame} \only
{ Wir behaupten nun, dass die Funktion $g $ nicht LOOP-berechenbar ist. } \begin{theorem} Die Funktion $g$ aus Lemma \ref{universelles Loop} ist nicht LOOP-berechenbar. \pause Au"serdem gibt es eine totale Funktion $f:\nz\rightarrow\nz$, \pause die WHILE-berechenbar, aber nicht LOOP-berechenbar ist.\pause \end{theorem} \only
{ Eine gew\"unschte Funktion $f $ erhalten wir aus der Funktion $g $ durch eine Diagonalkonstruktion. Wir definieren \[f(n) := g(n,n) + 1\] f\"ur alle nat\"urlichen Zahlen $n$. Da $g $ total ist, ist auch $f $ total. Da $g $ WHILE-berechenbar ist, ist auch $f $ WHILE-berechenbar. W\"are $g $ LOOP-berechenbar, so w\"are auch $f$ LOOP-berechenbar. Wir werden aber nun sehen, dass $f$ nicht LOOP-berechenbar ist. Wir f\"uhren einen Widerspruchsbeweis und nehmen an, $f$ sei doch LOOP-berechenbar. Dann gibt es ein LOOP-Programm $P_j$, das die Funktion $f$ berechnet. Also ist $f(n) = g(j,n)$ f\"ur alle nat\"urlichen Zahlen $n$, insbesondere f\"ur $n = j$. Es gilt also $f(j) = g(j,j)$. Andererseits gilt nach Definition von $f$ auch $f(j) =g(j,j) + 1$. Da die Zahlen $g(j,j)$ und $g(j,j) + 1$ niemals gleich sein k\"onnen (man beachte, dass $g(j,j)$ definiert ist, da $g$ total ist), haben wir einen Widerspruch hergeleitet. Also ist $f $ tats\"achlich nicht LOOP-berechenbar, und daher auch $g $ nicht.} \only{Beweis: Benutze folgende 'Diagonalkonstruktion' einer Funktion $f$: \pause \[f(n) := g(n,n) + 1\] \pause Damit: \begin{itemize} \item $g$ total, \pause also auch $f$ total\pause \item $g$ WHILE-berechenbar, \pause also auch $f$ WHILE-berechenbar\pause \item W\"are $g$ LOOP-berechenbar, \pause so w\"are auch $f$ LOOP-berechenbar. \pause \end{itemize} Annahme: $f$ sei LOOP-berechenbar. \pause \begin{itemize} \item Dann gibt es ein LOOP-Programm $P_j$, das $f$ berechnet.\pause \item Damit gilt $f(n) = g(j,n)$ für alle $n\in \nz$\pause \item Insbesondere auch $f(j) = g(j,j)$\pause \item Nach Definition von $f$ gilt jedoch $f(j) =g(j,j) + 1$\pause \item Widerspruch... \end{itemize} } \end{frame} \begin{frame} \only
{ Diese Beweismethode nennt man Diagonalisierung. Der Begriff Diagonalisierung wird verst\"andlich, wenn man sich die LOOP-Programme $P_0, P_1, P_2, P_3, \ldots$ untereinander schreibt und die Werte der von ihnen berechneten einstelligen Funktionen in den Zeilen daneben: \[\begin{array}{|c|c|c|c|c|c} \hline & 0 & 1 & 2 & 3&\cdots \\ \hline P_0 & \Fb{g(0,0)} & g(0,1) & g(0,2) & g(0,3) \\ \hline P_1 & g(1,0) & \Fb{g(1,1)} & g(1,2) & g(1,3) \\ \hline P_2 & g(2,0) & g(2,1) & \Fb{g(2,2)} & g(2,3) \\ \hline P_3 & g(3,0) & g(3,1) & g(3,2) & \Fb{g(3,3)} \\ \hline \vdots&&&&& \end{array}\] Die Funktion $f $ wird gerade so definiert, dass sie sich in der Diagonale von all diesen Funktionen unterscheidet. Von der $i$-ten LOOP-berechenbaren einstelligen Funktion, n\"amlich von der von $P_i $ berechneten einstelligen Funktion, unterscheidet sie sich gerade bei dem Eingabewert $i$. Das gilt f\"ur alle $i$. } \only{ Damit: $f$ nicht LOOP-berechenbar, \pause\\ also auch $g$ nicht LOOP-berechenbar\pause Idee der \Fb{Diagonalisierung}: \pause Betrachte Diagramm aller Werte $g(i,n)$:\pause \[\begin{array}{|c|c|c|c|c|c} \hline i \backslash n & 0 & 1 & 2 & 3&\cdots \\ \hline P_0 & \Fb{g(0,0)} & g(0,1) & g(0,2) & g(0,3) \\ \hline P_1 & g(1,0) & \Fb{g(1,1)} & g(1,2) & g(1,3) \\ \hline P_2 & g(2,0) & g(2,1) & \Fb{g(2,2)} & g(2,3) \\ \hline P_3 & g(3,0) & g(3,1) & g(3,2) & \Fb{g(3,3)} \\ \hline \vdots&&&&&\pause\\ \multicolumn{6}{c}{} \\\hline f(n) &g(0,0){+}1 & g(1,1){+}1 & g(2,2){+}1 & g(3,3) {+}1&\cdots \\\hline\end{array}\] \pause $f$ wird so definiert, dass $f$ sich in der Diagonale von jeder der Funktionen unterscheidet. } \end{frame}