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