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