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