16/21
\begin{frame}{From Turing Machines to Unrestricted Grammars}
\begin{block}{Construction continued}
\medskip

\emph{Step 2}: simulating the TM (in the subscripts)
\begin{talign}
V_{\alert{qc}}^\alpha V_{\alert{\gamma}}^\beta &\to V_{\alert{d}}^\alpha V_{\alert{q'\gamma}}^\beta
&& \text{if }\delta(q,c)=(q',d,R) \\[-.25ex]
V_{\alert{\gamma}}^\beta V_{\alert{qc}}^\alpha &\to V_{\alert{q'\gamma}}^\beta V_{\alert{d}}^\alpha
&& \text{if }\delta(q,c)=(q',d,L)
\end{talign}
for every $\alpha, \beta \in \Sigma \cup \{\Box\}$ and $\gamma \in \Gamma$.
\pause\medskip

\emph{Step 3}: If TM reaches accepting state, then generate $w$.
\hphantom{\emph{Step 3}: }(From the superscripts left unchanged in step 2.)
\begin{talign}
V_{q\gamma}^{\alert{\alpha}} &\to \alert{\alpha} &&\text{for every } q \in F \\[-.25ex]
\alert{\beta} V_\gamma^{\alert{\alpha}} &\to \alert{\beta\alpha} \\[-.25ex]
V_\gamma^{\alert{\alpha}} \alert{\beta} &\to \alert{\alpha\beta}  \\[-.25ex]
\Box &\to \lambda
\end{talign}
for every $\alpha, \beta \in \Sigma \cup \{\Box\}$ and $\gamma \in \Gamma$.
\pause\medskip

Then $L(G) = L(M)$.
\end{block}
\end{frame}