\begin{frame}{Union and Intersection} \begin{goal}{Theorem} If $L_1$ and $L_2$ are recursively enumerable languages, then so are \begin{talign} L_1 \cup L_2 && L_1 \cap L_2 \end{talign} \end{goal} \pause \begin{block}{} Let $M_1$ and $M_2$ be Turing machines such that \begin{talign} L(M_1) = L_1 && L(M_2) = L_2 \end{talign} \pause Create a Turing machine $M$ that \alert{runs $M_1$ and $M_2$ in parallel}.\\ (Alternating simulate one step of $M_1$ and one step of $M_2$.) \pause \begin{itemize} \item For $L(M) = \alert{L_1 \cup L_2}$,\\ let $M$ accept as soon as $M_1$ accepts \alert{or} $M_2$ accepts. \pause \item For $L(M) = \alert{L_1 \cap L_2}$,\\ let $M$ accept as soon as both $M_1$ \alert{and} $M_2$ accept. \end{itemize} \end{block} \pause \begin{exampleblock}{} What about $L_1 \setminus L_2$? \end{exampleblock} \end{frame}