\section{Eine totale WHILE-, aber nicht LOOP-berechenbare Funktion}
\inhalta{2-8}
\begin{frame}
\only<article>{
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<presentation>{
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<article>{
 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<presentation>{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<article>{
 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<presentation>{
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<article>{ 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<article>{ 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<presentation>{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<article>{
 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<presentation>{
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}
