\begin{frame}{Turing Machines}
  \medskip

  We introduce a \emph{blank symbol $\Box$}.
  The initial tape content is
  \vspace{-0.5ex}
  \begin{talign}
    \cdots \Box\Box\Box\Box \;\; \text{input word} \;\; \Box\Box\Box\Box\cdots\\[-3.5ex]
  \end{talign}
  There is a finite set of states $Q$ and a finite tape alphabet $\Gamma$.
  \pause
  
  \begin{goal}{}
    The transition function $\delta$ has the form
    \begin{talign}
      \alert{\delta : Q \times \Gamma \to Q \times \Gamma \times \{\,L,R\,\}}
    \end{talign}
    Here $\delta$ is a \emph{partial function}: $\delta(q,a)$ may be undefined.
  \end{goal}
  \pause
  
  \begin{goal}{}
    \alert{$\delta(q,a) = (q',b,X)$} means: if
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item the machine is in state \alert{$q$}, and
      \item the head reads \alert{$a$} from the tape
    \end{itemize}
    then
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item then $a$ is overwritten by \alert{$b$}, 
      \item the head moves $1$ position \alert{left} if $X = L$, \alert{right} if $X = R$, and
      \item the machine switches to state \alert{$q'$}.
    \end{itemize}
  \end{goal}
\end{frame}