\section{Berechenbarkeit mittels Turingmaschinen}
\inhalta{1-7}
\only<article>{\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<presentation>{\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<article>{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<presentation>{\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<article>{Das Wort  $uv$
 ist die aktuelle Bandinschrift (im schon beschriebenen oder besuchten Teil des Bandes)}
\only<presentation>{$uv$ ist aktuelle Bandinschrift,\pause}
\item  $s$
 ist der aktuelle Zustand,\pause
\item 
\only<article>{Der Schreib-Lesekopf steht auf dem ersten Zeichen von $v\Box$, weshalb $v\neq\varepsilon$ gelten muss.}
\only<presentation>{Schreib-Lesekopf über erstem Zeichen von $v$\pause, daher $v\neq\varepsilon$,\pause}
\item 
\only<article>{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<presentation>{Start der Maschine: \pause\\
Startkonfiguration $(\varepsilon,s_0,w\Box)$ bei Eingabe von $w$.\pause }
\end{itemize}
\only<article>{O.B.d.A. gilt $S\cap A=\emptyset$, daher schreiben wir eine Konfiguration
$(u,s,v)$ meist abgekürzt als $usv$ auf.}
\only<presentation>{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<article>{ 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<article>{ 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<presentation>{\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<article>{\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<article>{
 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<article>{\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<presentation>{\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<article>{ Wir wollen die Grundidee der Konstruktion nach Sander, Stucky und Herschel S. 194f. erläutern.}
\only<presentation>{\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<article>{Die \"Ubergangsfunktion definieren wir später in einer Tabelle.}


\only<article>{ 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<presentation>{\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<article>{\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<article>{\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<presentation>{\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<article>{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<presentation>{
\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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<article>{\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<presentation>{\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}}
