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