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}