\section{Primitiv rekursive und $\mu$-rekursive Funktionen}
\inhalta{1-7}
\only<article>{
 Wir haben die berechenbaren Zahlenfunktionen bisher durch 
 Turingmaschinen und durch WHILE-Programme charakterisiert.
  Au"serdem haben wir die Klasse der durch LOOP-Programme 
  berechenbaren Funktionen eingef\"uhrt. 
In diesem Abschnitt wollen wir eine weitere Charakterisierung 
der berechenbaren Zahlenfunktionen kennenlernen. 
Wir werden die Klasse der sogenannten primitiv rekursiven Funktionen 
und die Klasse der sogenannten $\mu$-rekursiven Funktionen definieren 
und beweisen, dass die primitiv rekursiven Funktionen genau die 
LOOP-berechenbaren Funktionen sind und die $\mu$-rekursiven genau die 
WHILE-berechenbaren. Beide Funktionenklassen werden dadurch definiert, 
dass wir von einer Menge von Grundfunktionen ausgehen und eine 
Zahlenfunktion primitiv rekursiv bzw. $\mu$-rekursiv
nennen werden, wenn man sie aus den Grundfunktionen 
durch endlich h\"aufige Anwendung einiger einfacher Operatoren bzw. 
Erzeugungsschemata gewinnen kann. Dabei lassen wir bei den $\mu$-
rekursiven Funktionen einen Operator 
mehr zu als bei den primitiv rekursiven Funktionen.
}


\begin{frame}
\only<article>{Wir werden im Folgenden aus formalen Gr\"unden auch 
nullstellige Zahlenfunktionen betrachten, also Funktionen 
$f: \nz^k\Partial  \nz$
 mit $k = 0$. Dies sind einfach Funktionen ohne Eingabe, 
 die einen festen Wert liefern, also Konstanten. Man beachte, 
 dass es einen formalen Unterschied macht, 
 ob man die nullstellige Funktion mit Wert $7$ betrachtet, 
 also die Konstante $7$, oder die zweistellige Funktionen, 
 die bei jeder Eingabe $(x,y)$ den Wert $7$ ausgibt. 
}
\only<presentation>{
Im Folgenden:\\
Anderer Zugang zu Berechenbarkeit von 
$f: \nz^k\rightarrow  \nz$ für $k\in\nz$\pause


Dabei auch $k=0$ erlaubt! \pause
$\Rightarrow$ Nullstellige Funktion, Konstante\pause

Beachte Unterschied \pause z.B bei \GLA f:\nz^0\rightarrow \nz&\textrm{  mit }&f()=42\pause\\
 g:\nz^2\rightarrow\nz&\textrm{ mit }&(\forall x,y)~g(x,y)=42\GLE

\pause In Programmiersprachen:\\ \pause\texttt{int f()} und
\texttt{int g(int,int)} haben verschiedenen Typ!\pause
}

\only<article>{ Die folgenden Funktionen sind unsere Grundfunktionen, 
 die wir von vornherein primitiv rekursiv nennen wollen:}
\only<presentation>{Nutze folgenden Grundstock an sehr einfachen Funktionen:\pause}
\begin{itemize}
\item $Z:\nz^0\rightarrow\nz$, \pause die nullstellige Funktion (=Konstante) mit $Z()=0$\pause
\item $S:\nz^1\rightarrow\nz$, \pause die einstellige Nachfolgerfunktion mit $S(n)=n+1$\pause
\item $pr^k_j:\nz^k\rightarrow\nz$, \pause die $k$-stellige Projektion auf die $j$-te Komponente, \pause
 also $pr^k_j(x_1,..., x_k) = x_j$, \pause  definiert f\"ur 
$k\geq 1$  und $1\leq j \leq k$.
\end{itemize}

\end{frame}



\only<article>{
 Jetzt f\"uhren wir zwei Erzeugungsschemata ein, 
 mittels derer man aus gegebenen Zahlenfunktionen neue Zahlenfunktionen erh\"alt.\pause

\begin{itemize}
\item Das Kompositionsschema $Komp: (g_1,...,g_m,h)\mapsto f$ 
 erzeugt aus $m$  $k$-stelligen Funktionen $g_1$,...,$g_m$ und einer $m$-stelligen Funktion $h$
 eine $k$-stellige Funktion $f$ mit
     \[f(x_1,..., x_k) := h(g_1(x_1,..., x_k),...,g_m(x_1,..., x_k))\]
Dabei ist $m\geq 1$ und $k \geq 0$. 
\item
 Das Rekursionsschema $PrRek: (g,h)\mapsto f$ der primitiven Rekursion erzeugt aus einer 
 $k$-stelligen Verankerungsfunktion $g$ und einer $(k{+}2)$-stelligen 
 Funktion $h $ eine neue (rekursiv definierte) $(k{+1})$-stellige Funktion $f$ mit
\GLA
f(x_1,..., x_k, 0) &:=& g(x_1,..., x_k) \\ 
f(x_1,..., x_k, y{+}1) &:=& h(x_1,..., x_k, y,f(x_1,..., x_k, y))
\GLE  
Dabei ist  $k\geq 0$.
\end{itemize}}

\only<presentation>{\begin{frame}
Mit Erzeugungsschemata  neue Funktionen aus gegebenen Zahlenfunktionen:\pause


\Fb{Kompositionsschema} $Komp: (g_1,...,g_m,h)\mapsto f$ \pause
\begin{itemize}
\item  
gegeben: \pause $m$ Stück $k$-stellige Funktionen $g_1$,...,$g_m$  \pause
\\ und eine $m$-stellige Funktion $h$ \pause
\item erzeugt: \pause
 eine $k$-stellige Funktion $f$  \pause mit
     \[f(x_1,..., x_k) := h(g_1(x_1,..., x_k),...,g_m(x_1,..., x_k))\]
 \pause Dabei ist $m\geq 1$ und $k \geq 0$.  \pause
\end{itemize}
 \Fb{Rekursionsschema} $PrRek: (g,h)\mapsto f$  \pause(für 'primitive Rekursion') \pause
\begin{itemize}
\item  
gegeben:   \pause eine  $k$-stellige Verankerungsfunktion $g$ \pause\\
 und eine $(k{+}2)$-stellige (Rekursions-)Funktion $h$  \pause
\item  
erzeugt: \pause eine (rekursiv definierte) $(k{+1})$-stellige Funktion $f$  \pause mit
\GLA
f(x_1,..., x_k, 0) &:=& g(x_1,..., x_k)  \pause\\ 
f(x_1,..., x_k, y{+}1) &:=& h(x_1,..., x_k, y,f(x_1,..., x_k, y))
\GLE  
 \pause Dabei ist  $k\geq 0$.
\end{itemize}
\end{frame}}

\begin{frame}
\only<article>{
 Damit k\"onnen wir die Funktionsklasse der 
 primitiv rekursiven Funktionen definieren: }

\begin{definition}
 Die Menge der \Fb{primitiv rekursiven Funktionen} besteht 
 genau aus den Funktionen, die sich \pause aus der Menge 
 der Grundfunktionen \pause durch endlich oft wiederholte 
 Anwendung des Kompositionsschemas \pause und des Rekursionsschemas bilden lassen. \pause 
\end{definition}

 Bemerkungen:\pause 

\begin{itemize}
\item 'Endlich oft wiederholbar' umfasst auch nullfache Wiederholung.\pause \\
 Die Grundfunktionen selbst sind also auch primitiv rekursiv.\pause 
\item Man kann die neue Klasse auch als kleinste Funktionenklasse definieren, \pause die die Menge der Grundfunktionen enth\"alt \pause  und unter den Anwendungen der beiden Schemata abgeschlossen ist.
\end{itemize}
\end{frame}

\begin{frame}
Formaler kann man die Klasse auch folgenderma"sen definieren:\pause 
\begin{enumerate}
\item  Alle Grundfunktionen sind primitiv rekursiv.\pause 
\item Sind $m$
 $k$-stellige Funktionen $g_1$,...,$g_m$
 primitiv rekursiv\pause\\  und eine $m$-stellige Funktion $h$
 ebenfalls primitiv rekursiv, \pause\\  
 so ist auch die im Kompositionsschema definierte $k$-stellige Funktion 
 $f=Komp(g_1,...,g_m,h)$ primitiv rekursiv.\pause 
\item Sind eine $k$-stellige Funktion $g$ und eine $(k{+}2)$-stellige Funktion $h$
 primitiv rekursiv,\pause\\ so ist auch die im Rekursionsschema definierte 
 $(k{+}1)$-stellige Funktion $f=PrRek(g,h)$ primitiv rekursiv.\pause
\item  Weitere primitiv rekursive Funktionen gibt es nicht.\pause
\end{enumerate}

\only<article>{Wir ersparen es uns, formal nachzuweisen, dass durch das Rekursionsschema $PrRek$  wirklich eine Funktion definiert wird.

Da die Grundfunktionen alle total sind und das Kompositionsschema und das Rekursionsschema aus totalen Funktionen wieder totale Funktionen erzeugen, sind alle primitiv rekursiven Funktionen total.}

\only<presentation>{\begin{itemize}
\item Rekursionsschema $PrRek$  definiert wirklich eine Funktion!\pause
\item Alle primitiv rekursiven Funktionen sind total!
\end{itemize}}
\end{frame}



\begin{frame}
\only<article>{
Man kann primitive Rekursivit\"at auch f\"ur charakteristische Funktionen und Pr\"adikate definieren:

Eine Teilmenge $T$ der nat\"urlichen Zahlen kann durch ihre charakteristische 
 Funktion $ch_T:\nz\rightarrow\nz$ charakterisiert werden:
\[ch_T(x) = \left\{\begin{array}{l}1\textrm{ f\"ur }x\in T\\
 0\textrm{ sonst}\end{array}\right.\]
 Dieses Konzept kann auf Teilmengen aus  $\nz^k$
 ausgedehnt werden. 
 Insofern kann man von primitiv rekursiven Mengen reden, 
 wenn die zugeh\"origen charakteristischen Funktionen primitiv rekursiv sind. 

Oftmals werden Mengen auch durch Pr\"adikate definiert:
Ein Prädikat $P$ ist eine Funktion $P:\nz\rightarrow\{\textrm{true},\textrm{false}\}$.

Dann ist $\{x\mid P(x)=\textrm{true}\}$ eine Menge. Damit  kann der Begriff 'primitiv rekurisv'
auch auf Pr\"adikate ausgedehnt werden:

$P$ heißt primitiv rekursiv, wenn die folgende Funktion $f_P$ primitiv rekusiv ist:
\[f_P(x) = \left\{\begin{array}{l}1\textrm{ falls }P(x)=\textrm{ true}\\
 0\textrm{ falls }P(x)=\textrm{ false}\end{array}\right.\]
 Mit Hilfe der \emph{charakteristischen}
 Funktionen kann man auch einfach die Negation eines 
 Pr\"adikates, die Disjunktion und die Konjunktion ausdr\"ucken, die in der 
Mengenlehre \"uber die Vereinigung und den Durchschnitt analog definiert werden.
Daher \"ubertr\"agt sich die primitive Rekursivit\"at auch auf diese 
abgeleiteten Pr\"adikate.
}
\only<presentation>{
primitive Rekursivit\"at f\"ur charakteristische Funktionen und Pr\"adikate:\pause

 'charakteristische 
 Funktion' $ch_T:\nz\rightarrow\nz$ für Menge $T\subseteq \nz$:\pause
\[ch_T(x) = \left\{\begin{array}{l}1\textrm{ f\"ur }x\in T\pause\\
 0\textrm{ sonst}\end{array}\right.\]
\pause Analog für Teilmengen aus  $\nz^k$...
\pause

Damit: \\\pause
$T\subseteq\nz^k$ heißt primitiv rekursiv, \pause wenn $ch_T$ primitiv rekursiv ist...\pause

Alternativer Zugang zu Mengen: \pause 
über 'Pr\"adikate' $P\pause:\nz\rightarrow\{\textrm{true},\textrm{false}\}$\pause


Ein Prädikat $P$ heißt primitiv rekursiv, wenn die folgende Funktion $f_P$ primitiv rekusiv ist:\pause
\[f_P(x) = \left\{\begin{array}{l}1\textrm{ falls }P(x)=\textrm{ true}\pause\\
 0\textrm{ falls }P(x)=\textrm{ false}\end{array}\right.\]
\pause Mit Hilfe der charakteristischen
 Funktionen: \pause

Für primitiv rekursive $P_1$, $P_2$ sind auch
 $P_1\vee P_2$,  $P_1\wedge P_2$ und $\neg P_1$ primitiv rekursiv!
}
 \end{frame}



\begin{frame}
\begin{example}
\begin{itemize}
\item[(a)]
\only<article>{ Die nullstellige Funktion $Z$
mit Wert $0$ ist eine Grundfunktion. 

Die nullstellige Funktion $c^{(0)}_1$ mit Wert $c^{(0)}_1()=1$ erh\"alt man durch Komposition der 
Nachfolgerfunktion und der nullstelligen Funktion mit Wert $0$: es gilt $S(0) = 1$,
d.h. $c^{(0)}_1=Komp(Z,S)$.
Also die Funktion  $c^{(0)}_1$  auch primitiv rekursiv. 

Durch Induktion zeigt man ebenso, dass f\"ur jede nat\"urliche Zahl $m$ 
die nullstellige Funktion $c^{(0)}_m$ mit Wert $m$ primitiv rekursiv ist.}
\only<presentation>{Betrachte $c^{(0)}_1:=Komp(Z,S)$:\pause

Stelligkeiten passen zusammen, \pause

Resultat  $c^{(0)}_1$ ist nullstellig, \pause mit $c^{(0)}_1()=1$\pause

d.h. $c^{(0)}_1$ ist nullstellige Konstante mit Wert $1$\pause

Analog:  \pause nullstellige Konstante $c^{(0)}_m$ mit Wert $m$ \pause durch
\[c^{(0)}_m=\underbrace{Komp(Komp(...Komp}_m(Z,S),...,S),S)\]
}

\item[(b)]\only<article>{ Sei $m$ irgendeine nat\"urliche Zahl. Mit 
 der nullstelligen konstanten Funktion $g=c^{(0)}_m$ mit Wert $m$ und 
 $h= pr^2_2$ erh\"alt man mit dem Rekursionsschema daraus die 
 einstellige konstante Funktion $c^{(1)}_m$ mit Wert $m$: Bei $c^{(1)}_m:=PrRek(g,h)$ 
ist stets $c^{(1)}_m(x)=m$} 
\only<presentation>{\pause
Betrachte $c^{(1)}_m:=PrRek(c^{(0)}_m\pause,pr^2_2)$\pause

Stelligkeiten passen wieder zusammen,\pause

Resultat $c^{(1)}_m(0)\pause=c^{(0)}_m()\pause=m$\pause, $c^{(1)}_m(n+1)\pause=c^{(1)}_m(n)\pause=...=m$\pause

d.h. $c^{(1)}_m$ ist einstellige Konstante mit Wert $m$
} \end{itemize}
\end{example}
\end{frame}
\only<article>{
\begin{frame}
\begin{cont}{}
\begin{itemize}
\item[(c)] Sei $m$
irgendeine nat\"urliche Zahl und $k \geq 1$. 
Aus der einstelligen konstanten Funktion $c^{(1)}_m$ mit Wert $m$
und der Funktion $pr^k_1$ 
erh\"alt man durch Substitution die $k$-stellige 
konstante Funktion mit Wert $m$.

\item[(d)] Die identische Funktion $id:\nz\rightarrow \nz$
ist primitiv rekursiv, denn sie ist nichts anderes 
als die Grundfunktion $pr^1_1$.

\item[(e)] Die Addition kann rekursiv durch $add(x, 0) = x $
und $add(x,  y+ 1) = S(add(x, y))$ definiert werden.
 
Formal erh\"alt man sie mit dem Rekursionsschema aus der einstelligen 
primitiv rekursiven Funktion $g = id$ 
und der 3-stelligen primitiv rekursiven Funktion $h=S(pr^3_3)$. 

Also ist die Additionsfunktion primitiv rekursiv.
\end{itemize}
\end{cont}
\end{frame}}

\only<presentation>{\begin{frame}
\begin{cont}{}
\begin{itemize}
\item[(c)] Betrachte $c^{(k)}_m:=Komp(pr^k_1,c^{(1)}_m)$:\pause

$k$-stellige \pause
konstante Funktion \pause mit Wert $m$\pause\\

\item[(d)] Identität  $id:\nz\rightarrow \nz$ \pause
ist primitiv rekursiv:\pause

$id=pr^1_1$\pause, d.h. $id$ ist Grundfunktion\pause\\

\item[(e)] Rekursive Definition der  Addition:\pause
\GLA add(x, 0) &=& x \pause\\
add(x,  y{+}1) &=& S(add(x, y))
\GLE
\pause Damit \[add=PrRek(id\pause ,Komp(pr^3_3\pause,S))\]
\end{itemize}
\end{cont}
\end{frame}}



\only<article>{
\begin{cont}{}
\begin{itemize}

\item[(f)] \"Ahnlich sieht man, dass auch die 
 Multiplikationsfunktion primitiv rekursiv ist. Es gilt n\"amlich 
 $mult(x,0) = 0$ und $mult(x, y+ 1) = add(x, mult(x, y))$. 

 Also erh\"alt man $mult $
durch Anwendung des Rekursionsschemas auf
\begin{itemize}\item
 $g $ = die einstellige konstante Funktion mit Wert 0
\item
   $h = add(pr^3_1,pr^3_3)$, 
   eine 3-stellige Funktion, die man wiederum durch 
   Komposition aus den Grundfunktionen $pr^3_1$,$ pr^3_3$ 
   und der schon als primitiv rekursiv erkannten Funktion $add $
erh\"alt. 
\end{itemize}
\item[(g)] Die Vorg\"angerfunktion $V:\nz\rightarrow \nz$
ist durch $V(0) := 0$ und $V(n+1) := n$
  definiert. 
  Also erh\"alt man sie mit dem Rekursionsschema aus $g =Z $
 und $h = pr^2_1$.

\end{itemize}
\end{cont}}

\only<presentation>{
\begin{frame}
\begin{cont}{}
\begin{itemize}

\item[(f)] Rekursive Definition der  Multiplikation:\pause
\GLA mult(x, 0) &=& 0 \pause\\
mult(x,  y{+}1) &=& add(x,mult(x, y))
\GLE

\pause Damit \[mult=PrRek(c_0^{(1)}\pause ,Komp(pr^3_1\pause,pr^3_3\pause,add))\pause\]


\item[(g)] Vorg\"angerfunktion $V:\nz\rightarrow \nz$ \pause mit
\GLA  V(0) &=& 0\\
V(n{+}1) &=& n
\GLE
\pause Damit \[V=PrRek(Z,pr^2_1)\]
\end{itemize}
\end{cont}
\end{frame}}


\only<article>{\begin{frame}
\begin{cont}{}
\begin{itemize}

\item[(h)] Die modifizierte Subtraktion $sub:\nz
 \rightarrow  \nz$
mit 
\[sub
(x,y) = \left\{\begin{array}{ll}x - y,&\textrm{ falls }x \geq y\\
0,&\textrm{  falls }x < y
\end{array}\right.\] 


erf\"ullt die Gleichungen $sub(x,0) = x$ und 
$sub(x,y+1) = V(sub(x,y))$. Also erh\"alt man sie mit dem Rekursionsschema 
aus den primitiv rekursiven Funktionen $id$ und $V(pr^3_3)$.

\item[(i)] Die Vorzeichenfunktion 
 $sg:\nz\rightarrow  \nz$
ist primitiv rekursiv, denn 
$sg(0) = 0$ und $sg(y+1) = 1$ f\"ur alle $y$.
\end{itemize}
\end{cont}
\end{frame}}


\only<presentation>{\begin{frame}
\begin{cont}{}
\begin{itemize}

\item[(h)]modifizierte Subtraktion $sub:\nz
 \rightarrow  \nz$ \pause 
mit 
\GLA sub
(x,y) &=& \left\{\begin{array}{ll}x - y,&\textrm{ falls }x \geq y\\
0,&\textrm{  falls }x < y
\end{array}\right.\pause \\
\textrm{d.h.~~~}sub(x,0) &=& x\pause \\
sub(x,y+1) &=& V(sub(x,y))\GLE
\pause Damit \[sub=PrRek(id,\pause Komp(pr^3_3,V))\pause\]
\item[(i)] Vorzeichenfunktion 
 $sg:\nz\rightarrow  \nz$ \pause mit
\GLA sg(0) &=& 0\\
sg(n+1) &=& 1\GLE
\pause Damit 
\[sg=PrRek(Z,c^{(2)}_1)\]
\end{itemize}
\end{cont}
\end{frame}}



\only<article>{\begin{frame}

\begin{example}
 Wir werden etwas sp\"ater ein weiteres Erzeugungsschema 
 definieren, das zu den $\mu$-rekursiven Funktionen
f\"uhren wird. Man kann es als Realisierung einer 
unbeschr\"ankten Nullstellensuche bezeichnen. 
Hier wollen wir zeigen, dass man eine beschr\"ankte Nullstellensuche noch mit den ersten beiden Erzeugungsschemata realisieren kann. 

Sei $f: \nz^{k+1} \rightarrow  \nz$
eine totale Funktion. 

Wir definieren eine neue totale Funktion $g: \nz^{k+1} \rightarrow  \nz$
durch
\[\begin{array}{r@{}l}
g(x_1,..., x_k, x_{k+1})&   = \min (~~~~ \\\{x_{k+1}\}~\cup~&~
  \{n\in\nz
\mid  n < x_{k+1}\textrm{ und }f(n,x_1,..., x_k) = 0\} ~~~)
\end{array}\]
 
 Dann gilt 
\GLA g(x_1,..., x_k, 0) &=& 0\\ 
g(x_1,..., x_k, y{+}1) &=&  
 g(x_1,..., x_k, y)\\&& + s_g(f(g(x_1,..., x_k,y),x_1,..., x_k))\GLE 
 Daher gilt: wenn $f $
primitiv rekursiv ist, ist auch $g $
primitiv rekursiv.


\end{example}
\end{frame}}


\only<presentation>{\begin{frame}

\begin{example}
Abgeleitetes Erzeugungsschema: beschr\"ankte Nullstellensuche \pause 

\begin{itemize}
\item Gegeben totale Funktion $f: \nz^{k+1} \rightarrow  \nz$\pause 
\item Definiere totale Funktion $g: \nz^{k+1} \rightarrow  \nz$ \pause 
durch
\[\begin{array}{r@{}l}
g(x_1,..., x_k, x_{k+1})~~~=~~~&   \min (~~\pause ~~ \\\{x_{k+1}\}~\pause \cup~\pause ~
  \{n\in\nz~&
\mid  n < x_{k+1}\textrm{ und }f(n,x_1,..., x_k) = 0\} ~)
\end{array}\]
\end{itemize}
\pause  Dann gilt \pause 
\GLA g(x_1,..., x_k, 0) &=& 0\pause \\ 
g(x_1,..., x_k, y{+}1) &=&  
 g(x_1,..., x_k, y)\pause \\&& + s_g(f(g(x_1,..., x_k,y),x_1,..., x_k))\GLE 
\pause  Daher gilt: \pause wenn $f $
primitiv rekursiv ist, \pause ist auch $g $
primitiv rekursiv.
\end{example}
\end{frame}}

\begin{frame}
\begin{cont}{}
Beispiel zur Anwendung der beschränkten Minimalisierung:  \pause 
\begin{itemize}
\item Sei $f: \nz^2\rightarrow \nz$
definiert durch \pause 
 \[f(n, x) := sub(x, mult(n, n))~~ \pause ~~= x-n^2\]
\only<presentation>{\vspace{-2ex}}
\item
\pause Sei $g $
die nach dem eben beschriebenen Verfahren\\
 zu $f $
definierte primitiv rekursive Funktion,  \pause d.h.
\[ g(x, y)   = \min (~~\{y\}~\cup~  \{n\in\nz
\mid  n < y\textrm{ und }n^2\geq x\}~~)
\]
\item \pause 
Sei $h: \nz
^2\rightarrow  \nz$ definiert durch $h(x) := g(x,x{+}1)$.  \pause 

Dann ist auch $h $
primitiv rekursiv,  \pause und es gilt:
     $$h(x) = \min\{n\in\nz\mid  n^2 \geq x\}$$
 \pause Für eine Quadratzahl $x$ ist $h(x)=\sqrt{x}$,  \pause generell: $$h(x)=\left\lceil\sqrt{x}~\right\rceil$$
\end{itemize}
\end{cont}
\end{frame}



\only<article>{\begin{frame}
 Wir wollen jetzt zeigen, dass man Zahlenvektoren 
 mit Hilfe einer primitiv rekursiven Funktion durch 
 einzelne Zahlen codieren kann. 
 Auch die Umkehrfunktionen dieser Codierung werden primitiv rekursiv sein.


 Die einstellige Funktion $c_2(n) :=\frac{n\cdot(n{+}1)}{2}=\sum_{i=0}^n i$ gibt gerade die Summe der 
 Zahlen von $0$ bis $n$
 wieder. Sie ist primitiv rekursiv, 
 denn es gilt $c_2(0) = 0$ und 
 $c_2(n{+}1) = c_2(n) + n + 1 = S(add(n, c_2(n)))$
 
 Man erh\"alt $c_2$ also mit dem Rekursionsschema 
 aus den Funktionen $Z $
und $S(add)$.


 Man kann dies nun f\"ur die zweistellige Funktion 
 $c(x, y) := c_2(x+y) + x$
 nutzen, die man aus $c_2$ und anderen primitiv rekursiven 
 Funktionen durch Komposition erh\"alt. 
 Also ist diese Funktion selbst primitiv rekursiv. 
 Sie ist au"serdem eine Bijektion zwischen $\nz^2$ und $\nz$. 
\end{frame}}




\only<presentation>{\begin{frame}
Äquivalenzbeweis Turing-berechenbar $\Rightarrow$ WHILE-berechenbar: \pause 
\\
Verschlüsselung des Bandes (= Vektor von Zeichen) durch eine Zahl \pause 

Jetzt:  
Verschlüsselung von \emph{Zahlen}vektoren durch eine Zahl \pause 

Betrachte 
 \GLA c_2(n) &:=&\frac{n\cdot(n{+}1)}{2} \pause =\sum_{i=0}^n i\pause \\
\textrm{ also }~~~~~~~~~~c_2(0) &=& 0 \pause \\
c_2(n{+}1) &=& c_2(n) + n + 1  \pause = S(add(n, c_2(n)))
\GLE
 \pause Damit  \[c_2=PrRek(Z,Komp(add,S))\]
 \pause und 
 \[\langle x, y\rangle = c_2(x+y) + x\]
 Also: Die \Fb{Cantorsche Bijektion} ist primitiv rekursiv!
\end{frame}}



\only<article>{\begin{frame}

 Die Umkehrung dieser Bijektion erh\"alt man folgenderma"sen: 
 Sei $z$ gegeben. Wir wollen $x $ und $y $
mit $z = \langle x,y\rangle$ finden. 
Man bestimmt dazu $n$ so, dass $c_2(n) \leq z<c_2(n{+}1)$ gilt. 
Dann ist $x =z - c_2(n)$ und $y = n - x$.

 Beispiel: $z = \langle x, y\rangle  = 18 \Rightarrow n= 5, x = 3, y= 2$. 
\end{frame}}

\only<presentation>{\begin{frame}
Umkehrung dieser Bijektion: \pause 
\begin{itemize}
\item Sei $z$ gegeben \pause 
\item Gesucht $x $ und $y $
mit $z =  \langle x,y\rangle$ \pause 
\item 
Bestimme $n$ mit $c_2(n) \leq z \pause <c_2(n{+}1)$ \pause 
\item  
Dann  $x =z - c_2(n)$  \pause und $y = n - x$. \pause 
\end{itemize}
 Beispiel: $z = \langle x, y\rangle  = 18 \Rightarrow n= 5, x = 3, y= 2$. 
\end{frame}}

\only<article>{
 Wir wollen nun beweisen, dass auch die Komponenten der Umkehrung  primitiv rekursive Funktionen sind. 

Dazu setzen wir $p_1(\langle x, y\rangle) := x$,
$p_2(\langle x, y\rangle) := y$.  Es muss also gelten $\langle p_1(n), p_2(n)\rangle = n$.
 
Wir wollen zeigen, dass die so definierten Funktionen $p_1$ und $p_2$
primitiv rekursiv sind. 

Dazu folgen wir der eben beschriebenen Methode, um aus $z=\langle x, y\rangle $ die Zahlen $x = p_1(z)$ und $y=p_2(z)$ zu bestimmen. 

Zuerst berechnet man die kleinste Zahl $n$, so dass $z< c_2(n{+}1)$ gilt. 
Dies geht mit einer beschr\"ankten Nullstellensuche wie im obigen Beispiel: 
Die durch $f(n, z) := sub(1,sub(c_2(n{+}1),z))$ definierte 
zweistellige Funktion $f $ ist primitiv rekursiv. 
Nach obigen Beispielen ist dann auch die durch
$$g(z,t)   = \min( \{t\} \cup\{n\in \nz\mid  n<t\textrm{ und  }f(n,z) = 0\} )$$
 definierte zweistellige Funktion $g $
primitiv rekursiv. 

Da klar ist, dass die gesuchte Zahl $n$
nicht gr\"o"ser als $z $
sein kann, braucht man nur bis $z $
zu suchen. Also ist die gew\"unschte Zahl $n$
 gegeben durch $n = g(z, z)$. 

 Wir erhalten $x = p_1(z)= z-c_2(g(z, z))$ und 
 $y = p_2(z) =n-x = g(z, z)-(z -c_2(g(z, z)))$. 
 Also ist sowohl $p_1$ als auch $p_2$
primitiv rekursiv.
}

\only<presentation>{\begin{frame}
Betrachte Komponenten der Umkehrung,  \pause d.h.
\[p_1:= pr^2_1\circ \langle\cdot,\cdot\rangle^{-1} \pause \textrm{ und }p_2:= pr^2_2\circ \langle\cdot,\cdot\rangle^{-1}\]
 \pause D.h. $p_1(\langle x, y\rangle) = x$, \pause  $p_2(\langle x, y\rangle) = y$  \pause und $\langle p_1(z), p_2(z)\rangle = z$.
 
 \pause $p_1$ und $p_2$ sind
primitiv rekursiv:  \pause 
\begin{itemize}
\item Zu $z$ bestimme kleinstes $n$ mit  $z< c_2(n{+}1)$: \pause 

Dazu beschr\"ankte Nullstellensuche  \pause mit 
\GLA f(n, z) &:=& sub(1,sub(c_2(n{+}1),z))=  \pause 1-(c_2(n{+}1)-z) \pause\\
g(z,t)   &:=& \min( \{t\} \cup\{n\in \nz\mid  n<t\textrm{ und  }f(n,z) = 0\} ) \pause \\
&=&\min( \{t\} \cup\{n\in \nz\mid  n<t\textrm{ und  }z< c_2(n{+}1)\} )
\GLE
 \pause gesuchte Zahl $n$
ist nicht gr\"o"ser als $z $, \pause  also $n := g(z, z)$. 
\item
 \pause  Dann \GLA x &=& p_1(z) \pause = z-c_2(g(z, z)) \pause \\
y &=& p_2(z)  \pause =n-x  \pause = g(z, z)-(z -c_2(g(z, z)))
\GLE 
\end{itemize}
 \pause Damit  sowohl $p_1$ als auch $p_2$
primitiv rekursiv.
\end{frame}}


\only<article>{\begin{frame}
 Man kann die Cantorsche Bijektion
auch verwenden, um ein $k$-Tupel 
von nat\"urlichen Zahlen (mit $k\geq 1$)
in eine einzige nicht negative Zahl umzukodieren. 
Dazu setzt man: 
     $$\langle n_1,n_2,..., n_k\rangle := \langle n_1,\langle n_2,..., \langle n_{k-1}, n_k\rangle ...\rangle\rangle$$
 Die so definierte Funktion ist also eine Bijektion von $\nz^k$ nach $\nz$.

Sie ist nach dem Kompositionsschema primitiv rekursiv. Durch Komposition der Funktionen $p_1$
und $p_2$  kann man auch die Umkehrfunktionen $d_i^{(k)}$ zu dieser 
 $k$-stelligen Codierfunktion erhalten: 
\GLA d_1^{(k)}(n) &=& p_1(n)\\
 d_2^{(k)}(n) &=& p_1(p_2(n))\\&&...\\ 
d_{k-1}^{(k)}(n) &=& p_1(p_2(p_2(...p_2(n)...)\\
d_k^{(k)}(n) &=& p_2(p_2(...p_2(n)...))\GLE
 wobei $p_2$ bei $d_{k- 1}^{(k)}(n)$  $(k{-}1)$-mal angewendet wird und bei 
 $d_k^{(k)}(n)$  $k$-mal. Auch diese Umkehrfunktionen sind primitiv rekursiv.
\end{frame}}


\only<presentation>{\begin{frame}
Definiere primitiv rekursive Bijektion $\langle\cdot\rangle~:~\nz^k\rightarrow\nz$ \pause  wie folgt:
     $$\langle n_1,n_2,..., n_k\rangle := \langle n_1,\langle n_2,..., \langle n_{k-1}, n_k\rangle ...\rangle\rangle$$
 \pause Dabei sei $k\geq 1$.

 \pause Betrachte Komponenten $d_i^{(k)}$  der Umkehrfunktion,
 \pause d.h.
\[d_i^{(k)}(\langle n_1,n_2,..., n_k\rangle)=n_i\]

 \pause Alle $d_i^{(k)}$  sind ebenfalls primitiv rekursiv: \pause 
\GLA d_1^{(k)}(n) &=& p_1(n) \pause \\
 d_2^{(k)}(n) &=& p_1(p_2(n)) \pause \\&&... \pause \\ 
d_{k-1}^{(k)}(n) &=& p_1(p_2(p_2(...p_2(n)...) \pause \\
d_k^{(k)}(n) &=& p_2(p_2(...p_2(n)...))\GLE
\end{frame}}





\begin{frame}
\only<article>{ Nun k\"onnen wir den folgenden Satz beweisen: }
\begin{theorem}\label{PR-Loop}
Eine Funktion ist primitiv rekursiv genau dann, wenn sie LOOP-berechenbar ist.
\end{theorem}
\only<article>{ Beweis :

 Zuerst zeigen wir durch Induktion \"uber den Aufbau der 
 primitiv rekursiven Funktionen, 
 dass jede primitiv rekursive Funktion LOOP-berechenbar ist. Die
 Grundfunktionen sind LOOP-berechenbar. 
 Zum Beispiel wird die nullstellige Funktion $Z $
mit konstantem Wert $0$ durch das LOOP-Programm $x_0  := x_0 + 0$ berechnet. 
Die Nachfolgerfunktion $S $ wird durch das LOOP-Programm $x_0  := x_1 + 1$ berechnet. Und die Projektionsfunktion $pr^k_j$ wird durch das LOOP-Programm 
$x_0  := x_j+ 0$ berechnet. 
Sei jetzt $f $ nach dem Kompositionsschema definiert, d.h. 
$f = h(g_1,...,g_m)$, und $g_1,...,g_m$ seien $k$-stellige Funktionen. 
Nach Induktionssannahme gibt es LOOP-Programme, die die Funktionen $h$, $g_1$,...,
$g_m$ berechnen. Es ist klar, dass man sie zu einem LOOP-Programm f\"ur $f $
zusammensetzen kann. Man  muss dazu nur einige Variablen auswechseln. 
}
\only<presentation>{
 \pause  Beweis '$\Rightarrow$' \pause 

durch Induktion \"uber den Aufbau der 
 primitiv rekursiven Funktionen: \pause 

\Fb{(a) Grundfunktionen} sind LOOP-berechenbar: \pause 

\[\begin{array}{c|l}
\textrm{Funktion}&\textrm{LOOP-Programm} \pause \\\hline
Z \pause &x_0  := x_0 + 0 \pause \\
S \pause &x_0  := x_1 + 1 \pause \\
pr_j^k \pause &x_0  := x_j+ 0
\end{array}\]
}
\end{frame}

\only<presentation>{\begin{frame}
\Fb{(b) Kompositionsschema }$f = h(g_1,...,g_m)$ mit $k$-stelligen $g_i$: \pause \\[2ex]

Setze Programme $H$, $G_1$,..., $G_m$  für $h$, $g_1$,..., $g_m$  \pause \\
zu Programm $F$ für $f$ zusammen durch: \pause \\[2ex]

$\nu$ sei maximaler Index der Variablen in $H$, $G_1$,..., $G_m$ \pause \\[2ex]

Dann arbeite $F$ wie folgt: \pause 
\begin{itemize}
\item Sicherung der Startwerte $n_1,...,n_k$ von $x_1,...,x_k$ in $x_{\nu+1},...,x_{\nu+k}$  \pause 
\item Ausführung von $G_1$,  \pause d.h. Berechnung von $j_1=g_1(n_1,...,n_k)$ \pause 
\item Sicherung des Resultates $j_1$  \pause durch $x_{\nu+k+1}:=x_0$ \pause 
\item Alle Variablen mit Index $\leq\nu$ wieder auf $0$ setzen \pause 
\item Werte $n_i$ für $1\leq i \leq k$ wieder in $x_i$ speichern \pause 
\item Ausführung von $G_2$, \pause  d.h. Berechnung von $j_2=g_2(n_1,...,n_k)$ \pause 
\item usw... \pause 
\item Am Ende:  \pause Berechnung von $h(j_1,...,j_m)$
\end{itemize}
\end{frame}}

\only<article>{\begin{frame}

Kommen wir zum Rekursionsschema:
\GLA
f(x_1,..., x_k, 0) &:=& g(x_1,..., x_k) \\ 
f(x_1,..., x_k, y{+}1) &:=& h(x_1,..., x_k, y,f(x_1,..., x_k, y))
\GLE  
 Wir k\"onnen wieder annehmen, dass LOOP-Programme zur 
 Berechnung von $g $ und $h $
zur Verf\"ugung stehen und k"onnen damit ein LOOP-Programm wie folgt konstruieren:

\texttt{\begin{tabular}{l}
$x_0:= g(x_1,..., x_k)$;\\
$t:= 0$;\\
LOOP $x_{k+1}$  DO  $x_0:= h(x_1,..., x_k, t, x_0);  t := t+ 1$ END;
\end{tabular}}

 wobei $t$ eine Variable sein soll, die in den LOOP-Programmen f\"ur $g $
und $h $
nicht verwendet wird. 
Au"serdem m\"ussen die LOOP-Programme f\"ur $g $
und $h $
so abgewandelt werden, 
dass sie keine gemeinsamen Arbeitsvariablen benutzen. 
Die Variablen $x_1$,..., $x_{k+1}$
 sollten ferner nicht \"uberschrieben werden, 
 da sie die Eingabe enthalten und diese in den Schleifendurchl\"aufen immer 
 wieder gebraucht wird. Dieses LOOP-Programm  berechnet offenbar 
 $f(x_1,..., x_k,x_{k+1})$.

\end{frame}}




\only<presentation>{\begin{frame}
\Fb{(c) Rekursionsschema} $f=PrRek(g,h)$, \pause  d.h.
\GLA
f(x_1,..., x_k, 0) &:=& g(x_1,..., x_k) \\ 
f(x_1,..., x_k, y{+}1) &:=& h(x_1,..., x_k, y,f(x_1,..., x_k, y))
\GLE  

 \pause Gegeben seien also LOOP-berechenbare $g$ und $h$ \pause 

Arbeitsweise eines LOOP-Programms für $f$: \pause 

\texttt{\begin{tabular}{l}
$x_0:= g(x_1,..., x_k)$; \pause \\
$t:= 0$; \pause \\
LOOP $x_{k+1}$  DO  $x_0:= h(x_1,..., x_k, t, x_0);  t := t+ 1$ END;
\end{tabular}}

 \pause Umsetzung in LOOP-Programm  \pause (analog zur Komposition): \pause
\begin{itemize}
\item Werte $x_1,...,x_k$ werden gesichert  \pause (in geeigneten Variablen) \pause 
\item Variablen, die bei $g$ oder  $h$ genutzt werden, werden
wieder gelöscht \pause 
\item Damit:  \pause Keine 'Seiteneffekte' bei den Berechnungen von $g$ und $h$ \pause 
\item $t$ ist Variable, die ansonsten ungenutzt ist \pause 
\end{itemize} 
 LOOP-Programm  berechnet offenbar  $f$ !

\end{frame}}



\only<article>{\begin{frame}

 Sei nun umgekehrt $f: \nz^r\rightarrow \nz$
 LOOP-berechenbar. Dann gibt es ein LOOP-Programm 
 $P$, das $f$
berechnet. Die in $P$
 vorkommenden Variablen seien $x_0$,$x_1$,..., $x_k$
 mit $k\geq r$. Nun wird durch Induktion \"uber die L\"ange von $P$
 gezeigt, dass es eine primitiv rekursive Funktion 
 $g_P: \nz\rightarrow  \nz$
 gibt, die das Verhalten des LOOP-Programms $P $
auf allen Variablen $x_0$, $x_1$,..., $x_k$
 simuliert. Dies ist in dem Sinne zu verstehen, 
 dass zu gegebenen Anfangswerten $a_0$, $a_1$,..., $a_k $
und Endwerten $b_0$, $b_1$,..., $b_k$ der Variablen 
$x_0$, $x_1$,..., $x_k$ gilt, dass \[g_P({\langle}a_0, a_1,..., a_k{\rangle}) = 
{\langle}b_0, b_1,..., b_k{\rangle}\]

 Falls $P$ die Form $x_i:= x_j \pm c$
 hat, so setzt man \[g_P(z) := {\langle}d_1^{(k+1)}(z),..., d_{i}^{(k+1)}(z), d_{j+1}^{(k+1)}(z) \pm c, 
 d_{i+2}^{(k+1)}(z),..., d_{k+1}^{(k+1)}(z){\rangle}\]
 Hier benutzen wir, dass die oben definierte Bijektion  
 ${\langle}\cdot{\rangle}$  von $\nz^{k+1}$ nach $\nz$
und ihre Umkehrfunktionen $d_1^{(k+1)}$, $d_2^{(k+1)}$, ..., $d_{k+1}^{(k+1)}$
 primitiv rekursiv sind. Man beachte die Indexverschiebung: Variable $x_i$ entspricht
der $i{+}1$-ten Komponenten des Zahlenvektors!

 Hat $P$ die Form $Q; R$, so sind die beiden Programme 
 $Q$ und $R$
 k\"urzer als $P$. Daher existieren nach Induktionsannahme 
 primitiv rekursive Funktionen $g_Q $ f\"ur $Q $
und $g_R$ f\"ur $R$.
 Wir definieren $g_P$
 einfach durch $g_P(z) = g_R(g_Q(z))$. Dann ist $g_P $
auch primitiv rekursiv und hat die gew\"unschte Eigenschaft. 
 
 Kommen wir zu der Form \texttt{LOOP $x_i$ DO $Q$ END}, 
so definieren wir zun\"achst durch die primitive Rekursion mittels $g_Q$
 eine zweistellige Funktion $h$:
\[h(0,x) = x;~~~ h(n{+}1,x) = g_Q(h(n,x))\]
 und k\"onnen so den Zustand der Arbeitsvariablen $x = {\langle}x_0, x_1,..., x_k{\rangle}$ nach 
 $n$ Anwendungen von $Q$  beschreiben. Wir k\"onnen setzen 
 $g_P(x) := h(d_{i+1}^{(k+1)}(x),x)$. 


 Damit ist der Induktionsbeweis beendet. 
 Wir haben gezeigt, dass es zu dem LOOP-Programm  $P$
eine primitiv rekursive Funktion $g_P$
mit $g_P({\langle}a_0,a_1,..., a_k{\rangle}) = {\langle}b_0,b_1,...,b_k{\rangle}$ gibt.
 Da $f(n_1,..., n_r)$ der Wert der Programmvariablen 
 $x_0$ nach Ausf\"uhrung von $P$ ist, gilt 
 $f(n_1,..., n_r) = d_1^{(k+1)}(g_P({\langle}0,n_1,...,n_r, 0,..., 0{\rangle}))$,
 wobei hier bei der Eingabe die letzten $(k-r)$ Stellen $0$ sind. 
 Also ist $f $ primitiv rekursiv.  
\end{frame}}




\only<presentation>{\begin{frame}
 Beweis '$\Leftarrow$' \pause 

durch Induktion \"uber den Aufbau der 
LOOP-berechenbaren Funktionen: \pause 

\begin{itemize}
\item  $P$ sei LOOP-Programm für $r$-stellige Funktion $f$ \pause 
\item in $P$ vorkommende Variablen seien $x_0$,$x_1$,..., $x_k$
 mit $k\geq r$.  \pause 
\item Kodiere  $x_0$,$x_1$,..., $x_k$ in einer einzelnen Zahl \pause \\
 mit  Bijektion  
 ${\langle}\cdot{\rangle}:\nz^{k+1}\rightarrow\nz$ und Umkehrungen $d_i^{(k+1)}$ \pause 
\item Konstruiere (induktiv) primitiv rekursive Funktion 
 $g_P: \nz\rightarrow  \nz$, \pause \\
 die das Verhalten von $P $
auf allen Variablen $x_0$, $x_1$,..., $x_k$
 simuliert \pause 
\item d.h. zu gegebenen Anfangswerten $a_0$, $a_1$,..., $a_k $ \pause 
und Endwerten $b_0$, $b_1$,..., $b_k$  \pause (nach Ablauf von $P$) \pause  der Variablen 
$x_0$, $x_1$,..., $x_k$ \pause  gelte \[g_P({\langle}a_0, a_1,..., a_k{\rangle}) = 
{\langle}b_0, b_1,..., b_k{\rangle}~~~ \pause~(*)\]
\end{itemize}
\end{frame}}




\only<presentation>{\begin{frame}

(a) Falls $P$ die Form $x_i:= x_j \pm c$
 hat,  \pause so setze 
\GLA g_P(z) &:= {\langle}& \pause d_1^{(k+1)}(z),..., d_{i}^{(k+1)}(z), \pause \\
&& d_{j+1}^{(k+1)}(z) \pm c, \pause \\
&& 
 d_{i+2}^{(k+1)}(z),..., d_{k+1}^{(k+1)}(z)~~~{\rangle}\GLE
 \pause (Achtung:  Variable $x_i$ enspricht $i{+}1$-ter Komponente!)

 \pause Damit ist $g_P $ primitiv rekursiv \pause  und hat Eigenschaft $(*)$ \pause 

(b) Falls $P$ die Form $Q; R$ hat:  \pause 
\begin{itemize}
\item Programme  $Q$ und $R$
sind  k\"urzer als $P$ \pause 
\item mit Induktionsannahme: \pause \\
 es gibt primitiv rekursive Funktionen $g_Q $ f\"ur $Q $
und $g_R$ f\"ur $R$\pause 
\item 
Definiere $g_P$  \pause durch $g_P(z) = g_R(g_Q(z))$.  \pause 
\end{itemize}
Damit ist $g_P $ primitiv rekursiv und hat Eigenschaft $(*)$
\end{frame}}




\only<presentation>{\begin{frame}
(c) Falls $P$ die Form \texttt{LOOP $x_i$ DO $Q$ END} hat: \pause 
\begin{itemize}
\item mit Induktionsannahme: \pause \\ es gibt primitiv rekursive Funktion $g_Q $ f\"ur $Q $ mit $(*)$ \pause 
\item Definiere mit primitiver Rekursion zweistellige Funktion $h$: \pause 
\[h(0,x) = x;~~~~~ h(n{+} 1,x) = g_Q(h(n,x))\]
\item  \pause $h(n,x)$ simuliert in $x$ (für  ${\langle}x_0, x_1,..., x_k{\rangle}$) \pause  $n$ Anwendungen
von~$Q$ \pause 
\item Setze $g_P(x) := h(d_{i+1}^{(k+1)}(x),x)$ \pause 
\end{itemize}
Damit ist wieder $g_P $ primitiv rekursiv mit Eigenschaft $(*)$ \pause 

Also:  \pause Für alle LOOP-Programme $P$ existiert primitiv rekursives $g_P$  \pause 
 mit \[g_P({\langle}a_0,a_1,..., a_k{\rangle}) = {\langle}b_0,b_1,...,b_k{\rangle}\]

 \pause Wird $f:\nz^r\rightarrow\nz$ durch $P$ berechnet,  \pause so ergibt sich 
\[f(n_1,..., n_r) = d_1^{(k+1)}(g_P({\langle}0,n_1,...,n_r, \underbrace{0,..., 0}_{k-r}{\rangle}))\]
 \pause d.h. $f $ ist auch primitiv rekursiv.  
\end{frame}}




\only<article>{\begin{frame}

 Eine echte Erweiterung der Klasse der primitiv rekursiven Funktionen 
 wird durch die Hinzunahme eines neuen Erzeugungsschemas, 
 des $\mu$-Operators erreicht. 
 Es sei $f $ eine gegebene $(k{+}1)$-stellige Funktion. 
 Dann definieren wir 
  \GLA g(x_1,..., x_k)& =& \min \{n\in\nz \mid f(n, x_1,..., x_k) = 0\textrm{ und}\\
&&\textrm{f\"ur alle }m<n\textrm{ ist }f(m, x_1,..., x_k)\textrm{ definiert und}\\
&&\textrm{f\"ur alle }m<n\textrm{ ist } f(m, x_1,..., x_k)>0\}
\GLE
 oder k\"urzer 
    \[g(x_1,..., x_k) = (\mu n) [f(n, x_1,..., x_k) = 0]\] 
 F\"ur $g $
schreibt man auch $\mu f$. Die Funktion $g$
 ist $k$-stellig und partiell \"uber $\nz^k$
 definiert, denn wenn das Minimum nicht existiert, sei $g$
 an dieser Stelle undefiniert. 
 $f$ braucht auch nur partiell definiert zu sein. Wenn $f $
z.B. die $(k{+}1)$-stellige konstante Funktion mit Wert z.B. $42$ ist und 
damit \"uberall definiert ist, ist $g$ die $k$-stellige nirgends 
definierte Funktion.  Die Funktion $g $ erh\"alt man durch 
unbeschr\"ankte Nullstellensuche f\"ur die Funktion $f$.
 Man beachte, dass man eine beschr\"ankte Nullstellensuche 
 noch durch das Rekursionsschema der primitiven Rekursion 
 und das Kompositionsschema realisieren kann, vgl. obige Beispiele.
\end{frame}}







\only<presentation>{\begin{frame}
Neues Erzeugungsschema: \Fb{$\mu$-Operator},  \pause $\mu:f\mapsto g$ \pause 
\begin{itemize}
\item gegeben:   $(k{+}1)$-stellige (evtl. partielle!) Funktion $f$\pause 
\item erzeugt: $k$-stellige Funktion $g$  \pause mit 
  \GLA g(x_1,..., x_k)& =& \pause  \min \{n\in\nz \mid  \pause f(n, x_1,..., x_k) = 0 \pause \textrm{ und}\\
&&\textrm{f\"ur alle }m<n\textrm{ ist }f(m, x_1,..., x_k)\textrm{ definiert und} \pause \\
&&\textrm{f\"ur alle }m<n\textrm{ ist } f(m, x_1,..., x_k)>0\}
\GLE
 \pause  oder k\"urzer 
    \[g(x_1,..., x_k) = (\mu n) [f(n, x_1,..., x_k) = 0]\]
\end{itemize} 
 \pause Anmerkungen: \pause 
\begin{itemize}
\item Schreibweise: $g:=\mu f$ \pause 
\item Mimimum der leeren Menge ist undefiniert,  \pause damit:
\item $g$ ist evtl.\ nicht total: \pause 
\begin{itemize}
\item
wenn $f(n, x_1,..., x_k)$ nie Null wird,  \pause ist $g(x_1,..., x_k)$ undefiniert \pause 
\item
wenn $f(n, x_1,..., x_k)=0$,  \pause aber $f(m, x_1,..., x_k)$ undefiniert ist für
ein $m<n$,  \pause so ist $g(x_1,..., x_k)$ ebenfalls undefiniert  \pause 
\end{itemize}
\item Zur Auswertung von $g$: \pause  Werte $f(n, x_1,..., x_k)$ für
$n=0,1,2,...$ der Reihe nach ausrechnen... 
\end{itemize}
\end{frame}}





\begin{frame}
\begin{definition}

 Die Menge der $\mu$-rekursiven (auch: partiell rekursiven)
   Funktionen \pause besteht genau aus den Funktionen, \pause  
   die sich aus der Menge der Grundfunktionen \pause durch 
   endlich oft wiederholte Anwendung des Kompositionsschemas, \pause 
   des Rekursionsschemas  \pause und des $\mu$-Operators bilden lassen.  \pause
\end{definition}

\begin{theorem}\label{MU-While}
 Die Klasse der $\mu$-rekursiven Funktionen stimmt mit der Klasse der WHILE- 
 (TURING-) berechenbaren Funktionen \"uberein. 
\end{theorem}
\end{frame}

\only<article>{
 Beweis: 

 Wir k\"onnen im Wesentlichen den Beweis des letzten Satzes 
 \"ubernehmen, m\"ussen allerdings noch den Fall des $\mu$-Operators 
 im Zusammenhang mit der WHILE-Schleife betrachten. 

 Sei eine Funktion $g$
 durch Anwendung des $\mu$-Operators auf eine $\mu$-rekursive Funktion $f $
definiert, also \[g(x_1,..., x_k) = (\mu n)[f(n,x_1,...,x_k) = 0]\]
Nach Induktionsannahme gibt es ein WHILE-Programm zur Berechnung von $f$. 
Dieses wird in dem folgenden WHILE-Programm unter geeigneter \"Anderung 
-falls n\"otig- der Variablen verwendet. Das folgende WHILE- Programm berechnet die Funktion $g$:

\texttt{\begin{tabular}{l}
$x_0 := 0$; \\ 
$y:= f(0,x_1,...,x_k)$; \\ 
WHILE $y$ DO \\ 
~~$x_0 := S(x_0)$; \\ 
~~$y:= f(x_0, x_1,..., x_k)$; \\ 
END; 
\end{tabular}}


 Sei umgekehrt $f: \nz^r\rightarrow  \nz$
 WHILE-berechenbar. Dann gibt es ein WHILE-Programm $P$, das $f $
berechnet. Die in $P$ vorkommenden Variablen seien 
$x_0$, $x_1$,..., $x_k$
 mit $k\geq r$. Nun wird durch Induktion \"uber die L\"ange von $P$
 gezeigt, dass es eine $\mu$-rekursive Funktion $g_P: \nz\rightarrow  \nz$
 gibt derart, dass zu gegebenen Anfangswerten $a_0$, $a_1$,..., $a_k $
und Endwerten $b_0$, $b_1$,..., $b_k$ der Variablen $x_0$, $x_1$,..., $x_k$ 
gilt, dass \[g_P({\langle}a_0, a_1,..., a_k{\rangle}) = {\langle}b_0, b_1,..., b_k{\rangle}\]
 
Nach den \"Uberlegungen im vorigen Beweis m\"ussen wir nur noch den Fall
 behandeln, dass das Programm $P$ ein WHILE-Programm der Form
      \texttt{WHILE $x_i$ DO $Q$ END} 
 ist. Wie im vorigen Beweis k\"onnen wir wieder 
 eine zweistellige Funktion $h(n, z)$ definieren, 
 die den Zustand der Programmvariablen $z = {\langle}x_0, x_1,..., x_k{\rangle}$ nach $n$
 Anwendungen von $Q$
 beschreibt und die in diesem Fall $\mu$-rekursiv ist. 
Dann setzen wir 
\[g_P(z) = h((\mu n)[d_{i+1}^{(k+1)}(h(n, z)) = 0],z )\]
 Das erste Argument liefert gerade die minimale 
 Wiederholungszahl des Programmes $Q$.
}


\only<presentation>{\begin{frame}
 Beweis:  \pause 
\begin{itemize}
\item analog zum Beweis 'LOOP-berechenbar $\Leftrightarrow$ primitiv rekursiv' \pause 
\item erweitert um $\mu$-Operator und  WHILE-Schleife \pause 
\end{itemize}
Alter Beweis also nur noch um Fälle (d) erweitert: \pause 
 
Fall (d) für '$\Rightarrow$':  \pause  $g=\mu f$ für $\mu$-rekursive Funktion $f$,  \pause also
 \[g(x_1,..., x_k) = (\mu n)[f(n,x_1,...,x_k) = 0]\]

 \pause Induktiv: WHILE-Programm $Q$ zur Berechnung von $f$ existiert... \pause 

Passendes WHILE-Programm für $g$: \pause 

\texttt{\begin{tabular}{l}
$x_0 := 0$;  \pause \\ 
$y:= f(0,x_1,...,x_k)$; \pause  \\ 
WHILE $y$ DO  \pause \\ 
~~$x_0 := S(x_0)$;  \pause \\ 
~~$y:= f(x_0, x_1,..., x_k)$;  \pause \\ 
END;  \pause 
\end{tabular}}

(Berechnung von $f$ über $Q$ wieder mit Sicherung der Variablen...)
\end{frame}}


\only<presentation>{\begin{frame}
Fall (d) für '$\Leftarrow$': \pause \\
  WHILE-Programm $P$ habe die Form
\texttt{WHILE $x_i$ DO $Q$ END}  \pause 

In $P$ vorkommende Variablen seien 
$x_0$, $x_1$,..., $x_k$ mit $k\geq r$.  \pause 

Wieder gesucht:  \pause $\mu$-rekursive Funktion $g_P: \nz\Partial  \nz$ \pause 
mit \[g_P({\langle}a_0, a_1,..., a_k{\rangle}) = {\langle}b_0, b_1,..., b_k{\rangle}\]
 \pause für gegebene Anfangswerte $a_0$, $a_1$,..., $a_k $
und Endwerte $b_0$, $b_1$,..., $b_k$  \pause (nach Ablauf von $P$) der Variablen $x_0$, $x_1$,..., $x_k$ \pause  

Induktiv:  \pause Entsprechende ($\mu$-rekursive!) Funktion $g_Q$ für $Q$ existiert... \pause 

Definiere (mit primitiver Rekursion) zweistellige Funktion $h$: \pause 
\[h(0,x) = x;~~~ \pause  ~~~h(n{+}1,x) = g_Q(h(n,x))\]
 \pause D.h. $h$ beschreibt wieder $n$ Anwendungen von $Q$ \pause 

Dann:  \pause $(\mu n)[d_{i+1}^{(k+1)}(h(n, x)) = 0]$  \pause ist minimale 
 Wiederholungszahl von $Q$ bis zum Erreichen einer Nullstelle, \pause 
also setze  
\[g_P(x) =  \pause h(~~~(\mu n)[d_{i+1}^{(k+1)}(h(n, x)) = 0]~ \pause ,~x~ )\]
 \pause (Rest des Beweises zu \ref{PR-Loop} wird unverändert übernommen!)
\end{frame}}





\begin{frame}
\only<article>{ Wir k\"onnen noch den folgenden Satz ableiten: }
\begin{theorem}[Kleene] \pause 
 F\"ur jede $k$-stellige $\mu$-rekursive Funktion $f$ \pause \\
gibt es zwei $(k{+}1)$-stellige primitiv rekursive Funktionen 
$p$ und $q$, \pause \\
 so dass sich $f$
darstellen l\"asst als  \pause 
     \[f(x_1,...,x_k) :=  \pause p(x_1,..., x_k,  \pause \mu q(x_0, x_1,..., x_k))\]
  \pause Hierbei ist $\mu q$
 durch die Anwendung des $\mu$-Operators auf $q$
 entstanden  \pause und steht abk\"urzend f\"ur $$(\mu x_0)[q(x_0, x_1,..., x_n) = 0]$$ 
\end{theorem}
\only<article>{
 Beweis: 

 Jede $\mu$-rekursive Funktion kann durch ein WHILE-Programm mit 
 nur einer WHILE-Schleife berechnet werden. 
 Bei der Transformation eines derartigen WHILE-Programms 
 in eine Darstellung als $\mu$-rekursive Funktion, die mittels 
 Grundfunktionen und Erzeugungsschemata erzeugt wird, 
 erh\"alt man die gew\"unschte Form, wie die Beweise von 
 Satz \ref{PR-Loop} und Satz \ref{MU-While}  zeigen.
}
\only<presentation>{
 \pause 
Beweis:  \pause 

 $f$ $\mu$-rekursiv  \pause \\
$\Rightarrow$ WHILE-Programm $P$ für $f$  \pause \\
 $\Rightarrow$ WHILE-Programm $P'$ für $P$ mit nur einer WHILE-Schleife \pause \\
 $\Rightarrow$ $\mu$-rekursive Funktion $f'$ für $P'$ mit nur einem $\mu$-Operator
}
\end{frame}