\begin{frame}{Not all Languages are Recursively Enumerable}
  A set $A$ is countable if there is a surjective function $f : \mathbb{N} \to A$.
   
  \begin{goal}{}
    There are \emph{countably} many TMs over an input alphabet $\Sigma$.
  \end{goal}
  
  \begin{goal}{}
    There are \emph{uncountable} many languages over $\Sigma$.
  \end{goal}
  \pause
  
  \begin{block}{Proof}
    Let $a \in \Sigma$.
    \smallskip
    
    Assume $L_0,L_1,L_2,\ldots$ is enumeration of all languages over $\{a\}$.
    \pause\medskip
    
    Define a language \alert{$L$} as follows:
    for every $i \geq 0$.
    \begin{talign}
      \alert{a^i \in L \iff a^i \not\in L_i}
    \end{talign}
    \pause
    Then for every $i \ge 0$, we have $L \ne L_i$.
    \pause\smallskip

    Thus $L$ is \emph{not} part of the above enumeration. Contradiction.
  \end{block}
  \pause

  \begin{goal}{}
    \emph{Conclusion}: not all languages are recursively enumerable.
  \end{goal}
\end{frame}


\themex{Universal Turing Machine}