\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}