\begin{frame}{Turing Machine Configuration} So configurations are denoted by words from $\Gamma^* \times Q \times \Gamma^*$. \begin{exampleblock}{} For instance, the configuration \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/\Box,-2/e,-1/d,0/a,1/b,2/b,3/\Box} { \node [scale=0.9] at (cell\i) {$\t$}; } \end{tikzpicture}\vspace{-1ex} \end{center} can be denoted by \begin{talign} ed\,q\,abb \end{talign} \pause The words \begin{talign} ed\,q\,abb\Box &&\mpause[1]{\approx}&& \Box ed\,q\,abb &&\mpause[1]{\approx}&& \Box\Box ed\,q\,abb \Box && \cdots \end{talign} denote the same configuration. \end{exampleblock} \pause \begin{goal}{} We write $w \approx v$ if $w$ and $v$ denote the same configuration. \end{goal} \end{frame}