\begin{frame}{Context-Sensitive versus Recursive Languages} \begin{goal}{Theorem} Not every recursive language is context-sensitive. \end{goal} \pause \begin{proof} $\Sigma=\{0,1\}$. There exists an \emph{injective, computable function} \begin{talign} h : \{\,G \mid G \text{ context-sensitive}\,\} \to \{\,0,1\,\}^* \end{talign} such that the \emph{image} of $h$ is \emph{recursive}. For example: \begin{talign} h(0) &= 010 & h(\rightarrow) &= 01110 & h(A_i) &= 01^{i+4}0 \\[-.5ex] h(1) &= 0110 & h(;) &= 011110 \end{talign} \pause Define \alert{$L = \{\, h(G) \mid G \text{ context-sensitive} \;\wedge\; h(G) \not\in L(G) \,\}$}. \pause Then $L$ is recursive (by the above assumptions on $h$). \pause\medskip Assume \structure{$L = L(G_0)$} for a context-sensitive grammar $G_0$. \pause Then \begin{talign} h(G_0) \in L \;\;\text{\alert{$\iff$}}\;\; h(G_0) \not\in L(G_0) \;\;\text{\structure{$\iff$}}\;\; h(G_0) \not\in L \end{talign} \pause Contradiction! \end{proof} \end{frame}