24/85
\begin{frame}{Turing Machine Computations}
\begin{block}{}
The \emph{computation steps $\vdash$} on configurations are defined by:
\begin{talign}
&& \text{if }\delta(q,a) = (q',b,R) \\
&& \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}