\section{LOOP- und WHILE-Berechenbarkeit} \inhalta{1-7} \begin{frame} \only
{ 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{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
{Mit LOOP-Programmen kann man Zahlenfunktionen berechnen:} \begin{definition}[LOOP-Berechenbarkeit]\label{LOOP-Berechenbarkeit} \only
{ 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{ \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
{ 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{ 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
{ 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{ 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
{\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{\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
{\item Die Subtraktion '$x_i := x_j - x_k$' (wieder mit der Konvention, dass der Wert 0 herauskommen soll, wenn $x_j{\item \pause Subtraktion '$x_i := x_j - x_k$': \pause ähnlich...\pause\\ (wieder mit Wert 0 bei $x_j0\\ 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
{ 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{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
{Auch mit WHILE-Programmen kann man Zahlenfunktionen berechnen:} \begin{definition}[WHILE-Berechenbarkeit] \only
{ 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{\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
{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{ 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
{ 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
{ 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{\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
{ 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{ 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
{ 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{ 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
{ 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{ 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
{ 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{\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
{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{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}