\section{Standardnotationen für berechenbare Funktionen} \inhalta{3-9} \only
{ In den letzten Kapiteln haben wir gesehen, dass es einen mathematisch präzise definierten Berechenbarkeitsbegriff für Zahlenfunktionen gibt, der der Churchschen These zufolge gerade die intuitiv berechenbaren Zahlenfunktionen beschreibt. Ein Indiz für die Natürlichkeit dieses Berechenbarkeitsbegriffs ist die Tatsache, dass ganz verschiedene Ansätze alle zu dem gleichen Berechenbarkeitsbegriff geführt haben. In diesem Abschnitt halten wir zuerst fest, dass der über Turingmaschinen eingeführte Berechenbarkeitsbegriff für Wortfunktionen gleicherma"sen natürlich ist und in gewisser Weise äquivalent zu dem für Zahlenfunktionen ist. Anschlie"send beschäftigen wir uns mit der Frage, welche Eigenschaften eine Programmiersprache für berechenbare Funktionen haben sollte. } \begin{frame} \begin{example} \label{Wort-Zahl} \only
{ Die berechenbaren Wortfunktionen haben wir über Turingmaschinen definiert. Da wir die berechenbaren Zahlenfunktionen über Turingmaschinen definiert haben, ist es naheliegend, eine These ähnlich der Churchschen These nun auch für die berechenbaren Wortfunktionen aufzustellen: die durch Turingmaschinen berechenbaren Wortfunktionen sind genau die intuitiv berechenbaren Wortfunktionen. Wir wollen dies auch noch dadurch belegen, dass wir eine natürliche Bijektion zwischen berechenbaren Wortfunktionen und berechenbaren Zahlenfunktionen herstellen. Sei $E = \{e_1, e_2, \ldots, e_n\}$ ein endliches Alphabet. Wir definieren eine Bijektion $\nu:\nz\rightarrow E^*$, indem wir die Wörter in $E^*$ der Länge nach und Wörter gleicher Länge alphabetisch sortieren: } \only{ Sei $E = \{e_1, e_2, \ldots, e_n\}$ ein endliches Alphabet. \pause Definiere Bijektion $\nu:\nz\rightarrow E^*$ durch Sortieren:\pause \begin{itemize} \item Wörter in $E^*$ nach Länge sortiert\pause \item Wörter gleicher Länge alphabetisch sortiert\pause \end{itemize} } {\small\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c} \hline i & 0 & 1 & 2 & \ldots & n & n{+}1 & n{+}2 & \ldots & n^2 {+}n & n^2{+}n{+}1 & \ldots \\ \hline \nu(i) &\pause \varepsilon& \pause e_1 & \pause e_2 & \pause \ldots & \pause e_n &\pause e_1e_1 & \pause e_1e_2 & \pause \ldots & \pause e_n e_n & \pause e_1e_1e_1 & \pause \ldots \\ \hline \end{array}\]} \only
{ Es ist klar, dass diese Abbildung $\nu:\nz\rightarrow E^*$ eine Bijektion ist. Daher ist auch ihre Umkehrabbildung $\nu^{-1} : E^* \rightarrow\nz$ definiert. Ist nun $f:\nz\Partial\nz$ eine einstellige Zahlenfunktion, so wird durch $\nu\circ f\circ\nu^{-1}$ eine Wortfunktion definiert, die man erhält, indem man auf das Eingabewort $w $ erst die Abbildung $\nu^{-1}$ anwendet, dann auf die erhaltene Zahl $\nu^{-1}(w)$ die Zahlenfunktion $f$, und dann auf die erhaltene Zahl $f\nu^{-1}(w)$ wiederum die Bijektion $\nu$, die die Zahl wieder in das korrespondierende Wort umwandelt. Ist andererseits $g: E^* \Partial E^*$ eine Wortfunktion, so wird durch $\nu^{-1}\circ g\circ \nu$ eine einstellige Zahlenfunktion definiert. Es ist klar, dass diese beiden Zuordnungen genau invers zueinander sind. Also definieren sie eine Bijektion zwischen der Menge aller (möglicherweise partiellen) Zahlenfunktionen $f:\nz\Partial \nz$ und der Menge aller (möglicherweise partiellen) Wortfunktionen $g: E^* \Partial E^*$. } \only{ \begin{itemize} \item \pause Abbildung $\nu:\nz\rightarrow E^*$ ist eine Bijektion\pause \item Umkehrabbildung $\nu^{-1} : E^* \rightarrow\nz$ ist definiert \pause und ebenfalls bijektiv. \end{itemize} } \end{example} \end{frame} \only{ \begin{frame} \begin{itemize} \item Ist $f:\nz\Partial\nz$ einstellige Zahlenfunktion, \pause\\ so ist $\Gamma(f):=\nu\circ f\circ\nu^{-1}\pause $ eine Wortfunktion:\pause $$\Gamma(f)=\nu\circ f\circ\nu^{-1}: \pause E^* \pause \stackrel{\nu^{-1}}{\longrightarrow}\pause \nz\pause \stackrel{f}{\Partial}\pause \nz\pause \stackrel{\nu}{\longrightarrow} \pause E^*$$ \item \pause Ist $g: E^* \Partial E^*$ eine Wortfunktion,\pause\\ so ist $\Delta(f)=\nu^{-1}\circ g\circ \nu$ einstellige Zahlenfunktion\pause \item Es ist $\Delta\circ\Gamma(f)=\pause\nu^{-1}\circ\left(\nu\circ f\circ\nu^{-1}\right)\circ\nu\pause =f$ \pause \\ und analog $\Gamma\circ\Delta(g)=g$ \end{itemize} \pause $\Rightarrow$ $\Delta$ und $\Gamma$ definieren Bijektion \pause zwischen: \begin{itemize} \item Menge aller Zahlenfunktionen $f:\nz\Partial \nz$ \pause und \item Menge aller Wortfunktionen $g: E^* \Partial E^*$ \end{itemize} \end{frame}} \begin{frame} \begin{theorem}\only
{~} \begin{enumerate} \item \pause Ist $f:\nz\Partial \nz$ eine (Turing-)berechenbare Zahlenfunktion, \pause so ist $\nu\circ f\circ \nu^{-1}$ eine (Turing-)berechenbare Wortfunktion.\pause \item Ist $g: E^* \Partial E^*$ eine (Turing-)berechenbare Wortfunktion, \pause so ist $\nu^{-1}\circ g \circ\nu$ eine (Turing-)berechenbare Zahlenfunktion. \end{enumerate} \end{theorem} \only
{ Wir beweisen (1). Der Beweis von (2) geht analog. Sei $f: \nz\Partial \nz$ eine berechenbare Zahlenfunktion. Dann gibt es eine Turingmaschine $TM$, die aus der Binärdarstellung $bin(n)$ einer Zahl $n$ im Definitionsbereich von $f$ die Binärdarstellung $bin(f(n))$ von $f(n)$ berechnet. Wir müssen eine Turingmaschine konstruieren, die aus einem Wort $w $ im Definitionsbereich von $\nu\circ f\circ\nu^{-1}$ das Wort $ \nu\circ f\circ\nu^{-1}(w)$ berechnet. Eine solche Turingmaschine kann folgenderma"sen vorgehen: zuerst bestimmt sie aus dem Wort $w $ die Binärdarstellung $bin(\nu^{-1}(w))$ der Zahl $\nu^{-1}(w)$. Darauf wendet sie die Turingmaschine $TM $ an. Das Ergebnis, das natürlich die Binärdarstellung der Zahl $f(\nu^{-1}(w))$ ist, wird schlie"slich wieder codiert in das Wort $\nu(f(\nu^{-1}(w)))$. Das Ganze geht mit Turingmaschinen, da die Funktion, die Wörter $w$ auf $bin(\nu^{-1}(w))$ abbildet, sicher berechenbar ist, ebenso ihre Umkehrung. } \only{\pause Beweis von (1):\pause \begin{itemize} \item Sei $f: \nz\Partial \nz$ berechenbare Zahlenfunktion.\pause \item Betrachte entsprechende Turingmaschine $TM$:\pause $TM$ berechne aus $bin(n)$ den Wert $bin(f(n))$\pause\\ (für $n$ aus dem Definitionsbereich von $f$)\pause \item Aufgabe: konstruiere Turingmaschine $TM'$,\pause\\ die aus $w $ das Wort $ \nu\circ f\circ\nu^{-1}(w)$ berechnet,\pause\\ (für $w$ im Definitionsbereich von $\nu\circ f\circ\nu^{-1}$) \end{itemize}} \end{frame} \begin{frame} \only{ Vorgehensweise von $TM'$:\pause \begin{itemize} \item Erst aus Wort $w $ das Wort $bin(\nu^{-1}(w))$ bestimmen\pause \item Auf $bin(\nu^{-1}(w))$ die Turingmaschine $TM $ anwenden. \pause \item Auf (binär kodiertes) $f(\nu^{-1}(w))$ wiederum $\nu$ anwenden,\pause\\ mit Resultat $\nu(f(\nu^{-1}(w)))$. \pause \item Das Ganze geht mit Turingmaschinen, \pause da die Funktion, die Wörter $w$ auf $bin(\nu^{-1}(w))$ abbildet, sicher berechenbar ist, \pause ebenso ihre Umkehrung. \end{itemize} \pause Beweis von (2): analog...\pause Damit: \\ Berechenbarkeitsbegriffe für Zahlen / für Funktionen gleichwertig.\pause Im Folgenden analog Funktionen $\nz\Partial E^*$ und $E^*\Partial\nz$ verwendet... } \only
{ Der Satz zeigt, dass die Berechenbarkeitsbegriffe für Zahlen und für Funktionen im Wesentlichen gleichwertig sind. Wir werden in der Zukunft manchmal einfach von berechenbaren Funktionen sprechen. Zum Teil werden wir auch als Eingabe Wörter und als Ausgabe Zahlen zulassen oder umgekehrt. Diesen Fall kann man mit Hilfe der Bijektion $\nu$ auf den Fall der berechenbaren Wortfunktionen zurückführen.} \end{frame} \only
{ Im zweiten Teil dieses Abschnitts möchten wir uns mit der Frage beschäftigen, ob und wie man eine beliebige berechenbare Funktion durch ein Wort beschreiben kann. Wir wollen nur Funktionen über einem festen Alphabet $E $ betrachten, das mindestens die Symbole $0$, $1$ und $\#$ enthalten möge. Es liegt nahe, dies über Turingmaschinen zu tun. Wir sind dabei nur an (deterministischen) Turingmaschinen interessiert, die Wortfunktionen berechnen. Wie immer sei $\delta(s, a)$ undefiniert für alle Endzustände $s$ und alle Symbole $a$ aus dem Arbeitsalphabet, d.h. die Maschine kann bei Erreichen eines Endzustands nicht weiterrechnen. Zur Erinnerung: Bei einer Turingmaschine $M$ ist die berechnete Wortfunktion $f_M$ wie folgt festgelegt: $f_M(w) =$ undefiniert, falls $M$ bei Eingabe von $w$ nie anhält, und $f_M(w) = y$, falls $M$ bei Eingabe von $w$ nach endlich vielen Schritten in einer Konfiguration $u s_f v$ mit einem Endzustand $s_f$ und Wörtern $u, v$ aus dem Arbeitsalphabet anhält; dabei sei $y$ das längste Präfix von $v$ über dem Eingabealphabet. } \begin{frame} \begin{lemma}\label{h-Notation} Die Menge aller von Turingmaschinen berechneten Funktionen über einem gegebenen Alphabet $E$ ist abzählbar, es gibt zu jedem $E$ eine totale Funktion $h$ mit Definitionsbereich $\{0,1\}^*$, deren Bild alle(!) berechenbaren Funktionen umfasst. \end{lemma} \only{ Konstruiere dazu Liste aller Turing-berechenbaren Funktionen\pause Dazu: (beachte: viele Feinheiten der Konstuktion sind willkürlich!)\pause \begin{itemize} \item Beschränkung auf deterministische Turingmaschinen $TM=(S, E, A, \delta, s_0, \Box, F)$\pause \item Festes Alphabet $E$ mit $\{0, 1,\#\}\subseteq E$\pause \item $\delta(s, a)$ undefiniert für alle $a\in A$ und Endzustände $s\in F$\pause \item $\delta(s, a)$ definiert für alle $a\in A$ und Nicht-Endzustände $s\not\in F$\pause \item Falls bei Eingabe $w$ mit Konfiguration $u s_f v$ hält:\pause $$f_{TM}(w):=\textrm{ das längste Präfix }\in E^*\textrm{ von }v$$ \end{itemize} } \only
{ Wir werden nun zuerst derartige Turingmaschinen $TM = (S, E, A, \delta, s_0, \Box, F)$ durch Wörter beschreiben. Zuerst nummerieren wir die Zustände einer Turingmaschine durch: \[S= \{s_0, s_1, \ldots, s_n\}\] Dabei sei $s_0$ der Startzustand. Wir können au"serdem die Nummerierung so wählen, dass die Endzustände am Ende stehen, d.h. es gibt eine Zahl $e $ in $\{1, \ldots, n\}$ derart, dass \[F = \{s_{n - e+1}, \ldots, s_n\}\] die Menge der Endzustände ist. Ebenso nummerieren wir die Symbole im Arbeitsalphabet $A $ einer Turingmaschine durch, d.h. wir nehmen an, dass \[A= \{a_0, a_1, \ldots, a_k\}\] Dabei sollen die Symbole des Eingabealphabets $E$, das ja in $A$ enthalten ist, am Anfang stehen, d.h. \[E=\{a_0, a_1, \ldots, a_l\}\textrm{ für ein }l \leq k\] Einen \"Ubergang der Form \[\delta(s_i, a_j)\textrm{ enthält }(s_t, a_m, B)\] kann man nun durch ein Wort der Form \[\#\# bin(i) \# bin(j) \# bin(t) \# bin(m) \# bin(b)\] beschreiben. Dabei sei $b = 0$, wenn $B=L$, $b = 1$, wenn $B=N$ und $b = 2$, wenn $B=R$. Die gesamte Turingmaschine kann man beschreiben, indem man alle derartigen Wörter, die \"Ubergänge der Turingmaschine beschreiben, hintereinander schreibt, und davor noch das Wort \[ bin(n) \# bin(e) \# bin(k) \# bin(l) \# bin(d)\#\] schreibt, das die Zahl der Zustände, die Zahl der Endzustände, die Zahl der Symbole des Arbeitsalphabets, die Zahl der Symbole des Eingabealphabets und den Index $d$ des Blanksymbols beschreibt. Auf diese Weise können wir eine beliebige Turingmaschine durch ein endliches Wort über dem Alphabet $\{0, 1, \#\}$ beschreiben. Indem wir schlie"slich $0$ durch $00$, $1$ durch $01$ und $\#$ durch $11$ codieren, erhalten wir sogar eine Codierung aller Turingmaschinen durch Wörter über dem Alphabet $\{0, 1\}$. } \end{frame} \only{\begin{frame} O.B.d.A.:\pause \begin{itemize} \item $S= \{s_0, s_1, \ldots, s_n\}$ \pause mit Startzustand $s_0$\pause \item Endzustände am Listenende: $F = \{s_{n - e+1}, \ldots, s_n\}$ \pause mit $e =|F|$\pause \item $A= \{a_0, a_1, \ldots, a_k\}$\pause \item $E\subset A$ \pause mit $E=\{a_0, a_1, \ldots, a_{l-1}\}$ \pause für $l=|E|$\pause \item $\Box=a_d$ für ein $d$ \end{itemize} \pause \"Ubergänge der Form '$\delta(s_i, a_j)\textrm{ enthält }(s_t, a_m, B)$' beschreibbar durch \pause \[\Delta_{i,j}:=\#\# bin(i) \# bin(j) \# bin(t) \# bin(m) \# bin(b)\] \pause mit $b = 0$, wenn $B=L$, $b = 1$, wenn $B=N$ und $b = 2$, wenn $B=R$.\pause $\Rightarrow$ \pause $TM$ beschreibbar durch \pause $n$, $e$, $k$, $l$, $d$ und \pause Angabe der $\delta(s_i, a_j)$,\pause\\ d.h. als Wort über $\{0,1,\#\}$ in folgender Form:\pause \[ bin(n) \# bin(e) \# bin(k) \# bin(l) \# bin(d)\#\Delta_{0,0}...\Delta_{n-e,k}\] \pause Codiere z.B. $0\mapsto 00$, $1\mapsto01$ und $\#\mapsto11$ \pause\\ $\Rightarrow$ \emph{jede} Turingmaschine durch ein $w\in\{0, 1\}^*$ beschreibbar. \end{frame}} \only
{\begin{frame} Nicht alle Wörter über $\{0, 1\}$ sind Beschreibungen von deterministischen Turingmaschinen, die die oben genannte Zusatzbedingungen erfüllen. Sei Maschine $M^{ud}$, die nur \"Ubergänge $\delta(s_0,a) = (s_0, a, N)$ für $a\in A $ enthält und einen von $s_0$ verschiedenen Endzustand $s_f$ hat, also bei keiner Eingabe je anhält. Zu jedem Binärwort $w$ definieren wir eine deterministische Turingmaschine $M_w$, die eine Wortfunktion berechnet, indem wir setzen: $M_w := M$, falls $M $ eine deterministische Turingmaschine ist, die die oben genannten Zusatzbedingungen und falls $w $ die Turingmaschine $M $ in der oben erläuterten Weise beschreibt, und $M_w= M^{ud}$, andernfalls. Die von $M_w$ berechnete Wortfunktion sei mit $h_w$ bezeichnet. Wir können jetzt $w $ als Programm für die Funktion $h_w:E^* \Partial E^*$ auffassen. Die Abbildung, die einem Wort $w $ über dem Alphabet $\{0, 1\}$ die Funktion $h_w:E^* \Partial E^*$ zuordnet, kann als Programmiersprache aufgefasst werden. Diese Idee wollen wir allgemeiner formulieren. Wir wollen der Einfachheit halber nur Programmiersprachen betrachten, deren Programme Binärwörter sind. \end{frame}} \only{\begin{frame} Ziel: Aufzählung aller berechenbaren Wortfunktionen, dazu\pause \begin{itemize} \item Zu jedem $w\in\{0,1\}^*$ definiere $M_w$ durch \pause \[M_w := \left\{\begin{array}{ll} M,&\textrm{ falls }w\textrm{ eine Beschreibung der Maschine }M\textrm{ ist }. \pause\\ M^{ud},&\textrm{ sonst } \end{array}\right.\] \item \pause Dabei sei $M^{ud}$ beliebig gewählt, z.B.\pause $$M^{ud}:=(\{s_0,s_1\},E,E\cup\{\Box\},\delta,\Box,\{s_1\})$$ \pause mit $\delta(s_0,a) = (s_0, a, N)$ für $a\in A$ \pause (d.h. $M^{ud}$ hält nie an...)\pause \item $h_w$ sei die von $M_w$ berechnete Wortfunktion. \end{itemize} \pause $\Rightarrow$ $w$ ist 'Programm' für die Funktion $h_w:E^* \Partial E^*$\pause $\Longrightarrow$ Abbildung $w\mapsto h_w$ ist 'Programmiersprache' \end{frame}} \begin{frame} \begin{definition}\pause Sei $E $ ein Alphabet. \pause\\ Eine \Fb{Notation} für die berechenbaren Funktionen $g:E^* \Partial E^*$ \pause ist eine surjektive Funktion \pause \[h':\{0, 1\}^* \rightarrow \{\textrm{ berechenbare Wortfunktionen über }E^*\}\] \begin{itemize} \item \pause Jedem $w\in\{0, 1\}^*$ wird eine berechenbare Wortfunktion zuordnet.\pause \item Zu jeder berechenbaren Wortfunktion $g $ gibt es ein Wort $w\in\{0, 1\}^*$ derart, \pause dass $h'(w)$ gerade die Funktion $g$ ist. \end{itemize} \pause Wir schreiben oft auch $h'_w$ für die Funktion $h'(w)$. \end{definition} \end{frame} \begin{frame} \only
{ Wir möchten zwei Eigenschaften, die Notationen $h'$ haben können, festhalten:} \only{Mögliche Eigenschaften von Notationen:\pause} \begin{block}{utm-Eigenschaft} \pause Die Wortfunktion, die Wörter $w\#x$ für $w \in\{0, 1\}^*$ und $x\in E^*$ auf $h'_w(x)$ abbildet, \pause ist berechenbar.\pause \end{block} \begin{block}{smn-Eigenschaft} \pause Ist $g: E^* \Partial E^*$ eine berechenbare Wortfunktion, \pause so gibt es eine totale berechenbare Wortfunktion $r$ derart, dass für alle $x\in\{0, 1\}^*$ und alle $y\in E^*$ gilt: \pause \[g(x\#y) = h'_{r(x)}(y)\] \end{block} \end{frame} \begin{frame} \begin{theorem} \pause Die von uns oben definierte Funktion $h$, die jedes Wort $w $ aus $\{0, 1\}^*$ auf eine berechenbare Funktion $h_w:E^* \Partial E^*$ abbildet, ist eine Notation der berechenbaren Wortfunktionen.\pause $h$ hat zudem die utm-Eigenschaft und die smn-Eigenschaft. \end{theorem}\pause Beweis:\pause Nach Konstruktion ist $h$ Notation der berechenbaren Wortfunktionen:\pause \begin{itemize} \item $h_w$ ist berechenbare Funktion für jedes $w$.\pause \item Jede (normierte) Turingmaschine wird durch ein $w$ kodiert. \end{itemize} \only{ \pause Zur utm-Eigenschaft: \pause Bilde Turingmaschine $U$ wie folgt:\pause \begin{itemize} \item Bei Eingabe $w\#x$ bestimmt $U$ die von $w$ codierte Maschine $M$ \pause (d.h. direkt $M=M_w$ oder aber $M=M^{ud}$)\pause \item Danach simuliert $U$ die Maschine $M$ auf der Eingabe $x$ \end{itemize} \pause $f_U$ ist dann die für die utm-Eigenschaft notwendige Funktion!} \end{frame} \only
{\begin{frame} Zur utm-Eigenschaft: Aus einem Wort $w $ kann man das Verhalten der Turingmaschine $M_w$ ablesen. Daher kann man eine Turingmaschine bauen, die bei Eingabe eines Wortes $w\#x$ für $w $ aus $\{0, 1\}^*$ die Turingmaschine $M_w$ mit Eingabe $x $ simuliert. Eine derartige Turingmaschine berechnet gerade die gewünschte Funktion. Zur smn-Eigenschaft: Sei $g:E^* \Partial E^*$ eine berechenbare Wortfunktion. Dann gibt es eine Turingmaschine $M_g$, die $g$ berechnet. Wenn ein Wort $w\in\{0, 1\}^*$ gegeben ist, können wir daraus sicher eine Beschreibung $r(w)$ für eine Turingmaschine $M_{r(w)}$ berechnen, die bei Eingabe $x $ die Maschine $M_g$ angesetzt auf $w\#x$ simuliert. \end{frame}} \only{\begin{frame} Zur smn-Eigenschaft: \pause \begin{itemize} \item Sei $g:E^* \Partial E^*$ eine berechenbare Wortfunktion.\pause \item Sei $M_g$ Turingmaschine, die $g$ berechnet (fest gegeben!) \end{itemize} \pause Betrachte eine Turingmaschine $R$, die wie folgt arbeitet: \pause \begin{itemize} \item $R$ liest ihre Eingabe $x$ \pause und modifiziert dann (eine Codierung von) $M_g$ \pause zu (der Codierung eines) $M_g^x$ mit folgender Arbeitsweise:\pause \begin{quote} Bei einer Eingabe $y$ schreibt $M_g^x$ zunächst das Wort $x\#$ links vor das Wort $y$ \pause und arbeitet dann weiter wie $M_g$ \end{quote} \item \pause $x$ wird dabei in der Zustandsmenge von $M_g^x$ codiert\pause \item $R$ erzeugt dann als Ausgabe eine Codierung von $M_g^x$\pause \item $M_g$ wird in der Zustandsmenge von $R$ codiert \end{itemize} \pause $R$ erzeugt also aus einer Eingabe $x$ (die Codierung von) $M_g^x$ mit \pause$$h_{f_R(x)}(y)=f_{M_g^x}(y)=f_{M_g}(x\#y)=g(x\#y)$$ \pause $f_R$ ist also das in der smn-Eigenschaft geforderte (totale!) $r$. \end{frame}} \begin{frame} Anwendung der smn-Eigenschaft in JAVA:\pause Betrachte Funktion zu Addition zweier Zahlen in JAVA aus Kapitel \ref{Berechenbarkeitsbeispiele},\pause\\ wende smn-Eigenschaft für ersten Parameter $m$ an:\pause \texttt{\footnotesize\begin{tabular}{|@{}l@{}|}\hline class SMN \{\\ public static void main(String args[]) \{\\ System.out.println(\"{}{\bfseries import java.math.BigInteger;}\"{});\\ System.out.println(\"{}{\bfseries class Addition \{}\"{});\\ System.out.println(\"{}{\bfseries public static void main(String args[])\{}\"{});\\ \pause System.out.println(\"{}\Fb{\bfseries BigInteger m=new BigInteger($\backslash$''}\"{}\\ \pause ~~~~~~~~~~~~~~~~\Fb{+~ args[0] + \"{}{\bfseries $\backslash$'');}\"{}}~);\\ \pause System.out.println(\"{}{\bfseries BigInteger n=new BigInteger(\Fb{args[0]});}\"{});\\ \pause System.out.println(\"{}{\bfseries while(n.compareTo(BigInteger.ZERO)>0)\{}\"{});\\ System.out.println(\"{}{\bfseries n = n.subtract(BigInteger.ONE);}\"{});\\ System.out.println(\"{}{\bfseries m = m.add(BigInteger.ONE);}\"{});\\ System.out.println(\"{}{\bfseries \}}\"{});\\ System.out.println(\"{}{\bfseries System.out.println(m.toString());}\"{});\\ System.out.println(\"{}{\bfseries \}}\"{});\\ System.out.println(\"{}{\bfseries \}}\"{});\\ \} \}\\ \hline\end{tabular}} \end{frame} \only
{\begin{frame} Das Kürzel utm steht übrigens für \emph{Universelle Turing-Maschine}. Eine universelle Turingmaschine arbeitet wie ein ganz normaler Computer in der Praxis, der als Eingabe einerseits ein Programm (hier das Wort $w$) erhält, und andererseits den jeweiligen Eingabewert (hier das Wort $x$) für das Programm. Es scheint sehr natürlich zu sein, von einer Notation oder Programmiersprache zu erwarten, dass man aus einem Programm $w$, geschrieben in der Programmiersprache, und einem Eingabewert $x $ auch den Ausgabewert des Programms bei dieser Eingabe berechnen kann. Das hei"st, man sollte von Programmiersprachen sicherlich verlangen, dass sie die utm-Eigenschaft haben. Auch die smn-Eigenschaft ist natürlich. Sie besagt, dass man zu einer berechenbaren Funktion $g $ und einem Wort $x$ effektiv eine Programm $r(x)$ schreiben können sollte, das bei Eingabe eines weiteren Wortes $y$ gerade das Wort $g(x\#y)$ ausrechnet. Typische Anwendungen sehen oft so aus, dass man aus $x$ ein Programm für eine Maschine berechnen möchte, die bei Eingabe $y$ die Maschine $M_x$ in irgendeiner Form simulieren soll. Das Kürzel smn hat nur historische Gründe. Es diente als mnemonische Abkürzung für eine mehrstellige Funktion, die in der ursprünglichen Fassung der smn-Eigenschaft auftrat. \end{frame}} \only{\begin{frame} 'utm' steht für \Fb{Universelle Turing-Maschine}\pause \begin{itemize} \item Die Maschine $U$ kann jedes 'Turingprogramm' $w$ auf jeder Eingabe $x$ simulieren\pause \item Analogie zum realen Computer und realen Programmiersprachen: \pause Beliebige Programme können auf beliebigen Eingaben gestartet werden... \pause \item Jede 'gute' Programmiersprache sollte erlauben, Programme auf Eingaben anzuwenden... \end{itemize} \pause Zur smn-Eigenschaft:\pause \begin{itemize} \item $r$ erlaubt es, das Turingprogramme für $g$ zu spezialisieren\pause \item aus einer 'Eingabe' $x$ wird eine 'Konstante' $x$ im Programm $M_g^x$\pause \item Kürzel 'smn': nur historische Gründe... \end{itemize} \end{frame}} \only
{\begin{frame} Wir wollen nun Notationen vergleichen. Wir sagen, dass man eine Notation $h''$ in eine andere Notation $h'$ \emph{übersetzen} kann, wenn es eine berechenbare Wortfunktion $u: \{0, 1\}^* \rightarrow\{0, 1\}^*$ gibt, die jedes Programm $w $ in $\{0, 1\}^*$ bezüglich der ersten Notation auf ein Programm $u(w)$ in $\{0, 1\}^*$ bezüglich der zweiten Notation abbildet, das die gleiche Wortfunktion beschreibt, d.h. es soll gelten $h''_w(x) =h'_{u(w)} (x)$ für alle Programme $w$ aus $\{0, 1\}^*$ und alle Wörter $x$ aus $E^*$ . Dann nennen wir $u $ eine \emph{\"Ubersetzungsfunktion}. Wir nennen zwei Notationen \emph{äquivalent}, wenn man jede in die andere übersetzen kann. \end{frame}} \only{\begin{frame} \Fb{ Vergleichbarkeit von Notationen}:\pause \begin{itemize} \item eine Notation $h''$ ist in eine Notation $h'$ \Fb{übersetzbar}, \pause\\ wenn es eine totale(!) berechenbare Wortfunktion $$u: \{0, 1\}^* \rightarrow\{0, 1\}^*$$ gibt mit \pause $$h''_w(x) =h'_{u(w)} (x)$$ \pause für alle $w\in\{0, 1\}^*$ und $x\in E^*$, \pause d.h. $h''_w =h'_{u(w)}$\pause \item Jedes 'Programm' $w$ der 'Programmiersprache' $h''$ kann also dann automatisch in ein 'Programm' der 'Sprache' $h'$ übersetzt werden.\pause \item $u $ heißt \Fb{\"Ubersetzungsfunktion}. \end{itemize} \pause Notationen $h'$ und $h''$ heißen \Fb{äquivalent}, \pause wenn man jede in die andere übersetzen kann. \end{frame}} \begin{frame} \begin{theorem}[\"Aquivalenzsatz von Rogers] \pause Eine Notation für die berechenbaren Wortfunktionen ist genau dann zu der von uns definierten Notation $h $ äquivalent, \pause wenn sie die utm-Eigenschaft und die smn-Eigenschaft hat. \end{theorem} \pause Beweis:\pause \only
{ Sei $h$ die von uns oben definierte Notation und $h'$ irgendeine weitere Notation für die berechenbaren Wortfunktionen. Wir nehmen zuerst an, dass die beiden Notationen äquivalent sind. Sei $u $ eine \"Ubersetzungsfunktion von $h $ nach $h' $ und $u' $ eine \"Ubersetzungsfunktion von $h'$ nach $h$. Da unsere Notation $h $ die utm-Eigenschaft hat und die Komposition von berechenbaren Funktionen wieder berechenbar ist, ist auch die Funktion berechenbar, die $w\#x $ mit $w $ aus $\{0, 1\}*$ auf $h_{u'(w)} (x) = h'_w(x)$ abbildet. Das ist gerade die utm-Eigenschaft für $h'$.} \only{ \begin{itemize} \item Sei $h$ wie oben\pause \item Sei $h'$ weitere Notation für berechenbaren Wortfunktionen. \end{itemize} \pause '$\Rightarrow$': \pause $h$ und $h'$ seien äquivalent, \pause mit $h_w=h'_{u(w)}$ und $h'_w=h_{u'(w)}$ \pause (a) utm-Eigenschaft für $h$: \pause$f_h$ mit $f_h(w\#x):=h_w(x)$ ist berechenbar\pause Definiere $f'$ durch $f'(w\#x):=f_h(u'(w)\#x)$\pause Dann $f'$ berechenbar \pause und \[h'_w(x)=\pause h_{u'(w)} (x)= \pause f_h(u'(w)\#x)=\pause f'(w\#x)\] \pause d.h. $f'$ zeigt utm-Eigenschaft für $h'$ } \end{frame} \only
{\begin{frame} Sei $g:E^*\Partial E^*$ irgendeine berechenbare Wortfunktion. Da unsere Notation $h $ die smn-Eigenschaft hat, gibt es eine berechenbare totale Funktion $r $ derart, dass für alle $x$ aus $\{0, 1\}^*$ und alle $y$ aus $E^*$ gilt: $g(x\#y) = h_{r(x)}(y)$. Wegen $h_{r(x)}(y) = h'(u(r(x)) (y)$ und weil die Funktion $ur$ total und als Komposition berechenbarer Funktionen selbst wieder berechenbar ist, hat auch die Notation $h'$ die smn-Eigenschaft.$ $ Nun nehmen wir an, dass auch die Notation $h' $ die utm-Eigenschaft und die smn-Eigenschaft hat. Wir wollen zeigen, dass $h' $ zu $h $ äquivalent ist: Wendet man die smn-Eigenschaft für $h' $ auf die laut utm-Eigenschaft für $h $ berechenbare Wortfunktion $w\# x\rightarrow h_w(x)$ an, so erhält man eine \"Ubersetzungsfunktion $r $ von $h$ nach $h'. $ Eine \"Ubersetzungsfunktion in der umgekehrten Richtung erhält man, indem man die smn-Eigenschaft für $h $ auf die laut utm-Eigenschaft für $h' $ berechenbare Funktion $w\#x\Partial h'_w(x)$ anwendet. \end{frame}} \only{\begin{frame} (b) Sei $g:E^*\Partial E^*$ irgendeine berechenbare Wortfunktion. \pause smn-Eigenschaft für $h$: \pause $r$ mit $h_{r(x)}(y):=g(x\#y)$ ist berechenbar\pause Dann ist $u\circ r$ berechenbar \pause (und total) \pause mit \[g(x\#y)=\pause h_{r(x)}(y)=\pause h'_{u\circ r(x)}(y)\] \pause D.h. $h'$ hat auch die smn-Eigenschaft.\pause '$\Leftarrow$': \pause $h'$ besitze ebenfalls die utm- und die smn-Eigenschaft:\pause utm-Eigenschaft für $h$: \pause $f_h$ mit $f_h(w\#x)=h_w(x)$ berechenbar\pause Wende smn-Eigenschaft für $h'$ auf $f_h$ an, \pause mit entsprechendem $r'$:\pause \[h_w(x)=\pause f_h(w\#x)=\pause h'_{r'(w)}(x)\] \pause Damit Übersetzung von $h$ nach $h'$ mit $r'$\pause Analog: utm-E.\ für $h'$ \pause und smn-E.\ für $h$ \pause $\Rightarrow$ $h'$ in $h$ übersetzbar.\pause Damit: $h$ und $h'$ äquivalent! \end{frame}} \begin{frame} \only
{ \"Aquivalente Notationen können als gleichwertig betrachtet werden, da man sie effektiv ineinander übersetzen kann. Während die utm-Eigenschaft sehr anschaulich ist und sicher eine Minimalforderung an jede Notation für berechenbare Funktionen, mag die smn-Eigenschaft auf den ersten Blick etwas unanschaulich sein. Aber man kann zeigen, dass man sie in dem \"Aquivalenzsatz von Rogers durch eine sehr anschauliche Eigenschaft ersetzen kann. } \begin{theorem} \pause \label{eff_Komp} Eine Notation $h'$ für die berechenbaren Wortfunktionen ist genau dann zu der von uns definierten Notation $h$ äquivalent, \pause wenn sie die utm-Eigenschaft und die folgende Eigenschaft hat:\pause \begin{quote}{(effektive Komposition)} \pause Es gibt eine totale berechenbare Wortfunktion $r:\{0, 1\}^* \#\{0, 1\}^* \rightarrow \{0, 1\}^*$ derart\pause,\\ dass für alle $v, w$ aus $\{0, 1\}^*$ und alle $x $ aus $E^*$ gilt: \pause $$h'_v(h'_w(x)) = h'_{r(v\#w)}(x)$$ \end{quote} \pause $r$ bestimmt also aus zwei 'Programmen' $v$, $w$ ein 'Programm' $r(v\#w)$ für die Komposition der Funktionen $h'_v$ und $h'_w$. \end{theorem} \only
{ Wir lassen den Beweis weg. } \only{\pause(Ohne Beweis.)\pause \begin{itemize} \item Alle 'vernünftigen' Notationen der berechenbaren Wortfunktionen sind äquivalent \pause (mit 'vernünftig' = \pause 'utm+smn' \pause = 'utm+effKomp' )\pause \item Jede zu $h$ äquivalente Notation heißt \Fb{Standardnotation} \end{itemize} } \end{frame} \only
{\begin{frame} Die effektive Kompositionseigenschaft ist sicherlich auch eine Minimalforderung an eine Notation für berechenbare Funktionen. Satz \ref{eff_Komp} zeigt, dass jede Notation, die diese beiden Minimalforderungen erfüllt, bereits zu der von uns oben explizit definierten Notation äquivalent ist. Die letzten drei Sätze zeigen also zweierlei. Einerseits gibt es eine Notation für die berechenbaren Wortfunktionen, die die utm-Eigenschaft, die smn-Eigenschaft und die effektive Kompositionseigenschaft erfüllt. Andererseits ist jede Notation, die die utm-Eigenschaft und die smn-Eigenschaft (bzw. die effektive Kompositionseigenschaft) erfüllt, bereits zu dieser Notation äquivalent. Es gibt also bis auf \"Aquivalenz nur eine \glqq vernünftige \grqq Notation für die berechenbaren Wortfunktionen. Man bezeichnet diejenigen Notationen der berechenbaren Wortfunktionen, die zu der von uns definierten Notation $h$ äquivalent sind, auch als \emph{Standardnotationen}. Man könnte Notationen auch als Programmiersprachen bezeichnen. \end{frame}}