23/113
\begin{frame}{From Unrestricted Grammars to Turing Machines}
\begin{block}{Theorem}
For every unrestricted $G$ there is a Turing machine $M$ such that
\begin{talign}
L(M) = L(G)
\end{talign}
\end{block}
\pause

\begin{construction}
Input for $M$ is a word $w$ (written on the tape).
\pause\medskip

$M$ can do a \emph{breadth-first search} for a derivation of $w$ from $S$.
\pause\medskip

If a derivation is found, then $w$ is accepted by $M$.
\pause\medskip

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