9/21

\begin{frame}{From Unrestricted Grammars to Turing Machines} \begin{goal}{Theorem} For every unrestricted $G$ there is a Turing machine $M$ such that \begin{talign} L(M) = L(G) \end{talign} \end{goal} \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}