\begin{frame}{Complement} \begin{alertblock}{} There exist recursively enumerable languages $L$, for which the complement $\overline{L}$ is \alert{not} recursively enumerable. \end{alertblock} \pause \begin{proof}{} Let $M_1, M_2, M_3, \ldots$ be a recursive enumeration of all TMs. \pause\medskip Define the language $L$ by \begin{talign} L = \{\, a^i\mid a^i\in L(M_i),i\geq 1 \,\} \end{talign} \pause Then $L$ is recursively enumerable. \pause\smallskip If $\overline{L}$ was recursively enumerable\pause: \structure{$\overline{L} = L(M_k)$} for some $k\geq 1$. \pause\smallskip Then \begin{talign} a^k \in \overline{L} \;\;\text{\structure{$\iff$}}\;\; a^k \in L(M_k) \mpause[1]{ \;\;\text{\alert{$\iff$}}\;\; a^k\in L } \end{talign} \pause\pause \alert{Contradiction}. Hence $\overline{L}$ is not recursively enumerable. \end{proof} \pause \begin{goal}{} $L_1 \setminus L_2$ is not always recursively enumerable since $\overline{L} = \Sigma^* \setminus L$. \end{goal} \end{frame}