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