\begin{frame}{Turing Machines} \begin{goal}{} Turing machines can \alert{read} and \alert{write} the input word. \end{goal} \medskip Input is written on a \alert{tape} on which a \alert{read-write-head} works. \begin{center} \begin{tikzpicture}[default,-,thin] \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); \end{tikzpicture}\vspace{-1ex} \end{center} \pause In each step: \begin{itemize} \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. \end{itemize} \pause \begin{goal}{} The tape is two-sided infinite: \alert{unlimited memory}! \end{goal} \end{frame}