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}