\begin{frame}{Turing Machines}
    Turing machines can \alert{read} and \alert{write} the input word.
  Input is written on a \alert{tape} on which a \alert{read-write-head} works.
      \foreach \i in {0,...,6} {
        \draw (.4*\i,0) -- (.4*\i,.4);
      \draw (-.2,0) -- (.4*6+.2,0);
      \draw (-.2,0.4) -- (.4*6+.2,0.4);
      \node [anchor=east] at (-.1,.2) {$\dots$};
      \node [anchor=west] at (.4*6+.1,.2) {$\dots$};
      \node [anchor=west] at (3.5,.2) {tape};

      \node (cu) [rectangle,rounded corners=2mm,draw,inner sep=2mm] at (1.2,2) {control unit};
      \draw [<->] (cu) to[out=-120,in=60,looseness=2] node [right,inner sep=2mm] {read-write-head} (1,.4);
  In each step:
    \item the read-write-head reads a symbol from the tape,
    \item overwrites the symbol, and
    \item moves one place to the left or right.
    The tape is two-sided infinite: \alert{unlimited memory}!