\documentclass[12pt]{article}
\usepackage{german}
\usepackage[latin1]{inputenc}
\usepackage{amsfonts}
\textwidth=16,1cm
\textheight=24cm
\hoffset = -19mm
\voffset = -25mm
\let\eps\varepsilon

\begin{document}
\noindent
Die folgende Turingmaschine berechnet die Summe zweier Zahlen in Binärdarstellung. 
 Bei
  Eingabe von bin($x$){\tt\#}bin($y$){\tt\$} und Start im Zustand
$q_0$ hält die Maschine im
  Zustand $q_F$ mit der Ausgabe bin($x+y$){\tt\#}bin($y$){\tt\$} und
  dem Kopf auf dem ersten Eingabesymbol.  (Die Notation
  bin$(x)\in\{0,1\}^*$ ist eine Darstellung von $x\in \mathbb{N}$ in
  Binärdarstellung.)  Der Bandinhalt rechts vom \texttt{\$}-Zeichen
  bleibt dabei unverändert stehen.

Beginnend von rechts, wird jeweils das erste nicht markierte
Bit von $y$ und von $x$ markiert. Wenn dieses Bit von $y$ gleich 1 ist,
wird es zur entsprechenden Stelle von $x$ addiert, und gegebenenfalls
ein Übertrag nach links weitergereicht.
Ein $B$-Symbol am Anfang von
$x$ wird dabei wie eine $0$ behandelt.
Wenn alle Stellen von $y$ markiert sind, werden alle Markierungen
gelöscht, und der Automat hält.
\par\smallskip

  {\offinterlineskip \small
\halign{\hfil$#$\hfil\ \strut\vrule\ &
 \hfil$#$\hfil\ & \hfil$#$\hfil\ &
 \hfil$#$\hfil\ & \hfil$#$\hfil\ &
 \hfil$#$\hfil\ & \hfil$#$\hfil\hskip-0,3em &
\hskip-0,3em \hfil$#$\hfil\ &\vrule\  #\hfil\cr
\delta&0&1&\bar0&\bar1&\#&\$&B&Kommentar\cr
\noalign{\hrule}
q_0& (q_0,0,R) & (q_0,1,R) &(q_0,\bar0,R)&(q_0,\bar1,R)&
 (q_0,\#,R) & (q_1,\$,L) &-
&fahre nach rechts\cr
q_1& (q_2,\bar0,L) & (q_4,\bar1,L) &(q_1,\bar0,L)&(q_1,\bar1,L)& (q_7,\#,R) &
  - & -
&finde erstes nicht markiertes\cr
&&&&&&&& \ \ Bit $y_0$ von $y$ und markiere es\cr
q_2& (q_2,0,L) & (q_2,1,L) &-&-& (q_3,\#,L) &
  - & -
&falls $y_0=0$, finde erstes unmar-\cr
q_3& (q_0,\bar0,N) & (q_0,\bar1,N) &(q_3,\bar0,L)&(q_3,\bar1,L)& - &
  - & (q_0,\bar0,N)
&\ \ kiertes Bit von $x$, markiere es.\cr
q_4& (q_4,0,L) & (q_4,1,L) &-&-& (q_5,\#,L) &
  - & -
&falls $y_0=1$, finde erstes Bit\cr
q_5& (q_0,\bar1,N) & (q_6,\bar0,L) &(q_5,\bar0,L)&(q_5,\bar1,L)& - &
  - & (q_0,\bar1,N)
&\ \ von $x$,
markiere es, addiere 1,\cr
q_6& (q_0,1,N) & (q_6,0,L) &-&-&-&
  - & (q_0,1,N)
&gegebenenfalls Übertrag\cr
q_7& -&-&(q_7,\bar0,R) & (q_7,\bar1,R) &-&
 (q_8,\$,L)&-
&Ende, fahre ganz nach rechts\cr
q_8& (q_8,0,L)&(q_8,1,L)&(q_8,0,L) & (q_8,1,L) &(q_8,\#,L)&-& (q_F,B,R)
& nach links, lösche Markierungen\cr
}}

\medbreak

\noindent
$ \let\oldvdash=\vdash \def\vdash{
            \mskip 1,8mu plus2mu
\allowbreak\oldvdash\allowbreak  \mskip 0,0mu plus2mu
}
 \def \q_#1{{\mathit {q_{\mathrm#1}}}}
\catcode`q=\active
\let q=\q
\tt
 q_0 101\#11\$
\vdash
 1q_0 01\#11\$
\vdash
 10q_0 1\#11\$
\vdash
 101q_0 \#11\$
\vdash
 101\#q_0 11\$
\vdash
 101\#1q_0 1\$
\vdash
 101\#11q_0 \$
\vdash
 101\#1q_1 1\$
\vdash
 101\#q_4 1\bar 1\$
\vdash
 101q_4 \#1\bar 1\$
\vdash
 10q_5 1\#1\bar 1\$
\vdash
 1q_6 0\bar0\#1\bar 1\$
\vdash
 1q_0 0\bar0\#1\bar 1\$
\vdash
 11q_0 \bar0\#1\bar 1\$
\vdash
 11 \bar0q_0\#1\bar 1\$
\vdash
 11 \bar0\#q_01\bar 1\$
\vdash
 11 \bar0\#1q_0\bar 1\$
%\stackrel*\vdash
% 10\bar0 \bar0\#q_0\bar 1\bar 1\$
\vdash \cdots \vdash
% 10\bar0 \bar0\#\bar 1q_0\bar 1\$
%\vdash
 10\bar0 \bar0\#\bar 1\bar 1q_0\$
\vdash
 10\bar0 \bar0\#\bar 1q_1\bar 1\$
\vdash
 10\bar0 \bar0\#q_1\bar 1\bar 1\$
\vdash
 10\bar0 \bar0q_1\#\bar 1\bar 1\$
\vdash
 10\bar0 \bar0\#q_7\bar 1\bar 1\$
\vdash
 10\bar0 \bar0\#\bar 1q_7\bar 1\$
\vdash
 10\bar0 \bar0\#\bar 1\bar 1q_7\$
\vdash
 10\bar0 \bar0\#\bar 1q_8\bar 1\$
\vdash
 10\bar0 \bar0\#q_8\bar11\$
\vdash
 10\bar0 \bar0q_8\#11\$
\vdash
 10\bar0q_8\bar0\#11\$
\vdash
 10q_8\bar00\#11\$
\vdash
 1q_8000\#11\$
\vdash
 q_81000\#11\$
\vdash
 q_8B1000\#11\$
\vdash
 q_F1000\#11\$
.$

\end{document}
