12/85
\begin{frame}{Turing Machine Configuration}
\begin{block}{}
A \emph{configuration} $(q,c)$ of a Turing machine consists of
\begin{itemize}
\item a state $q \in Q$, and
\item a function $c : \mathbb{Z} \to \Gamma$, the \emph{tape content}.
\end{itemize}
The non-blank positions $\{ z \in \mathbb{Z} \mid c(z) \ne \Box \}$ are finite.
\smallskip

The head of the machine stands on $c(0)$.
\end{block}

\begin{center}
\def\cellwidth{10mm}
\def\cellheight{6mm}
\def\cellfrom{-3}
\def\cellto{3}
\begin{tikzpicture}[default,-,thin]
\draw [draw=none,fill=orange!15] (\cellfrom*\cellwidth - \cellwidth,\cellheight/2) rectangle (\cellto*\cellwidth + \cellwidth,-\cellheight/2);

\foreach \i in {\cellfrom,...,\cellto} {
\draw ({\cellwidth*(\i-0.5)},\cellheight/2) -- ({\cellwidth*(\i-0.5)},-\cellheight/2);
\node (cell\i) at ({\cellwidth*\i},0) {};
}
\draw ({\cellwidth*(\cellto+0.5)},\cellheight/2) -- ({\cellwidth*(\cellto+0.5)},-\cellheight/2);

\draw (\cellfrom*\cellwidth - \cellwidth,\cellheight/2) -- (\cellto*\cellwidth + \cellwidth,\cellheight/2);
\draw (\cellfrom*\cellwidth - \cellwidth,-\cellheight/2) -- (\cellto*\cellwidth + \cellwidth,-\cellheight/2);

\node [anchor=east] at (\cellfrom*\cellwidth - \cellwidth,0) {$\dots$};
\node [anchor=west] at (\cellto*\cellwidth + \cellwidth,0) {$\dots$};

\node (cu) [rectangle,rounded corners=2mm,draw,inner sep=2mm,fill=orange!15] at ($(cell0) + (0,2*\cellheight)$) {$q$};
\draw [<->] (cu) to ($(cell0) + (0,\cellheight/2)$);

\foreach \i/\t in {-3/c(-3),-2/c(-2),-1/c(-1),0/c(0),1/c(1),2/c(2),3/c(3)} {
\node [scale=0.9] at (cell\i) {$\t$};
}
\end{tikzpicture}\vspace{-1ex}
\end{center}
\pause

\begin{goal}{}
Let $n,m \in \mathbb{N}$ (exist for every configuration) such that
\begin{talign}
\forall i < -n.\; c(i) = \Box && \text{ and } &&
\forall i > m.\; c(i) = \Box
\end{talign}
Then we \emph{denote the configuration by the finite word}
\begin{talign}
c(-n) c(-n+1) \cdots c(-1) \;\alert{q}\; c(0) c(1) \cdots c(m)
\end{talign}
\end{goal}
\end{frame}