8/85
\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}