28/113
\begin{frame}{From Turing Machines to Unrestricted Grammars}
\begin{block}{Theorem}
For every TM $M$ there is a grammar $G$ with $L(G) = L(M)$.
\end{block}
\pause

\begin{construction}
The variables are $S,T,\alert{\Box}$\\
\ \hfill and $V_\gamma^\alpha,V_{q\gamma}^\alpha$ for every $\alpha \in \Sigma \cup \{\Box\}$, $\gamma \in \Gamma$ and $q\in Q$.
\pause\medskip

\emph{Step 1}: guessing the word $w$
\begin{talign}
S &\to V_\Box^\Box S \mid S V_\Box^\Box\mid T \\[-.25ex]
T &\to T V_a^a \mid V_{q_0a}^a &&\text{for every } a \in \Sigma
\end{talign}
\pause
After step 1, we have derived something of the form
\begin{talign}
V^\Box_\Box \cdots V^\Box_\Box
where $w = a_1a_2 \cdots a_n$.