\section{LOOP- und  WHILE-Berechenbarkeit}
\inhalta{1-7}
\begin{frame}
\only<article>{ In diesem Kapitel wollen wir uns mit anderen möglichen Definitionen von berechenbaren 
`Zahlenfunktionen' (= hier benutzt für Funktionen, die natürliche Zahlen oder Tupel 
davon auf natürliche Zahlen abbilden) beschäftigen. 
Zuerst führen wir sogenannte LOOP-Programme ein, etwas später dann WHILE-Programme. 
Mit beiden Programmenarten kann 
man Zahlenfunktionen berechnen. Alle durch LOOP-Programme berechenbaren Funktionen
können auch durch WHILE-Programme berechnet werden. In einem späteren Kapitel 
werden wir aber sehen, dass die Umkehrung nicht einmal dann gilt, wenn man nur
totale Funktionen betrachtet. Aber wir werden zeigen, dass die durch 
Turingmaschinen berechenbaren Zahlenfunktionen genau mit den durch WHILE-Programme berechenbaren Funktionen 
übereinstimmen. Damit haben wir eine weitere 
einfache Möglichkeiten kennen gelernt, die 
berechenbaren Zahlenfunktionen zu charakterisieren.

Zuerst führen wir die LOOP-Programme ein. Die Idee ist, dass man mit diesen Programmen auf 
 Variablen rechnen darf, die als Werte natürliche Zahlen annehmen, 
 und dass einem als Programmkonstrukt LOOP-Schleifen zur Verfügung stehen, 
 die oft auch for-Schleifen genannt werden. 

 Die syntaktischen Grundbausteine von LOOP-Programmen sind:
}
\only<presentation>{Syntaktische Grundbausteine von LOOP-Programmen:\pause}
\begin{itemize}
\item        Variablen: \pause $x_0$ $x_1$ $x_2$ $\ldots$\pause
\item    Konstanten:  \pause $0$  $1$   $2$ $\ldots$ \pause\\ (also für \emph{jede} natürliche Zahl eine Konstante) \pause
\item  Trennsymbole und Operationszeichen: \pause  $~~;~~$   $~~:=~~$     $~~+~~$    $~~-~~$ \pause
\item   Schlüsselwörter: \pause~~~\texttt{\bfseries LOOP} \pause \texttt{\bfseries DO} \pause \texttt{\bfseries END}
\end{itemize}

\pause LOOP-Programme sind dann: \pause
\begin{itemize}
\item Jede Wertzuweisung $x_i  := x_j + c$ und  $x_i  := x_j - c$ ist ein LOOP-Programm (für Variablen $x_i, x_j$ und Konstanten $c$).\pause
\item Sind $P_1$ und $P_2$ LOOP-Programme,  \pause\\dann  ist auch $P_1;P_2$ ein LOOP-Programm. \pause
\item Ist $x$ Variable und $P$ LOOP-Programm,  \pause dann  ist auch\\  \texttt{\bfseries LOOP $x$ DO $P$ END} ein LOOP-Programm.\pause
\item Weitere Konstruktionen sind nicht zugelassen.
\end{itemize}
\end{frame}



\begin{frame}
 Die Semantik (Bedeutung) von LOOP-Programmen ergibt sich aus:\pause
\begin{itemize}
\item Die Werte der Variablen $x_i$ sind (beliebig) aus $\nz$.\pause
\item Bei $x_i  := x_j + c$ \pause erhält $x_i$ den Wert $x_j+ c$\pause\\ analog zu üblichen Programmiersprachen...\pause
\item Bei $x_i  := x_j - c$ \pause erhält $x_i$ den Wert $x_j{-} c$\pause, falls $x_j\geq c$,
\pause\\ ansonsten den Wert $0$. \pause(Damit bleiben alle Werte in $\nz$.)\pause
\item Bei  $P_1; P_2$  \pause wird erst $P_1$ ausgeführt, dann  $P_2$. \pause
\item Bei \texttt{\bfseries  LOOP $x$ DO $P$ END}  \pause wird das Programm $P$ so oft ausgeführt, wie der Wert
von $x$ \emph{\Fb{zu Beginn}}  der LOOP-Anweisung angibt. \pause
\end{itemize}
\only<article>{Mit LOOP-Programmen kann man Zahlenfunktionen berechnen:}

\begin{definition}[LOOP-Berechenbarkeit]\label{LOOP-Berechenbarkeit}
\only<article>{ Eine Funktion $f: \nz^k\rightarrow  \nz$
hei"st LOOP-berechenbar, falls es ein LOOP-Programm $P$
 gibt, so dass $P$ gestartet mit der beliebigen Eingangsbelegung 
 $n_1,..., n_k$
 aus $\nz$
 in den Variablen $x_1,..., x_k $
und $0$ in allen anderen Variablen mit dem Wert $f(n_1,..., n_k)$ 
in der Variablen $x_0$ stoppt.}
\only<presentation>{ \pause Eine Funktion $f: \nz^k\rightarrow  \nz$
hei"st LOOP-berechenbar, falls \pause
\begin{itemize}
\item es ein LOOP-Programm $P$ gibt, so dass $P$, \pause
\item  gestartet mit  
 $n_1,..., n_k$
 aus $\nz$
 in den Variablen $x_1,..., x_k $ \pause
\item und $0$ in allen anderen Variablen \pause
\item  mit dem Wert $f(n_1,..., n_k)$ 
in der Variablen $x_0$ stoppt.
\end{itemize}}
 \end{definition}

\end{frame}



\begin{frame}
\only<article>{
 Zwei wichtige Eigenschaften der LOOP-berechenbaren Funktionen 
 müssen hervorgehoben werden. Erstens sind alle 
 LOOP-berechenbaren Funktionen total, d.h. auf allen Zahlenvektoren aus 
 $\nz^k$  (für ein festes $k $
natürlich) definiert, da jedes LOOP-Programm 
nach endlich vielen Schritten (`Schritt' = Ausführung einer Wertzuweisung)  anhält, 
wie man per Induktion über den Aufbau der Programme formal beweisen kann:
Die Aussage gilt offenbar für Programme der Form
 $x_{i}:=x_{j}\pm c$. Gilt sie für $P_{1}$ und für $P_{2}$, dann auch für
$P_{1};P_{2}$. Gilt sie für $P$, dann auch für $\mathtt{LOOP} x_{i}
\mathtt{DO} \mathtt{P} \mathtt{END}$. Letzteres gilt dank der speziellen
Semantik der \texttt{\bfseries LOOP}-Anweisung. \texttt{for}-Anweisungen wie sie
z.B. Programmiersprachen wie \texttt{C} und \texttt{Java} erlauben, haben eine andere
Semantik --- hier kann man mühelos Endlosschleifen produzieren, etwa durch
\texttt{for (x=0;x<1;x=x) x=x-1;}.

Zweitens stellt sich die Frage, 
ob alle totalen Turing-berechenbaren Funktionen auch LOOP-berechenbar sind. 
Diese Frage muss verneint werden, wie wir später sehen werden.}
\only<presentation>{
Anmerkungen:\pause
\begin{enumerate}
\item alle  LOOP-berechenbaren Funktionen sind total:\pause

\emph{Jedes} LOOP-Programm hält auf \emph{jeder} Eingabe!\pause

(Beweis: Induktion über den Aufbau der LOOP-Programme...) \pause
\item Es gibt also Turing-berechenbare Funktionen, \\die nicht LOOP-berechenbar sind...\pause
\item Sogar: Nicht einmal jede \emph{totale} Turing berechenbare Funktion\\ ist  LOOP-berechenbar...
\end{enumerate}
}
\end{frame}



\begin{frame}
\only<article>{
 Wir wollen nun zeigen, dass einige einfache Funktionen und Konstrukte in 
 der LOOP-Sprache realisierbar sind. Wir wollen zunächst dazu äquivalente 
LOOP-Programm angeben  und dann diese Funktionen/Konstrukte dann auch als Abkürzungen
in anderen LOOP-Programmen verwenden.

\begin {itemize}
\item  Eine Kopierzuweisung '$x_i:= x_k$' ergibt sich zum Beispiel durch
 die Zuweisung '$x_i:=x_k + 0$' mit der Konstanten $c=0$.
\item 
 Eine Zuweisung '$x_i := c$' erhält man durch '$x_i:=x_k+ c$', wenn man dabei
 eine Variable $x_k$ nutzt, die immer den Wert $0$ hat.
\item Bedingte Ausführungen '\texttt{\bfseries IF $x_k= 0$ THEN $Q $ END}' sind 
implementierbar durch
\[\texttt{\bfseries \begin{tabular}{l}
$y := 1$;\\
LOOP $x_k$ DO $y := 0$ END;\\
LOOP $y$ DO $Q$ END
\end{tabular}}\]
mit einer ansonsten nicht benutzten Variable $y$
\item Als \"Ubungsaufgabe: '\texttt{\bfseries IF $x_k = 0$ THEN $Q$ ELSE $R$ END}'
\end{itemize}
}

\only<presentation>{
Im Folgenden: `Programmierübungen' mit LOOP-Programmen...\pause\\
(später als abgekürzte Schreibweisen für LOOP-Programme benutzt...)\pause\\


\begin {itemize}
\item  Zuweisung '$x_i:= x_k$' \pause durch  '$x_i:=x_k + 0$' \pause\\
 mit der Konstanten $c=0$\pause
\item  Zuweisung '$x_i := c$' \pause durch '$x_i:=x_k+ c$' \pause\\
für eine Variable $x_k$, die immer Wert $0$ hat.\pause
\item Bedingte Ausführung '\texttt{\bfseries IF $x_k= 0$ THEN $Q $ END}' \pause  durch
\[\texttt{\bfseries \begin{tabular}{l}
$y := 1$;\\
LOOP $x_k$ DO $y := 0$ END;\\
LOOP $y$ DO $Q$ END
\end{tabular}}\]
\pause mit einer ansonsten nicht benutzten Variable $y$\pause
\item Bedingte Ausführung '\texttt{\bfseries IF $x_k = 0$ THEN $Q$ ELSE $R$ END}' \pause\\ als \"Ubungsaufgabe...
\end{itemize}
}

\end{frame}

\begin{frame}
\begin {itemize}
\item Additionen '$x_i := x_j + x_k$' mit $i\neq j$:\pause
\[\texttt{\bfseries \begin{tabular}{l}
$x_i := x_k$; \\ 
 LOOP $x_j$ DO $x_i := x_i + 1$ END 
\end{tabular}}\]

 \only<article>{\item Der Spezialfall '$x_0:=x_1+x_2$' berechnet damit die 
Additionsfunktion $+:\nz^2\rightarrow\nz$ im
Sinne von Definition \ref{LOOP-Berechenbarkeit}}

 \only<presentation>{\item \pause Spezialfall '$x_0:=x_1+x_2$': \pause\\ berechnet Addition 
$+:\nz^2\rightarrow\nz$ in Sinne von Definition \ref{LOOP-Berechenbarkeit}\pause}


\item Der Fall $i=j$, d.h. '$x_i := x_i + x_k$', \pause ist sogar noch einfacher:
\[\texttt{\bfseries \begin{tabular}{l} 
 LOOP $x_k$ DO $x_i := x_i + 1$ END 
\end{tabular}}\]

\only<article>{\item  Die Subtraktion '$x_i := x_j - x_k$' 
 (wieder mit der Konvention, dass der Wert 0 herauskommen soll, wenn 
 $x_j<x_k$
  ist)  kann ähnlich berechnet werden. }

\only<presentation>{\item \pause Subtraktion '$x_i := x_j - x_k$': \pause ähnlich...\pause\\
 (wieder mit Wert 0 bei  $x_j<x_k$) }
\end{itemize}
\end{frame}

\begin{frame}
\begin{itemize}
\item Multiplikationen '$x_i := x_j\cdot x_k$'\pause
\[\texttt{\bfseries \begin{tabular}{l}
$x_i := 0$; \\ 
 LOOP $x_j$ DO $x_i := x_i + x_k$ END 
\end{tabular}}\]
\pause was wiederum nur eine Abkürzung ist für \pause
\[\texttt{\bfseries \begin{tabular}{l}
$x_i := 0$; \\ 
LOOP $x_j$ DO\\ 
~~~LOOP $x_k$ DO $x_i := x_i + 1$ END\\
END 
\end{tabular}}\]
\end{itemize}
\end{frame}

\begin{frame}
\begin{itemize}
\item Die `Signum'-Funktion $sg:\nz\rightarrow\nz$ \pause mit 
\[sg(x):=\left\{\begin{array}{l}
1\textrm{ falls } x>0\\
0\textrm{ falls } x=0
\end{array}\right.\]
\pause ist realisierbar über\pause 
\[\texttt{\bfseries \begin{tabular}{l}
$x_0 := 1$; \\
IF $x_1 = 0$ THEN $x_0 := 0$ END
\end{tabular}}\]

\item \pause Die inverse Signum-Funktion $\overline{sg}(x):= 1 - sg(x)$ \pause\\
  kann ähnlich berechnet werden. \pause

\item  Die `Gleichheits'-Funktion $se(x,y)$ 
 mit \[se(x,y):=\left\{\begin{array}{l}
1\textrm{ falls } x=y\\
0\textrm{ falls } x\neq y
\end{array}\right.\]
\pause kann über die Funktionen 
$sg$
 und $\overline{sg}$ realisiert werden.
\end{itemize}
\end{frame}


\begin{frame}
\begin{itemize}
\item Ganzzahldivision  \textrm{$x_i:= x_j$ DIV $x_k$} mit $x_k>0$:\pause

 Dazu  zunächst 
 '\texttt{\bfseries IF $x_k\leq x_j$ THEN $Q$ END}' \pause über 
\[\texttt{\bfseries \begin{tabular}{l}
$x_0 := x_k - x_j$;\\ 
$x_1 := \overline{sg}(x_0)$;\\ 
 LOOP $x_1$ do $Q$ END 
\end{tabular}}\]


\pause Damit erhalten wir  `$x_i:= x_j$ DIV $x_k$' durch: \pause\\ 
\[\texttt{\bfseries \begin{tabular}{l}
$x_i := 0$; \\ 
 LOOP $x_j$ DO \\ 
~~~IF $x_k\leq x_j$ THEN $x_i := x_i + 1$ END; \\ 
~~~$x_j := x_j - x_k$;\\ 
 END 
\end{tabular}}\]


\item  \pause  Zur Übung realisieren Sie z.B. die Modulo-Funktion \textrm{MOD}
als LOOP-Programm (wird später noch benötigt...).
\end{itemize}

\end{frame}


\begin{frame}
\begin{itemize}\label{CantorLOOP}
\item Weitere Übung: Cantor'sche Bijektion $\langle\cdot,\cdot\rangle: \nz^2\to\nz$\pause
$$\langle x,y\rangle~~:=~~y+ \sum_{i\leq x+y} i ~~=~~y+\frac{(x+y)(x+y+1)}{2}$$
\pause
{\tiny$$\begin{array}{|c||c|c|c|c|c|c|c}
\hline 
 \langle x,y\rangle & 0 & 1 & 2 & 3 & 4 &5 &\ldots\\\hline\hline
 0 & 0 & 2 & 5 & 9 & 14 & 20 &\ldots\\ \hline 
 1 & 1 & 4 & 8 & 13 & 19 &26 &\ldots\\ \hline 
 2 & 3 & 7 & 12 & 18 & 25 &33 &\ldots\\ \hline 
 3 & 6 & 11 & 17 & 24 & 32 &41&\ldots\\ \hline 
 4 & 10 & 16 & 23 & 31 & 40 &50&\ldots\\ \hline 
 5 & 15 & 22 & 30 & 39 & 49 &60&\ldots\\ \hline 
\vdots &\vdots&\vdots&\vdots&\vdots&\vdots&\vdots
\end{array}$$}

\end{itemize}
\end{frame}
\begin{frame}
Sowohl die Bijektion von $\nat\times\nat\to\nat$ als auch die einzelnen Komponenten $p_1, p_2:\nat\to\nat$
der Umkehrfunktion (d.h. $\langle p_1(z),p_2(z)\rangle = z$) sind LOOP-berechenbar:\pause 
\begin{itemize}
\item Berechnung von $y+ \sum_{i\leq x+y} i$ benötigt i.W. LOOP-Schleife  mit Additionen\pause
\item Berechnung der  Komponenten $p_1(z), p_2(z)$: 
\begin{itemize}
\item Suche (von $k=0,...,z$) nach größtem $k$ mit $\sum_{i\leq k} i\leq z$.\pause
\item Dann $p_2(z)=z-\sum_{i\leq k}$ \pause und $p_1(z)=k - p_2(z) $.
\end{itemize}
\end{itemize}

\end{frame}

\begin{frame}
\only<article>{ Nun wollen wir die LOOP-Programme um ein weiteres Programmkonstrukt 
 erweitern, die WHILE-Schleife, und erhalten damit WHILE-Programme.
 
Die syntaktischen Grundbausteine von WHILE-Programmen sind dabei:}
 
\only<presentation>{Erweiterung der LOOP-Programme zu WHILE-Programmen:\pause}
\begin{itemize}
\item unverändert wie bei Loop:\\
Variablen $x_0$ $x_1$ $x_2$ $\ldots$, \\
Konstanten   $0$  $1$   $2$ $\ldots$,\\
Trennsymbole und Operationszeichen $~~;~~$   $~~:=~~$     $~~+~~$    $~~-~~$\pause
\item  Schlüsselwörter: ~~~\texttt{\bfseries LOOP}\pause~~~ \pause \texttt{\bfseries DO} ~~~\pause \texttt{\bfseries END}
\item neues, zusätzliches Schlüsselwort: \pause~~~\texttt{\bfseries WHILE}
\end{itemize}

\pause WHILE-Programme sind dann wie folgt definiert: \pause
\begin{itemize}
\item Jede Wertzuweisung $x_i  := x_j + c$ und  $x_i  := x_j - c$ ist ein WHILE-Programm  (für Variablen $x_i, x_j$ und Konstanten $c$).\pause
\item Sind $P_1$ und $P_2$ WHILE-Programme,  \pause\\dann  ist auch $P_1;P_2$ ein WHILE-Programm.\pause
\item Ist $x$ Variable und $P$ WHILE-Programm,  \pause dann sind auch \\\texttt{\bfseries LOOP $x$ DO $P$ END} und   \texttt{\bfseries WHILE $x$ DO $P$ END} WHILE-Programme\pause
\item Weitere Konstruktionen sind nicht zugelassen.
\end{itemize}
\end{frame}


\begin{frame}

Jedes LOOP-Programm ist damit auch ein WHILE-Programm.\pause

\pause Die Semantik von WHILE-Programmen wird analog zu LOOP definiert.

Wichtig ist dabei die Semantik der neuen WHILE-Schleife: \pause\\
\begin{itemize}\item Bei \texttt{\bfseries \bfseries WHILE $x$ DO $P$ END} wird
wiederholt $P$ ausgeführt,\\ bis \pause der (\Fb{sich evtl. ändernde!}) Inhalt von 
$x$ \pause\\ zu Beginn des Schleifenrumpfes $P$ den Wert.
$0$ hat.\pause
\item Bei \texttt{\bfseries \bfseries LOOP $x$ DO $P$ END}  \pause wurde $P$ so oft ausgeführt,\\ wie der Wert
von $x$ \emph{\Fb{zu Beginn}} der LOOP-Anweisung angibt. \pause
\end{itemize}

Also: \begin{itemize}\item
LOOP-Programme müssen im Voraus wissen, wie oft eine Schleife ausgeführt wird.\pause
\item
WHILE-Programme können hingegen unbeschränkt `suchen'...
\end{itemize}
\end{frame}


\begin{frame}

\only<article>{Auch mit WHILE-Programmen kann man Zahlenfunktionen berechnen:}

\begin{definition}[WHILE-Berechenbarkeit] 
\only<article>{ Eine Funktion $f: \nz^k\Partial  \nz$
hei"st WHILE-berechenbar, falls es ein WHILE-Programm $P$
 gibt, so dass $P$
 gestartet mit der beliebigen Eingangsbelegung 
 $n_1,..., n_k$
 aus $\nz$
 in den Variablen $x_1,..., x_k $
und $0$ in allen anderen Variablen 
mit dem Wert $f(n_1,...,n_k)$ 
in der Variablen $x_0$ nach endlich vielen Schritten stoppt, 
falls $f(n_1,..., n_k)$ definiert ist, und nie stoppt, falls 
$f(n_1,...,n_k)$ nicht definiert ist.}
\only<presentation>{\pause Eine Funktion $f: \nz^k\Partial  \nz$
hei"st WHILE-berechenbar, falls\pause
\begin{itemize}
\item es ein WHILE-Programm $P$ gibt, so dass $P$\pause
\item
 gestartet mit $n_1,..., n_k$ aus $\nz$
 in den Variablen $x_1,..., x_k $\pause
\item und $0$ in allen anderen Variablen \pause
\item mit $f(n_1,...,n_k)$ 
in $x_0$  stoppt, \pause
falls $f(n_1,..., n_k)$ definiert ist, \pause
\item
und nie stoppt, \pause falls  $f(n_1,...,n_k)$ nicht definiert ist.
\end{itemize}
}
\end{definition}
\end{frame}


\begin{frame}

Bei WHILE-Programmen kann man auf die LOOP-Anweisung sogar komplett verzichten, \pause
'\texttt{\bfseries LOOP $x_j $ DO $P $ END}' wird simuliert durch\pause
\[\texttt{\bfseries \begin{tabular}{l}
$x_k := x_j$;\\
WHILE $x_k$ DO $x_k := x_k - 1$; $P$  END 
\end{tabular}}\]
\pause Dabei sei $x_k $  eine Variable, die im Programm $P $
nicht verwendet wird.\pause

 Alle LOOP-berechenbaren Funktionen sind WHILE-berechenbar. \pause

 Die Umkehrung gilt nicht, \pause z.B. für die partielle Funktion  $f$ mit
\[f(x):=\left\{\begin{array}{ll}
42&\textrm{ falls } x=0\\
undefiniert&\textrm{ falls } x>0
\end{array}\right.\]
\pause $f$ ist sicher nicht LOOP-, aber WHILE-berechenbar:\pause
\[\texttt{\bfseries \begin{tabular}{l}
     WHILE $x_1$ DO $x_1 := x_1+ 1$ END; $x_0 := 42$
\end{tabular}}\]

\pause Es gibt sogar \emph{totale} Funktionen, 
die nicht LOOP-, aber WHILE-berechenbar sind (z.B. Ackermann-Funktion)!

\end{frame}


\begin{frame}
\only<article>{Wir haben im letzten Kapitel gesehen, dass man alle Programmkonstrukte, die in 
WHILE-Programmen vorkommen, durch Mehrband-Turingmaschinen realisieren kann. Zum 
Beispiel kann man den Inhalt der $i$-ten Variablen $x_i $
 binär auf Band $i $
der Maschine speichern. 
Au"serdem haben wir gesehen, dass man Mehrband-Turingmaschine durch Einband-Turingmaschinen, also gewöhnliche Turingmaschinen simulieren kann. 
Daher gilt der folgende Satz: }
\only<presentation>{
Vergleich WHILE-Programm mit Mehrband-Turingmaschinen:\pause
\begin{itemize}
\item Per Induktion über Aufbau von WHILE-Programmen:\\ 
Für jedes WHILE-Programm gibt es eine MTM, die die gleiche Funktion
berechnet)\pause
\item Verwende pro benutzter Variable $x_i$ ein eigenes Band $i$ der MTM, 
nutze die bereits betrachteten MTM-Konstruktionen
\end{itemize}
\pause Damit sofort:\pause}

\begin{theorem}\label{WHILE2Turing}
 Jede WHILE-berechenbare Zahlenfunktion ist Turing-berechenbar. 
\end{theorem}

\end{frame}



\begin{frame}
\only<article>{
 Schlie"slich möchten wir noch den \"Aquivalenzbeweis vollenden, 
 indem wir den folgenden Satz beweisen.}

\begin{theorem}
 Turing-berechenbare Zahlenfunktionen sind WHILE-berechenbar.
\end{theorem}

\only<article>{
 Zum Beweis starten wir mit einer Turingmaschine
  $TM= (S, E, A, \delta, s_0, \Box, F)$ 
  zur Berechnung einer Zahlenfunktion $f$.
 Wir simulieren sie durch ein WHILE-Programm aus drei Teilen. 

 Der erste Teil transformiert die Zahlen 
 $n_1,..., n_l$ der Eingabe von $f$
  in Binärdarstellung und stellt die Startkonfiguration der $TM$
 mittels dreier Zahlenvariablen $x, y, z$
 dar, die gleich erklärt werden. 

 Der zweite Programmteil simuliert die Berechnung der Turingmaschine 
 Schritt für Schritt durch entsprechende \"Anderung der 
 drei Zahlenvariablen  $x, y, z$. Dabei wird die Konfiguration 
 der TM zu jedem Zeitpunkt komplett in den drei Zahlenvariablen gespeichert.


 Der dritte Teil erzeugt schlie"slich am Ende der 
 Rechnung aus den drei Zahlenvariablen, die dann die Endkonfiguration der $TM$
 codieren, den Ausgabewert (eine Zahl) in der Variablen $x_0$.
}
\only<presentation>{\pause Gegeben Turingmaschine
  $$TM= (S, E, A, \delta, s_0, \Box, F)$$
  zur Berechnung einer Zahlenfunktion $f$.\pause


$TM$ wird durch WHILE-Programm aus drei Teilen simuliert:\pause
\begin{enumerate}
\item 
 Eingabe  $n_1,..., n_l$ für $f$ wird in drei Zahlen $x, y, z$
 umgerechnet, die die Startkonfiguration der $TM$ darstellen,\pause\\
 $x,y,z$ werden dabei in Variablen gespeichert!\pause
\item
 Die Berechnung durch $TM$ wird 
 Schritt für Schritt durch entsprechende \"Anderung der 
 drei Zahlen $x, y, z$ nachvollzogen\pause
\item
 Aus den Zahlen $x,y,z$, die die Endkonfiguration beschreiben,
 wird der Ausgabewert extrahiert und  in  $x_0$ gespeichert
\end{enumerate}
}

\end{frame}

\begin{frame}
\only<article>{

 Wir beschreiben dies etwas genauer.

 
 Sei die Zustandsmenge 
 $S = \{s_0,..., s_k\}$ und das Arbeitsalphabet 
 $A = \{a_1,..., a_m\}$, sowie 
 $b$ eine Zahl mit $b>m$. 

Dann wird eine Konfiguration 
     $$a_{i_1}...a_{i_p}s_la_{j_1}...a_{j_q}$$
 der Turingmaschine dadurch beschrieben, dass die Variablen die Werte 
 $x = (i_1...i_p)_b, 
y= (j_q...j_1)_b$ und $z=l$
 annehmen. 

Dabei sei hier
\[(i_1...i_p)_b = \sum_{l=1}^{p} i_l\cdot b^{ p - l}\]
 also ist $x $
eine Codierung der Ziffern $i_1,\ldots i_p$
in einer einzigen Zahl. 
Bei $y$
 sei nur die Reihenfolge der Ziffern andersherum. Das hei"st, in $x $
speichern wir die Inschrift des Bandes links vom Lese-Schreibkopf. In $y$
 speichern wir die Inschrift des Bandes ab der Position 
 unter dem Lese-Schreibkopf und rechts davon. 
 In $z$
 speichern wir den aktuellen Zustand.
}
\only<presentation>{
 Sei 
 $$S = \{s_0,..., s_k\}~~~~A = \{a_1,..., a_m\}$$
\pause Wähle  $b\in \nz$ mit $b>m$\pause

Eine Konfiguration 
     $$a_{i_1}...a_{i_p}~s_l~a_{j_1}...a_{j_q}$$
\pause wird durch drei Zahlen $x,y,z$ beschrieben:\pause
 $$x = (i_1...i_p)_b~\pause~~~y= (j_q...j_1)_b~\pause~~~z=l$$
\pause Dabei sei 
\[(i_1...i_p)_b = \sum_{l=1}^{p} i_l\cdot b^{ p - l}\]
\pause d.h. Worte werden als Zahlen zur Basis $b$ notiert.\pause

 Wichtig: Bei $y$ ist die Reihenfolge der Ziffern vertauscht! \pause

\begin{itemize}\item  $x$:  Bandinschrift links des Lese-Schreibkopfes\pause
\item$y$: Bandinschrift rechts des Lese-Schreibkopfes,\pause\\ inklusive dem Zeichen unter dem Kopf\pause
\item $z$: aktueller Zustand der $TM$
\end{itemize}
}
\end{frame}


\begin{frame}
\only<article>{
 Das mittlere, zweite  Programmstück simuliert nun eine Schleife mit 
 einer einzigen gro"sen Verzweigung:

\texttt{\bfseries \begin{tabular}{l}
WHILE Zustand $s$ ist kein Endzustand DO\\
~~~~Bestimme Zeichen $a$ unter dem Kopf;\\
~~~~IF ($s=s_0$) und ($a=a_1$):\\
~~~~~~~simuliere $\delta(s_0,a_1)$ in $x,y,z$;\\
~~~~ELSE IF...\\
~~~~~~~...\\
~~~~ELSE IF ($s=s_k$) und ($a=a_m$):\\
~~~~~~~simuliere $\delta(s_k,a_m)$ in $x,y,z$;\\
END WHILE; 
\end{tabular}}

Die Bestimmung des \emph{Zeichens} $a$ können wir durch die Berechnung der 
\emph{Zahl} `$y $ MOD $ b$' simulieren; damit entspricht der Vergleich `$a=a_j$' dem Test `$y $ MOD $b=j$'.
Der Vergleich `$s=s_i$' zweier Zustände
entspricht dem Zahlenvergleich
`$z=i$'.

 Es gibt insgesamt $(k{+}1)*m$
 verschiedene Fälle, die abhängig von den Werten von $s$
 (es gibt $k{+}1$ Zustände $s$) und 
 $a$  (es gibt $m$ Symbole $a$ im Arbeitsalphabet $A$) auszuwählen sind.
}
\only<presentation>{
Simulation der Schritte der $TM$ durch Wiederholung einer gro"sen Verzweigung:\pause

\texttt{\bfseries \begin{tabular}{l}
WHILE Zustand $s$ ist kein Endzustand DO\\
~~~~Bestimme Zeichen $a$ unter dem Kopf;\\
~~~~IF ($s=s_0$) und ($a=a_1$):\\
~~~~~~~simuliere $\delta(s_0,a_1)$ in $x,y,z$;\\
~~~~ELSE IF...\\
~~~~~~~...\\
~~~~ELSE IF ($s=s_k$) und ($a=a_m$):\\
~~~~~~~simuliere $\delta(s_k,a_m)$ in $x,y,z$;\\
END WHILE; \pause  
\end{tabular}}

\begin{itemize}
\item Bestimmung des \emph{Zeichens} $a$: Berechnung der 
\emph{Zahl} `$y $ MOD $ b$'\pause
\item Vergleich `$a=a_j$' entspricht Test `$y $ MOD $b=j$'\pause 
\item Vergleich `$s=s_i$' entspricht Test `$z=i$'.
\end{itemize}
Insgesamt $(k{+}1)*m$
 verschiedene Fälle:\pause
\begin{itemize}\item für  $k{+}1$ Zustände $s$ \pause und
\item für $m$ Symbole $a$ im Arbeitsalphabet $A$ (unter dem Kopf)
\end{itemize}
}
\end{frame}

\begin{frame}
\only<article>{
Bei der Simulation der \"Ubergangsfunktion $\delta(s_i, a_j) =(s_i', a_j', B)$ muss
 die Folgekonfiguration in den Variablen $x, z, y$ erstellt werden: 


Im Folgenden betrachten als Beispiel wir den Fall $B = L$. Hier wird der Zustand angepasst, also die Variable $z $
entsprechend geändert, $y$
 wird zunächst um den letzten Eintrag $j$
 verkürzt, dann um $j'$
 verlängert und schlie"slich weiter um den $x$-Anteil 
verlängert, was die Kopfbewegung nach links simuliert. Schlie"slich wird $x$
 entsprechend verkürzt. 

Bei $x\neq 0$, d.h. links vom Kopf der Turingmaschinen stehen noch Zeiochen, geschieht mit den folgenden Anweisungen, 
die durch WHILE-Programme simuliert werden können:

 \begin{tabular}{l}
     $z := i'$; \\ 
     $y:= y $ DIV $ b$; \\ 
     $y:= b*y + j'$; \\ 
     $y:= b*y + (x$ MOD $b)$; \\ 
     $x := x$ DIV $ b$;
\end{tabular}

Im Fall $x=0$, also keinen weiteren Zeichen links vom Kopf der Maschine, muss ein Blank `eingefügt' werden, was durch $y:= b*y + j_{\Box}$ an Stelle von $y:= b*y + (x$ MOD $b)$
möglich ist (wobei $j_{\Box}$ der Index von $\Box$ in $A$ sei). 

 Ist die Maschine im Endzustand angelangt, so wird in 
 den dritten Teil des WHILE-Programmes verzweigt. 
 Die Konstruktionen dieses und des ersten Teils hängen 
 nicht von der \"Ubergangsfunktion d der Turingmaschine ab. 

 Damit haben wir auch Satz \ref{WHILE2Turing} bewiesen.
}
\only<presentation>{
Simulation der \"Ubergangsfunktion $\delta(s_i, a_j) =(s_{i'}, a_{j'}, B)$:\pause\\
Erstellung der  Folgekonfiguration in den Variablen $x, z, y$\pause

Hier nur  $B = L$ bei $x \neq0$ als Beispiel:

 \begin{tabular}{l}
     \pause$z := i'$; \\ 
     \pause$y:= y $ DIV $ b$;\\ 
     \pause$y:= b*y + j'$; \\ 
     \pause$y:= b*y + (x$ MOD $b)$; \\ 
     \pause$x := x$ DIV $ b$;
\end{tabular}

\pause D.h.:
\begin{itemize}
\item Variable für $z$ direkt passend für Zustand $s_{i'}$ ändern,\pause
\item $a_{j'}$ als neues letztes Zeichen in $y$ vermerken (statt $a_j$) \pause und
\item   letztes Zeichen aus $x$ in $y$ übertragen (Kopf nach links!)
\item bei $x=0$ statt $y:= b*y + (x$ MOD $b)$ nun $y:= b*y + j_\Box$ (bei $a_{j_\Box}=\Box$) 
\end{itemize}

\pause Erster Teil (Kodierung der Eingabe) und dritter Teil (Extraktion der Ausgabe): \pause i.W. analog...
}
\end{frame}

\begin{frame}
Als Folgerung aus der Konstruktion ergibt sich:
\begin{theorem}\label{WHILE-Anzahl}
 Jedes Turing-Programm kann durch ein WHILE-Programm \\mit 
 nur einer einzigen WHILE-Schleife berechnet werden.
\end{theorem}

\only<article>{ Achtung:
 es wird in der  Simulation nur eine einzige WHILE-Schleife gebraucht, 
aber viel möglicherweise viele LOOP-Schleifen. 
 Dies führt zu dem folgenden Satz.}
\only<presentation>{\pause...nur eine WHILE-Schleife, aber evtl.\ viele LOOP-Schleifen $\Rightarrow$\pause}

\begin{theorem}[Kleenesche Normalform für WHILE-Programme]
\pause Zu jedem WHILE-Programm gibt es ein äquivalentes 
WHILE-Programm mit nur einer einzigen WHILE-Schleife.\pause
\end{theorem}


\only<article>{Zum Beweis transformiere man erst ein WHILE-Programm 
 für die jeweilige WHILE-berechenbare Funktion in ein Turing-Programm 
 (wir haben oben gesehen, wie das geht) und dieses dann 
 wieder in ein WHILE-Programm mit nur einer WHILE-Schleife.}
\only<presentation>{Dazu: \begin{itemize}\item
Transformiere  WHILE-Programm $P$ in  Turing-Programm $P'$\pause\item
Transformiere  Turing-Programm $P'$ in WHILE-Programm $P''$\pause\\ 
mit nur einer WHILE-Schleife (nach \ref{WHILE-Anzahl})
\end{itemize}}

\end{frame}



