\begin{frame}{Properties of Recursive Languages}
  \begin{goal}{Theorem}
    If $L$, $L_1$ and $L_2$ are recursive, then so are
    \begin{talign}
      \overline{L} &&
      L_1 \cup L_2 &&
      L_1 \cap L_2 &&
      L_1 \setminus L_2 &&
      L^* &&
      L_1L_2 
    \end{talign}
  \end{goal}
  \pause
  
  \begin{proof}{}
    Let $L$, $\overline{L}$, $L_1$, $\overline{L_1}$, $L_2$ and $\overline{L_2}$ be recursively enumerable (r.e.).  
    \begin{itemize}
    \pause
      \item \alert{$\overline{L}$}:
        $\overline{L}$ and $\overline{\overline{L}} = L$ are r.e.
    \pause
      \item \alert{$L_1 \cup L_2$}:
        $L_1 \cup L_2$ and $\overline{L_1 \cup L_2} = \overline{L_1} \cap \overline{L_2}$ are r.e.
    \pause
      \item \alert{$L_1 \cap L_2$}:
        $L_1 \cap L_2$ and $\overline{L_1 \cap L_2} = \overline{L_1} \cup \overline{L_2}$ are r.e.
    \pause
      \item \alert{$L_1 \setminus L_2 = L_1 \cap \overline{L_2}$}
    \pause
      \item \alert{$L_1L_2$}, \alert{$L^*$}: 
        same proof as for recursively enumerable languages. Observe that the constructed Turing machine halts on all inputs if $M_1$, $M_2$ and $M$ do.
    \end{itemize}
  \end{proof}
  
\end{frame}