18/113
\begin{frame}{Unrestricted Grammars}
  \begin{goal}{}
    What class of grammars corresponds to Turing machines?
  \end{goal}
  \pause\bigskip
  
  \begin{block}{}
    An \alert{unrestricted} grammar $G$ contains rules
    \begin{talign}
      x \to y
    \end{talign}
    where \alert{$x\neq\lambda$}.
  \end{block}
  \medskip
  
  Note that there is no restriction other than $x$ being non-empty.
  \pause\bigskip
  
  \begin{block}{Theorem}
    A language $L$ is generated by an unrestricted grammar\\
    \hfill$\iff$ $L$ is accepted by a Turing machine.
  \end{block}  

\end{frame}