\begin{frame}{Turing Machine Computations}
  \begin{block}{}
    The \emph{computation steps $\vdash$} on configurations are defined by:
    \begin{talign}
      v\alert{q}aw &\vdash vb\alert{q'}w 
        && \text{if }\delta(q,a) = (q',b,R) \\
      vc\alert{q}aw &\vdash v\alert{q'}cbw 
        && \text{if }\delta(q,a) = (q',b,L) 
    \end{talign}
    where $v,w \in \Gamma^*$, $a,c \in \Gamma$ and $q \in Q$.
  \end{block}
  We write $\vdash^*$ for a computation of zero or more steps.
  \pause
  
  \begin{exampleblock}{}
    Assume that ($\delta$ is undefined in all other case)
    \begin{talign}
      \delta(q_0,a) &= (q_0,a,R) &
      \delta(q_1,a) &= (q_1,b,L) &
      \delta(q_0,\Box) &= (q_1,c,L)
    \end{talign}
    Then we have steps:
    \begin{talign}
      q_0 aa 
      \mpause[1]{\vdash a q_0 a}
      \mpause{\vdash aa q_0}  
      \mpause{}
      \mpause{\vdash a q_1 ac}
      \mpause{\vdash q_1 abc}
      \mpause{}
      \mpause{\vdash q_1 \Box bbc}
    \end{talign}
    \mpause[3]{Here we use $aa q_0 \approx aa q_0 \Box$}\mpause[6]{ and $q_1 abc \approx \Box q_1 abc$.}
  \end{exampleblock}
  
  \mpause{
  \begin{block}{}
    A configuration $vqaw$ is a \emph{halting state} if $\delta(q,a) \text{ is undefined}$.
  \end{block}
  }
\end{frame}