\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}