\section{Berechenbarkeit mittels Turingmaschinen} \inhalta{1-7} \only
{\begin{frame} Turingmaschinen sind evtl.\ schon bereits als Akzeptoren für die Sprachen der Chomsky Typ-0-Klasse bekannt. \[\includegraphics[scale=.5]{./grafik/turing.png}\] \end{frame} }%article \only{\begin{frame} Bekannt(?): Turingmaschinen als Akzeptoren für Typ-0-Sprachen\pause \[\includegraphics[scale=.5]{./grafik/turing.png}\] Jetzt: Turingmaschinen als allgemeines Maschinenmodell zur Berechnung von Funktionen \pause(Alan Turing, 1930): \[f: E^*\Partial E^* \pause\textrm{ bzw. }f: \nz^k\Partial \nz\] \end{frame} }%presentation % \begin{frame} % Wir wollen ein auf Alan Turing zur\"uckgehendes Maschinenmodell vorstellen. % Diese sogenannte Turingmaschine spielt auch in der Berechenbarkeitstheorie eine sehr wichtige Rolle. % % Anschaulich gesehen besteht die Turingmaschine aus einem unendlichen Band % (in manchen Versionen ist auch nur von einem einseitig unendlichen Band die % Rede mit einem Stoppzeichen auf einer Seite). % Jedes Feld kann ein einzelnes Zeichen des Arbeitsalphabets enthalten. % Felder, die noch nie besucht oder ver\"andert (beschrieben) wurden, enthalten ein Blankzeichen $\Box$. % % Der Kopf ist ein Schreib-Lesekopf und bearbeitet Zeichen, die sich direkt unter ihm befinden. % Zudem kann er in einem Rechenschritt um eine Position nach links oder rechts gehen. % \end{frame} \begin{frame} \begin{definition}[Turingmaschine] Eine (nichtdeterministische) Turingmaschine (TM) ist durch ein 7-Tupel beschrieben: $$TM = ( S, E, A, \delta, s_0, \Box, F)$$ Dabei bedeuten \pause \begin{itemize} \item $S = \{ s_0, s_1, ..., s_n\}$ die Menge der Zustände,\pause \item $E = \{ e_1, e_2, ..., e_r\}$ das endliche Eingabealphabet,\pause \item $A = \{ a_0, a_1, ..., a_m\}$ das endliche Arbeitsalphabet (auch Bandalphabet genannt), \pause es sei dabei $E\subset A$,\pause \item $s_0$ der Startzustand,\pause \item $a_0 =\Box$ das Blank, \pause das zwar dem Arbeitsalphabet, aber nicht dem Eingabealphabet angehört,\pause \item $F \subseteq S$ die Menge der Endzustände \end{itemize} \end{definition} \end{frame}\begin{frame} \begin{cont}{} \begin{itemize} \item $\delta$ sei die (totale) {\em \"Uberführungsfunktion} \pause\\ mit (im deterministischen Fall) $$\delta:(S\setminus F)\times A\rightarrow S\times A \times \{ L, R, N\}$$ \pause bzw.\ (im nichtdeterministischen Fall) $$\delta: (S\setminus F)\times A\rightarrow {\mathcal P}( S\times A \times \{ L, R, N\})$$ \pause Hier bedeutet: \pause $L $= links, \pause $R$ = rechts, \pause $N$= neutral (nicht bewegen). \end{itemize} \end{cont} \end{frame} \begin{frame} Die \"Uberführungsfunktion wird folgenderma"sen interpretiert:\pause Die Definition $$\delta(s, a) = (s', b, x)$$\pause bzw.\ im nichtdet.\ Fall $$(s', b, x)\in \delta(s, a)$$ \pause mit $x\in\{ L, R, N\}$, beschreibt folgendes Verhalten( bzw.\ folgendes mögliche Verhalten im nichtdet.\ Fall):\pause \begin{quote} Wenn sich der Automat im Zustand $s$ befindet und \pause unter dem Kopf das Zeichen $a$ steht, so \pause schreibt der Automat $b$ und \pause geht ein Feld nach rechts ($R$), bzw. links ($L$), bzw.\ bewegt sich nicht ($N$) und \pause geht in den Zustand $s'$ über. \end{quote} \only
{Jede Turingmaschine kann auch als Tabelle geschrieben werden in Form einer Matrix mit den Zuständen als Zeilenmarkierung und den Zeichen aus dem Bandalphabet als Spaltenindizes. In jedem Kästchen steht dann ein Tripel bestehend aus neuem Zustand, geschriebenem Zeichen und Positionszeichen. Im Fall des nichtdeterministischen Automaten enthalten die Kästchen Mengeneinträge. } \only{\pause Darstellung von $\delta$: als Tabelle, evtl. mit Mengeneinträgen...} \end{frame} \begin{frame} \begin{definition}[Konfiguration] Eine Konfiguration einer Turingmaschine $TM = ( S, E, A, \delta, s_0, \Box, F)$ \pause ist ein Tripel $(u,s,v)$ aus $A^*\times S \times A^+$:\pause \begin{itemize} \item \only
{Das Wort $uv$ ist die aktuelle Bandinschrift (im schon beschriebenen oder besuchten Teil des Bandes)} \only{$uv$ ist aktuelle Bandinschrift,\pause} \item $s$ ist der aktuelle Zustand,\pause \item \only
{Der Schreib-Lesekopf steht auf dem ersten Zeichen von $v\Box$, weshalb $v\neq\varepsilon$ gelten muss.} \only{Schreib-Lesekopf über erstem Zeichen von $v$\pause, daher $v\neq\varepsilon$,\pause} \item \only
{Beim Start der Maschine enthält das Band ein Wort $v=w\Box$, wobei $w$ die Eingabe sei. Damit ist $v$ aus $E^* \circ \{\Box\}$, ferner sei $s = s_0$ und $u$ sei leer. Bei Eingabe $w$ startet die Maschine also mit der Konfiguration $(\varepsilon,s_0,w\Box)$.} \only{Start der Maschine: \pause\\ Startkonfiguration $(\varepsilon,s_0,w\Box)$ bei Eingabe von $w$.\pause } \end{itemize} \only
{O.B.d.A. gilt $S\cap A=\emptyset$, daher schreiben wir eine Konfiguration $(u,s,v)$ meist abgekürzt als $usv$ auf.} \only{O.B.d.A. $S\cap A=\emptyset$\pause, daher Schreibweise $usv$ statt $(u,s,v)$} \end{definition} \end{frame} \begin{frame} \begin{definition}[\"Ubergangsrelation $\vdash$] Zu einer (nicht)deterministischen Turingmaschine \[TM = ( S, E, A, \delta, s_0, \Box, F)\] wird die \"Ubergangsrelation $\vdash_{TM} $ (oder kurz $\vdash $) aus $(A^*\times S \times A^+)^2$ folgenderma"sen definiert: \begin{itemize} \item \pause $$ a_1... a_m s b_1... b_n \vdash \pause[3] a_1... a_m s' c b_2... b_n$$ \pause[2]falls: $( s', c, N)\in \delta( s,b_1), m \geq 0, n \geq 1$ \pause[3] \item \pause $$ a_1... a_m s b_1... b_n \vdash\pause[5] a_1... a_m c s' b_2... b_n $$ \pause[4]falls: $(s',c,R)\in \delta( s, b_1), m\geq 0, n \geq 2$\pause[5] \item \pause $$ a_1... a_m s b_1... b_n \vdash\pause[7] a_1... a_{m-1} s' a_mcb_2... b_n$$ \pause[6]falls: $(s', c, L)\in \delta( s, b_1), m\geq 1, n\geq 1$ \end{itemize} \end{definition} \end{frame} \begin{frame} \begin{cont}{} \only
{ Wir schreiben noch zwei Sonderfälle auf: } \begin{itemize} \item $$a_1... a_m s b_1 \vdash \pause[2]a_1... a_m c s' \Box $$ \pause[1]falls $( s', c, R)\in \delta( s, b_1) $ , $ m \geq 0, n = 1$ \pause[2] \item \pause $$s b_1... b_n \vdash \pause[4]s' \Box c b_2... b_n$$ \pause[3]falls $( s', c, L)\in \delta( s, b_1)$ , $m = 0, n \geq 1$ \pause[4] \end{itemize} \pause Bei Überschreiten der Grenzen der Bandinschrift werden also Blanks an die Teilwörter $v$ bzw.\ $u$ angefügt.\vsp \pause Dabei bedeutet das Symbol $\vdash $, dass die Konfiguration links in die jeweilige Konfiguration rechts übergehen kann (bzw. muss, wenn es genau eine Möglichkeit gibt).\vsp \pause Weiterhin sei $\vdash^*$ wieder die reflexiv-transitive Hülle der Relation $\vdash$. \end{cont} \end{frame} \begin{frame} \begin{example}[Inkrementieren einer Binärzahl]\label{Zaehlen mit TM} \only
{ Wir wollen eine Turingmaschine angeben, die die Bandinschrift als eine Binärzahl interpretiert und $1$ hinzuaddiert. Als Beispiel wählen wir die Zahl $1010$ und erhalten $1011$. Interessant wird die Frage, wie die Maschine mit der Zahl $111$ oder $\Box$ umgeht, da hier die Stellenzahl wächst.} \only{\pause Turingmaschine} $$TM= (\{ s_0, s_1, s_2, s_f\} , \{0, 1\} , \{0, 1, \Box\}, \delta, s_0, \Box, \{s_f\})$$ mit\pause \[\begin{array}{|c|c|c|c|} \hline \delta( s, a)& 0&1& \Box \\ \hline s_0&( s_0, 0, R) &( s_0, 1, R) &( s_1, \Box, L) \\ \hline s_1&( s_2, 1, L) &( s_1, 0, L) &( s_f, 1, N) \\ \hline s_2&( s_2, 0, L) &( s_2, 1, L) &( s_f, \Box, R) \\ \hline s_f&- &- &- \\ \hline \end{array}\] \pause Beispiel: \[\begin{array}{rl} s_0111 \Box &\pause ~\vdash~ 1s_011 \Box \pause ~\vdash~ 11s_01 \Box \pause ~\vdash ~ 111s_0\Box \\ &\pause ~\vdash~ 11s_11\Box \pause ~\vdash~ 1s_110\Box \pause ~\vdash~ s_1100\Box \pause ~\vdash~ s_1\Box000\Box \\&\pause ~\vdash~ s_f1000\Box \end{array}\] \end{example} \end{frame} \only
{\begin{frame} \begin{cont}{} Man überlegt sich, dass die Maschine zunächst mittels der Angaben der Zeile 1 solange nach rechts läuft, bis sie das Ende der Zahl (niederwertigste Ziffer) erreicht hat. Ein weiterer Schritt führt auf ein Blank (wenn zu Beginn nichts auf dem Band steht, steht der Lese-Schreibkopf schon auf einem Blank). Dann erfolgt wieder ein Schritt nach links und \"Ubergang nach $s_1$. Nunmehr ist die Maschine in Arbeitsposition. Trifft sie auf eine Null, so invertiert sie sie (Addition von $1$) und geht nach $s_2$. Trifft sie vorher auf Einsen, müssen diese invertiert werden. Ein Spezialfall tritt auf, wenn es keine $0$ in der Zahldarstellung gibt. Dann wächst die Stellenzahl um $1$ und die Maschine schreibt eine $1$ anstelle des ersten linken Blanks. Dies ist die führende Stelle, die Maschine geht in den Endzustand über und der Kopf bleibt hier stehen. Die vorletzte Zeile der Tabelle betrifft den Fall, dass die Zahldarstellung eine Null enthält. Hier läuft die Maschine noch schrittweise im Zustand $s_2$ bis ans linke Ende der Zahl. Trifft sie auf ein Blank, kehrt sie um und geht mit dem Schreibkopf über der führenden Stelle in den Endzustand über. \end{cont} \end{frame}} \begin{frame} \begin{definition}[Initialkonfiguration, Finalkonfiguration, akzeptierte Sprache] \begin{itemize} \item \pause Initialkonfiguration beim Start der Turingmaschine mit Eingabe $w\in E^*$ \pause ist $s_0w\Box$.\pause \item Finalkonfigurationen sind alle Konfigurationen $us_fv$ mit $s_f\in F $. \pause Hier kann die Berechnung nicht mehr fortgesetzt werden.\pause \item Weiter ist $$L(TM) := \{w\in E^* \mid s_0w\Box \vdash^* us_fv,\pause s_f\in F, \pause u, v\in A^*\}$$ \pause die von der Turingmaschine akzeptierte Sprache $L$. \end{itemize} \end{definition} \only
{ Turingmaschinen lassen sich nutzen, um sowohl die Typ-0-Sprachen als auch die kontextsensitiven Sprachen charakterisieren (letzte über Beschränkung der Größe des Arbeitsbandes). Außerdem ist einfach zu erkennen, das sie mächtiger als endliche Automaten und Kellerautomaten sind. } \end{frame} \only
{\begin{frame} Ein endlicher Automat ist ein Spezialfall einer Turingmaschine, der Schreib-Lesekopf nutzt ausschließlich die Lese-Funktion und der Kopf bewegt sich nur nach rechts. Formal bedeutet das, dass die Übergangsfunktion die Form $\delta(s,a)=(s',a,R)$ für alle $a\in E$ hat. Die Simulation von Kellerautomaten ist nach folgender Idee möglich. Das Schreib-Leseband der Turingmaschine wird ``zweigeteilt'': Rechtsseitig steht das Eingabewort. Die Maschine trägt auf dem ersten freien Platz links ein Zeichen ein, das den Boden des Kellers markiert und simuliert in späteren Schritten den Kellerspeicher. Dabei müssen die Übergänge unter der Übergangsfunktion des Kellerautomaten, die ja mehrere Zeichen an die Kellerspitze schreiben können, durch mehrere Schritte der Turingmaschine simuliert werden. Diese kann sich auch merken, an welcher Stelle sie zuletzt die Eingabe gelesen hat, indem sie die schon verarbeiteten Zeichen durch ein Zeichen aus dem Arbeitsalphabet ersetzt. Das oberste Kellersymbol ist leicht zu finden, da links davon ein Blank steht. Ist der Keller leer, so geht die Turingmaschine in einen Endzustand über. Damit ist gezeigt, das die Turingmaschine mindestens so leistungsfähig ist wie die bisherigen Automaten. Wir wollen nun zeigen, dass man mittels einer Turingmaschine auch die Sprache $L= \{ a^nb^nc^n \mid n >0\}$ erkennt. \end{frame}} \only{\begin{frame} Simulation endlicher Automat durch Turingmaschine einfach: \pause \begin{itemize} \item Schreib-Lesekopf nutzt ausschlie"slich lesende Funktion\pause \item Lesekopf zeichenweise lesend nach rechts\pause \item Zustandsübergänge des endlichen Automaten werden übernommen\pause \item Akzeptieren bei Erreichen von $\Box$ (d.h. Ende der Eingabe) im 'Automaten-Endzustand' \end{itemize}\pause Simulation Kellerautomat durch Turingmaschine z.B. wie folgt:\pause \begin{itemize} \item Turing-Band zweigeteilt: \pause Rechts Eingabewort, links Keller\pause \item Nach Start sofort Markierung für 'Boden' des Kellers\pause \item \"Ubergangsfunktion des NKA durch mehrere Schritte der TM\pause \item Gelesene Zeichen der Eingabe mit Spezialzeichen markieren\pause \item Bestimmung des Überganges im NKA \pause durch Inspektion der noch nicht markierten Eingabe und des simulierten Kellers \pause \item Spitze des Kellers leicht zu finden, da links davon ein Blank steht. \end{itemize} \pause $\Longrightarrow$ Turingmaschinen mindestens so mächtig wie NKA \end{frame}} \begin{frame} \begin{example}[Turingmaschine zu $L = \{a^nb^nc^n \mid n >0\}$] \only
{ Wir wollen die Grundidee der Konstruktion nach Sander, Stucky und Herschel S. 194f. erläutern.} \only{\pause (vgl. Sander, Stucky und Herschel S. 194f.)\pause } Dazu definieren wir $TM := ( S, E, A, \delta, s_0, \Box, F)$ wie folgt \pause \GLA S&=&\{ s_0, s_1, s_2, s_3, s_4, s_f\} \\\pause A&\pause=&\pause\{ a, b, c, 0, 1, 2, \Box\} \\ \pause F&\pause=&\pause\{s_f\} \GLE \only
{Die \"Ubergangsfunktion definieren wir später in einer Tabelle.} \only
{ Die Maschine steht über dem ersten Zeichen des Wortes. Sodann ersetzt sie das am weitesten links stehende $a$ durch $0$ und geht in den Folgezustand über. Dasselbe geschieht mit dem am weitesten links stehenden $b$ (wird ersetzt durch $1$) bzw. $c$ (wird ersetzt durch $2$). Dann beginnt durch Zurückspringen in den Ausgangszustand die Suche von neuem. Wird kein $a$ mehr gefunden, darf auch kein $b$ oder $c$ mehr auftreten; ist noch ein $a$ vorhanden, muss das gleiche auch für $b$ und $c$ gelten. \ Interessant ist der Zustand $s_3$. Hier läuft der Automat zurück bis zur ersten Null von rechts und geht dann einen Schritt nach rechts. Kommen keine $b$ und $c$ mehr vor, geht der Kopf bis zum rechten Rand und beim ersten Blank in den Endzustand. } \only{\pause Idee der Arbeitsweise:\pause \begin{itemize} \item Ersetze jeweils erstes $a$ durch $0$\pause , $b$ durch $1$ \pause und $c$ durch $2$\pause \item Achte dabei auf korrekte Reihenfolge \pause \item Teste am Ende, ob alle $a$, $b$, $c$ ersetzt wurden \end{itemize} \pause d.h. $$s_0a^nb^nc^n\Box\pause \vdash^*\pause 0^ks_0a^m1^kb^m2^kc^m\Box\pause \vdash^*0^ns_01^n2^n\Box\pause \vdash^*0^n1^n2^ns_f\Box$$ } \end{example} \end{frame} \begin{frame} \begin{cont}{} {\small$$\begin{array}{@{}|c|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}c@{}|@{}} \hline & a & b & c & 0 & 1 & 2 & \Box \\ \hline s_0 & (s_1, 0,R) & & & & \pause[8] (s_4, 1,R)\pause[1] & & \\ \hline s_1 & \pause[2] (s_1,a,R) \pause[1] & \pause[3] (s_2, 1,R) \pause[1] & & & \pause[2] (s_1, 1, R) \pause[1] & & \\ \hline s_2 & & \pause[4] (s_2, b, R)\pause[1] & \pause[5](s_3, 2,L) \pause[1] & & & \pause[4](s_2, 2,R) \pause[1] & \\ \hline s_3 & \pause[6]( s_3,a,L) \pause[1] & \pause[6]( s_3,b,L) \pause[1] & & \pause[7]( s_0, 0, R)\pause[1] & \pause[6]( s_3, 1, L)\pause[1] & \pause[6](s_3, 2,L)\pause[1] & \\ \hline s_4 & & & & & \pause[9] (s_4, 1,R) \pause[1] & \pause[9] (s_4, 2,R) \pause[1] & \pause[10] (s_f, \Box,N) \pause[1]\\ \hline s_f & & & & & & & \\ \hline \end{array} $$} \pause[11] Ist die \"Ubergangsfunktion nicht definiert, bleibt der Automat stehen. \end{cont} \end{frame} \only
{\begin{frame} Als Beispiel soll das Wort $abcc$ geteset werden: $s_0 abcc \vdash 0 s_1 bcc \vdash 01 s_2 cc \vdash 0 s_312 c \vdash s_3012 c \vdash 0 s_012 c \vdash 01 s_42 c \vdash 012 s_4 c$ halt Also wird $abcc$ nicht akzeptiert). Wäre das letzte $c$ nicht vorgekommen, wäre der Kopf auf dem Blank in den Endzustand übergegangen. Das Wort $abc$ wäre daher akzeptiert worden. \end{frame}} \only
{\begin{frame} Jetzt wollen wir Turingmaschinen auch zur Berechnung von Funktionen $f: E^*\rightarrow E^*$ und von Funktionen $f: \nz^k\rightarrow \nz$ einsetzen. Für die Notation der Zahleneingaben bieten sich verschiedene Möglichkeiten an. Naheliegend sind natürlich die dezimale oder auch die binäre Notation $bin(n)$. Eine andere Möglichkeit besteht darin, die Variable durch die unär zu beschreiben. Hier schreibt man für $n$ z.B. dann $n$-mal ein Zeichen $|$. Au"serdem müssen wir bei der Eingabe eines Vektors zwischen den einzelnen Komponenten ein Trennsymbol haben, z.B. ein Blank. Der Kopf steht wiederum ganz links über dem ersten Zeichen. Nach Ausführung der Berechnung enthält das Band den Ergebniswert und der Kopf steht wiederum über dem ersten Zeichen. \end{frame}} \only{\begin{frame} Jetzt: Turingmaschinen als allgemeines Maschinenmodell zur Berechnung von Funktionen: \pause \[f: E^*\Partial E^* \pause\textrm{ bzw. }f: \nz^k\Partial \nz\] \pause Für Zahlenfunktionen notwendig: Notation der Zahlen! \pause \begin{itemize} \item Dezimalnotation $dez(n)$, z.B. $dex(12^2)=\texttt{144}$\\ (mit $\{\texttt{0,1,2,3,4,5,6,7,8,9,}\}\subseteq E$), \pause \item Binärnotation $bin(n)$, z.B. $bin(13)=\texttt{1101}$ und $bin(0)=\texttt{0}$\\ (mit $\{0,1\}\subseteq E$) \pause oder \item Unärnotation: $n$ durch $n$ Zeichen, z.B. $13$ durch $\texttt{|\!|\!|\!|\!|\!|\!|\!|\!|\!|\!|\!|\!|}$\pause \item Eingabe von Vektoren: mit Trennsymbol (z.B. Blank oder $\#$) zwischen den Zahlen\pause \item zu Beginn: Lese-Kopf steht über dem ersten Eingabe-Zeichen (von links) \pause \item am Ende: Ausgabe steht auf dem Band, \pause Kopf steht links über dem ersten Zeichen \end{itemize} \end{frame}}%presentation \begin{frame} \begin{definition} Eine Funktion $f:E^* \Partial E^*$ hei"st Turing-berechenbar, \pause falls es eine deterministische Turingmaschine $TM$ gibt derart, \pause dass für $x,y\in E^*$ genau dann $f(x) = y$ gilt, wenn es einen Endzustand $s'\in F$ und Worte $u,v$ gibt mit $$s_0x~~~~\vdash^*_{\mathnormal{TM}}~~~~ u s' v$$ und $y$ das längste Präfix von $v$ über $E$ ist.\\~ \pause Eine Funktion $f:\nz^k \Partial \nz$ hei"st Turing-berechenbar, \pause falls es eine deterministische Turingmaschine $TM$ gibt derart, \pause dass für $n_1,..., n_k,m$ aus $\nz$ genau dann $f(n_1,..., n_k) = m$ gilt, wenn es einen Endzustand $s'\in F$ und Worte $u,v$ gibt mit $$s_0 bin(n_1)\Box bin(n_2)\Box...\Box bin(n_k)\Box~~~~\vdash^*_{\mathnormal{TM}}~~~~ u s' v$$ und $bin(m)$ das längste Präfix von $v$ über $\{0,1\}$ ist. Dabei sei $bin(n)$ die Binärdarstellung von $n$. \end{definition} \end{frame} \begin{frame} \begin{example} a) Wir haben bereits in Beispiel \ref{Zaehlen mit TM} gesehen, dass die folgende Funktion $f$ (bezüglich der Binärdarstellung) berechenbar ist: $$ f(n) = S(n) = n+ 1$$ \pause b) Die nirgends definierte Funktion $f: \nz^k\Partial \nz$ ist ebenfalls berechenbar. \only
{Sie wird zum Beispiel von einer Turingmaschine mit einem Startzustand $s_0$, einem davon verschiedenen Endzustand $s_1$ und den \"Ubergängen $\delta(s_0, a) = (s_0, a, N)$ berechnet.} \only{ \pause Passende Turingmaschine: \pause \\ --- Startzustand $s_0$, \pause \\--- Endzustand $s_1\neq s_0$, \pause\\ --- \"Ubergänge $\delta(s_0, a) = (s_0, a, N)$ für alle $a\in A$ } \end{example} \end{frame} \only
{\begin{frame} \begin{example} Wir hatten festgestellt, dass die Typ-0-Sprachen genau diejenigen Sprachen sind, die von nichtdeterministischen Turingmaschinen erkannt werden. Au"serdem hatten wir bemerkt, dass man die nichtdeterministischen Turingmaschinen durch deterministische Turingmaschinen simulieren kann. Also ist eine Sprache genau dann vom Typ 0, wenn es eine deterministische Turingmaschine gibt, die sie erkennt. Ein Wort $x $ gehört genau dann zu der von einer Turingmaschine erkannten Sprache, wenn man von der Anfangskonfiguration $s_0x$ aus eine Konfiguration der Form $us_fv$ mit beliebigen Wörtern und einem Endzustand $s_f $ erreichen kann. Da die Maschine ein Eingabewort also akzeptiert, sobald sie in einen Endzustand gelangt, ist das Verhalten einer Maschine nach Erreichen eines Endzustandes für das Akzeptieren oder Nicht-Akzeptieren also ohne Belang. Daher hatten wir Turingmaschinen so definiert, dass sie nach Erreichen eines Endzustandes nicht weiterrechnen (können). Wir können die Maschine auch zum Beispiel so modifizieren, dass sie bei Erreichen eines Endzustandes erst zwei Blanks schreibt und den Kopf auf das rechte dieser Blanks setzt, d.h. sie hält mit $...\Box s_f\Box ...$ (wenn sie anhält) Damit haben wir gezeigt, dass eine Sprache $L $ genau dann vom Typ 0 ist, wenn die Funktion $g:E^*\rightarrow E^*$ mit $g(x) = \varepsilon$ für $x$ aus $L$ und $g(x)$ undefiniert für alle anderen Wörter $x$, berechenbar ist. \end{example} \end{frame}} \only{\begin{frame} \begin{example} \begin{itemize} \item Typ-0-Sprachen = Sprachen, die von n.det. TM erkannt werden.\pause \item n.det. TM durch det.\ TM simulierbar \pause \item d.h. $L$ ist vom Typ 0, wenn es eine det.\ TM gibt mit $L=L(TM)$ \end{itemize} \pause Dabei: $x\in L(TM)$ $\Leftrightarrow$ von $s_0x\Box$ ist $us_fv$ mit $s_f\in F $ erreichbar.\pause Verhalten der TM nach Erreichen von $s_f$ für Akzeptieren unwichtig!\pause Daher: Turingmaschinen so definiert, dass sie nach Erreichen eines Endzustandes nicht weiterrechnen (können).\pause Jede $TM$ ist so modifizierbar, dass sie nur mit $...\Box s_f\Box ...$ akzeptiert...\pause Damit: \begin{quote} Eine Sprache $L $ ist genau dann vom Typ 0, \pause\\ wenn die folgende Funktion $g:E^*\rightarrow E^*$ berechenbar ist:\pause \[g(x) = \left\{\begin{array}{ll}\pause\varepsilon&\pause\textrm{ für }x\in L\\ \pause\textrm{undefiniert}&\pause\textrm{ für }x\not\in L \end{array}\right.\] \end{quote} \end{example} \end{frame}} \only
{\begin{frame} Schlie"slich wollen wir noch einmal überlegen, was passieren kann, wenn die Maschine ein Wort $x $ \emph{nicht} akzeptiert. Dann wird sie niemals eine Konfiguration $us_fv$ mit beliebigen Wörtern und einem Endzustand $s_f $ erreichen. Dafür kann es zwei Gründe geben: Entweder sie hört nie auf zu rechnen, erreicht aber niemals einen Endzustand. Oder sie bleibt in einer Konfiguration, die keine Endkonfiguration ist, stecken, weil es zu dem gerade aktuellen Zustand und dem gerade unter dem Lese-Schreibkopf befindlichen Symbol keinen \"Ubergang gibt. Diesen zweiten Fall können wir nun ausschlie"sen, indem wir einen neuen Zustand $s_l $ einführen, und zu jedem Nicht-Endzustand $s$ und jedem Arbeitssymbol $a$ derart, dass es keinen \"Ubergang von $(s,a)$ aus gibt, einen \"Ubergang $\delta(s,a) = (s_l, a, N)$ einführen und zu jedem Arbeitssymbol $a$ einen \"Ubergang $\delta(s_l, a) = (s_l, a, N)$ einführen. Dann führt jedes Wort, das nicht akzeptiert wird, zu einer nie endenden Berechnung. Also ist eine Sprache genau dann vom Typ 0, wenn es eine deterministische Turingmaschine gibt, die genau bei den Wörtern aus $L $ (als Eingabe) anhält. All diese \"Uberlegungen kann man natürlich auch auf Mengen von Zahlen übertragen. Wir kommen später darauf zurück. \end{frame}} \only{\begin{frame} Bei $x\not \in L(TM)$ wird {\em nie} ein Endzustand $s_f$ erreicht, \pause mögliche Gründe: \begin{enumerate} \item Die Maschine rechnet endlos \pause oder \item die Maschine `bleibt stecken' \pause\\ (d.h. zu $s$ und $a$ kein Übergang $\delta(s,a)$ definiert) \end{enumerate} \pause Fall (2) vermeidbar mit Modifikation $\delta'$ von $\delta$:\pause \begin{itemize} \item neuer Zustand $s_l$ \pause mit $\delta'(s_l, a) = (s_l, a, N)$ für alle $a\in A$\pause \item $\delta'(s,a)= (s_l, a, N)$ \pause, falls $\delta(s,a)$ nicht definiert (für $s\in S\setminus F$) \end{itemize} \pause Damit: \begin{quote} Eine Sprache $L $ ist genau dann vom Typ 0, \pause\\ wenn es eine deterministische Turingmaschine gibt, \\die genau bei den Wörtern aus $L $ (als Eingabe) {\em anhält}. \end{quote} \end{frame}} \only
{\begin{frame} Wir wollen nun eine Mehrband-Turingmaschine $MTM$ mit $k\geq 1$ Bändern und Schreibköpfen definieren, die unabhängig voneinander operieren. Formal wird man die \"Ubergangsfunktion $\delta: S \times A^k\rightarrow S \times A^k\times \{L, R, N\}^k$ ansetzen und den Begriff der Konfiguration und \"Ubergangsrelation anpassen. Man kann nun zeigen, dass diese Mehrband-Turingmaschine, die ja zunächst stärker als eine Einbandmaschine erscheint und diese durch Stilllegung von $k{-}1$ Bändern simulieren kann, umgekehrt auch durch eine Einbandmaschine simuliert werden kann. \begin{theorem} Zu jeder Mehrbandmaschine $MTM$ gibt es eine Einbandmaschine $TM$, die dieselbe Sprache akzeptiert, bzw. dieselbe Funktion berechnet. \end{theorem} \end{frame}} \only{\begin{frame} Erweiterung der Turingmaschinen-Definition: \pause \Fb{ Mehrband-Turingmaschine $MTM$} \pause \begin{itemize} \item mit $k\geq 1$ Bändern und Schreibköpfen \pause \item alle Schreibköpfe können unabhängig voneinander operieren\pause \item \"Ubergangsfunktion $\delta: S \times A^k\rightarrow S \times A^k\times \{L, R, N\}^k$ \pause \item Definition von Konfiguration und \"Ubergangsrelation passend dazu... \pause \end{itemize} \begin{theorem} Zu jeder Mehrbandmaschine $MTM$\label{Mehrbandmaschine} gibt es eine Einbandmaschine $TM$, die dieselbe Sprache akzeptiert, bzw. dieselbe Funktion berechnet. \end{theorem} \end{frame}} \only
{\begin{frame} Beweis: Sei eine Mehrbandmaschine $MTM$ mit $k$ Bändern gegeben, die wir uns mit $1$ bis $k $ durchnummeriert denken. Sei $A$ ihr Arbeitsalphabet. Dann wollen wir eine Turingmaschine $TM$ konstruieren, die die $MTM$ simuliert. Dazu wird das Schreib-Leseband der $TM$ in $2k$ Spuren unterteilt, die wir uns mit $1$ bis $2k $ durchnummeriert denken. Dabei soll die Spur $2i{-}1$ den Inhalt von Band $i $ der $MTM $ enthalten. Die Spur $2i$ soll nur an einer Stelle das Zeichen $*$ und sonst nur Blanks enthalten. Das Zeichen $*$ soll anzeigen, dass der Lese-Schreibkopf des $i$-ten Bandes der $MTM$ gerade an dieser Stelle steht. Der Kopf der Einbandmaschine muss jetzt die Kopfpositionen der $MTM$ sukzessive abfahren. Daher wählen wir für die $TM$ das Arbeitsalphabet $A' = A\cup(A \cup \{*\})^{2k}$. \end{frame}} \only{\begin{frame} Beweisidee: \pause Gegeben Mehrbandmaschine $MTM$ \pause \begin{itemize} \item mit $k$ Bändern ($1$ bis $k$) \pause \item Arbeitsalphabet $A$ \end{itemize} \pause Konstruiere Turingmaschine $TM$, die $MTM$ simuliert: \pause \begin{itemize} \item Schreib-Leseband der $TM$ in $2k$ Spuren ($1$ bis $2k$ ) unterteilt \pause \item Spur $2i{-}1$ enthält Inhalt von Band $i$ der $MTM $ \pause \item Spur $2i$ hat an genau einer Stelle das Zeichen $*$, \pause ansonsten nur Blanks. \pause \item Das Zeichen $*$ zeigt an, dass der Lese-Schreibkopf des $i$-ten Bandes der $MTM$ gerade an dieser Stelle steht. \pause \item Kopf der $TM$ testet alle Kopfpositionen der $MTM$ nacheinander \pause \item Neues Arbeitsalphabet $A' = A\cup(A \cup \{*\})^{2k}$. \end{itemize} \end{frame}} \only
{\begin{frame} Die $TM$ simuliert die $MTM$ nun folgenderma"sen: Gestartet wird mit der Eingabe $a_1...a_n $ aus $E^*$. Dann erzeugt $TM$ zunächst die Startkonfiguration von $MTM$ in der Spurendarstellung. Die Startkonfiguration sieht so aus, dass das Eingabewort $a_1...a_n$ auf Spur $1$ steht, alle anderen ungeraden Spuren leer sind, und alle geraden Spuren an der ersten Position unter dem Lese-Schreibkopf einen Stern haben und ansonsten leer sind. Durch Laufen nach rechts bis zu dem am weitesten rechts stehenden $*$ oder evtl. eine Position darüber hinaus kann dann der Lese-Schreibkopf der $TM$ alle \"Anderungen vornehmen, die die Mehrbandmaschine in einem Schritt vornimmt. Dazu muss er in den Tupeln lesen, schreiben und eventuell die Sternmarken löschen und neu setzen (dazu muss er eventuell bei einer Linksbewegung eines Lese-Schreibkopfes noch einen Extraschritt nach links und rechts machen). Danach kehrt der Kopf wieder auf die am weitesten links stehende Marke zurück, und es kann der nächste Schritt der $MTM$ simuliert werden. \end{frame}} \only{\begin{frame} Arbeitsweise der $TM$: \pause \begin{itemize}\item Gestartet wird mit der Eingabe $a_1...a_n \in E^*$. \pause \item Zunächst erzeugt $TM$ die Startkonfiguration von $MTM$: \pause\\ --- Eingabewort $a_1...a_n$ auf Spur $1$ \pause\\ --- alle anderen ungeraden Spuren sind leer \pause\\ --- alle geraden Spuren haben $*$ unter dem Lese-Schreibkopf \pause \item In Spuren unterteilter Bereich des Bandes ist in Blanks eingeschlossen \pause\\ $\Rightarrow$ $TM$ kann stets durch Lauf über alle beschriebenen Zellen Information über den nächsten Schritt den $MTM$ sammeln \pause und ihn simulieren \pause \item jeder Einzelschritt der $MTM$ wird durch mehrere (=viele) Schritte der $TM$ simuliert. \end{itemize} \end{frame}} \only
{\begin{frame} Die Verwendung mehrerer Bänder bringt dennoch wesentlich Vorteile: Jedes Band stellt im Prinzip ein unendlich langes Register dar. Besitzt die Maschine nur eines dieser Register, wird sie Rechnungen, die $n$ Eingaben erfordern, nur in der angegebenen Form mit Hintereinander-Eintrag ausführen können. Hier werden die einfachsten Beispiele schon sehr unelegant in der Formulierung, da die $TM$ die meiste Zeit damit beschäftigt ist, zwischen den einzelnen Eingaben hin- und herzufahren. Bei einer Mehrbandmaschine werden die Eingaben untereinander geschrieben und können quasi gleichzeitig verarbeitet werden. Oft möchte man das Verhalten einer Einbandmaschine in einer $k$-Band-Turingmaschine auf Band $i$ simulieren. Die anderen Bänder bleiben unverändert. Dies wird dann durch $MTM(i,k)$ beschrieben. Es ist damit so etwas wie eine Projektionsmaschine definiert mit einer Projektion auf die $i$-te Koordinate. Die \"Ubergangsfunktion sieht dann z.B. folgenderma"sen aus: $\delta(s, a_1,..., c,..., a_k) = (s', a_1,..., d,..., a_k, N,...,R,..., N)$. Zur Erleichterung der Bezeichnung wird $k$ oft einfach gro"s genug gewählt und dann in der Schreibweise weggelassen. \end{frame}} \only{\begin{frame} Vorteile von Mehrbandmaschinen: \pause \begin{itemize} \item Jedes Band stellt ein unendlich langes Register dar. \pause \item Besitzt eine Maschine nur eines dieser Bänder, ist sie meist damit beschäftigt, auf diesem Band hin- und herzufahren... \pause \item Mehrbandmaschine: Daten auf Bänder verteilt, mit leichterem Zugriff \end{itemize} \pause Z.B.: Simulation einer Einbandmaschine mit $k$-Band-TM auf Band $i$ ohne Änderung der anderen Bänder: \pause \"Ubergangsfunktion dazu z.B. statt $\delta(s,c)=(s',d,R)$ jetzt\pause $$\delta'(s, a_1,..., c,..., a_k) = (s', a_1,..., d,..., a_k, N,...,R,..., N)$$ \pause I.d.R: $k$ gro"s genug gewählt und dann in der Schreibweise weggelassen... (Beispiele: später) \end{frame}} \only
{\begin{frame} Wir wollen nun zeigen, dass man einige Grundoperationen in Turingmaschinen implementieren kann und mit Turingmaschinen `programmieren' kann. Wir hatten in Beispiel \ref{Zaehlen mit TM} bereits gesehen, dass man mit einer Einbandmaschine Zahlen inkrementieren kann. Ein Mehrbandmaschine, die dies auf Band $i$ macht, wollen wir mit \begin{quote} Band $i$ := Band $i + 1$ \end{quote} beschreiben. Man kann auch leicht eine Maschine angeben, die Zahlen dekrementiert, d.h. die $n $ auf $n-1$ abbildet, wenn $n>0$, und auf 0, wenn $n = 0$. Ein Mehrbandmaschine, die dies auf Band $i$ macht, sei mit \begin{quote} Band $i$ := Band $i - 1$ \end{quote} beschrieben. Weiterhin möchten wir Elementaroperationen wie \begin{quote} Band $i := 0$ \end{quote} und \begin{quote} Band $i :=$ Band $j$ \end{quote} einführen. Wir weisen darauf hin, dass eine formale Behandlung all dieser Implementierungen es eigentlich nötig macht, die Turingtabellen anzugeben. Da die Operationen und ihre Verwirklichung jedoch einsichtig sind, wollen wir es unterlassen. \end{frame}} \only{\begin{frame} Im Folgenden: 'Programmieren' mit Turingmaschinen... \pause Vgl. Beispiel \ref{Zaehlen mit TM}, Inkrementieren von Zahlen mit Einbandmaschine \pause \begin{itemize} \item Analog $MTM$, die Inhalt von Band $i$ inkrementiert \pause\\ Schreibweise: \begin{quote} Band $i$ := Band $i + 1$ \end{quote} \end{itemize} \begin{itemize} \item \pause Analog: $MTM$, die Zahlen dekrementiert, \\ d.h. aus $n{>}0$ wird $n{-}1$, \pause Dekrement von $0$ sei wieder $0$ \pause\\ Schreibweise: \begin{quote} Band $i$ := Band $i - 1$ \end{quote} \end{itemize} \begin{itemize} \item \pause Weitere naheliegende Abkürzungen: \begin{quote} Band $i := 0$ \end{quote} \pause und \begin{quote} Band $i :=$ Band $j$ \end{quote} \end{itemize} \pause Hier Verzicht auf Angabe der Turingtabellen ... \end{frame}} \only
{\begin{frame} Ein weiterer wichtiger Aspekt ist die Ausführung mehrerer Operationen hintereinander und damit die Hintereinanderschaltung von Turingmaschinen. Zu zwei (Einband- oder Mehrband-)Turingmaschinen $$M_1= (S_1, E, A_1, \delta_1, s_{01}, \Box, F_1)$$ und $$M_2= (S_2, E, A_2, \delta_2, s_{02}, \Box, F_2)$$ von denen wir annehmen wollen, dass die Zustandsmengen $S_1$ und $S_2$ keine gemeinsamen Elemente haben, schreiben wir \[\multiinclude[graphics={width=14em}]{grafik/tm_1}\] oder \begin{quote} $M_1; M_2$ \end{quote} und meinen damit die Turingmaschine $$M= (S_1 \cup S_2, E, A_1 \cup A_2, \delta, s_{01}, \Box, F_2)$$ mit $$\delta = \delta_1 \cup \delta_2 \cup \{((s_f, a), (s_{02}, a, N)) \mid s_f\in F_1, a\in A_1\}$$ Dabei sind die \"Ubergangsfunktionen als Relationen über kartesischen Produkten geschrieben. \end{frame}} \only{\begin{frame} \begin{itemize}\item Hintereinanderschaltung von Turingmaschinen: \pause Gegeben \[M_1= (S_1, E, A_1, \delta_1, s_{01}, \Box, F_1)\] \[M_2= (S_2, E, A_2, \delta_2, s_{02}, \Box, F_2)\] \pause O.B.d.A. $S_1\cap S_2=\emptyset$ \pause Schreibweise \[\multiinclude[graphics={width=17em}]{grafik/tm_1}\] \pause oder $M_1; M_2$ \pause für $$M= (S_1 \cup S_2, E, A_1 \cup A_2, \delta, s_{01}, \Box, F_2)$$ \pause mit $$\delta = \delta_1 \cup \delta_2 \cup \{((s_f, a), (s_{02}, a, N)) \mid s_f\in F_1, a\in A_1\}$$ \end{itemize} \pause(Hier: \"Ubergangsfunktionen als Relationen über kartesischen Produkten) \end{frame}} \begin{frame} Beispiel: Die durch: \[\multiinclude[graphics={width=17em}]{grafik/tm_2}\] beschriebene Maschine realisiert die Operation `Band $i$ := Band $i + 3$'. \end{frame} \begin{frame} Weiteres Beispiel: Die Maschine \[\multiinclude[graphics={width=17em}]{grafik/tm_3}\] realisiert eine Verzweigung über die Endzustände $s_{f1}$ und $s_{f2}$ der Maschine $M $ und ein Fortfahren mit entweder $M_1$ oder $M_2$. \end{frame} \only
{\begin{frame} Nun wollen wir eine bedingte Verzweigung simulieren, bei der getestet wird, ob 0 (als Zahl) auf dem Band steht. Wir nennen die folgende Maschine ``Band = 0?''. Dazu wählen wir die Zustandsmenge $S := \{s_0, s_1, ja, nein\}$, wobei die Endzustände $ja$ und $nein$ seien. Das Arbeitsalphabet sei hier $A=\{0,1,\Box\}$. Die \"Ubergangsfunktion wird in der folgenden Tafel angegeben: \[\begin{array}{|c|c|c|c|} \hline \delta &1&0 &\Box\\\hline s_0 & (nein, 1, N) &(s_1, 0,R) & (ja, \Box, N) \\ \hline s_1 & (nein, 1, L) &(s_1, 0,R) & (ja,\Box , L)\\ \hline \end{array}\] \"Ahnlich wie in dem vorigen Beispiel kann man damit eine bedingte Verzweigung programmieren. Die gleiche Operation kann auch in der Form `Band$ i =0$?' mit einem entsprechenden Test auf Band $i $ vorgenommen werden. \end{frame}} \only{\begin{frame} Beispiel: Test, ob $0$ (als Zahl) auf dem Band steht, und bedingte Verzweigung \pause Schreibweise: \begin{quote} Band = $0$? \end{quote} \pause Zustandsmenge $S := \{s_0, s_1, ja, nein\}$ \pause Endzustände $ja$ und $nein$ \pause Arbeitsalphabet $A=\{0,1,\Box\}$. \pause \"Ubergangsfunktion: \[\begin{array}{|c|c|c|c|} \hline \delta &1&0 &\Box\\\hline s_0 & (nein, 1, N) &(s_1, 0,R) & (ja, \Box, N) \\ \hline s_1 & (nein, 1, L) & (s_1, 0,R) & (ja,\Box , L)\\ \hline \end{array}\] \pause Analog: \begin{quote} Band $i$ = $0$? \end{quote} \end{frame}} \only
{\begin{frame} Schlie"slich können wir eine WHILE-Schleife simulieren: \[\multiinclude[graphics={width=17em}]{grafik/tm_4}\] Dies wollen wir mit `WHILE Band $i \neq 0$ DO $M$' abkürzen. \end{frame}} \only{\begin{frame} Simulation einer WHILE-Schleife: \pause \[\multiinclude[graphics={width=17em}]{grafik/tm_4}\] \pause mit der Schreibweise \begin{quote} WHILE Band $i \neq 0$ DO $M$ \end{quote} \end{frame}}