\begin{frame}{Proof}
  \begin{block}{}
    \alert{$(\Leftarrow)$}
    $L$ accepted by deterministic TM $M$ that always halts.
    \pause\smallskip

    We show that $\overline{L}$ is recursively enumerable.
    \pause\smallskip
    
    From $M$ we construct a Turing machine $N$ as follows:
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item Add a fresh state $q_f$.
      \item For all $q \in Q \setminus F$ and $a \in \Gamma$: \\
        if $\delta(q,a)$ undefined, define $\delta(q,a) = (q_f,a,R)$.
      \item Make $q_f$ the only final state.
    \end{itemize}
    \pause
    Then $L(N) = \overline{L(M)}$, thus $L(M)$ is recursive.
  \end{block}
  \pause
  
  \begin{block}{}
    \alert{$(\Rightarrow)$} $L$ and $\overline{L}$ accepted by deterministic TMs $M_1$ and $M_2$.
    \pause\medskip
    
    Construct a TM $M$ executes $M_1$ and $M_2$ in parallel:
    \begin{itemize}
      \item $M$ \alert{accepts} when \alert{$M_1$} accepts
      \item $M$ has \alert{non-accepting} halting state when \alert{$M_2$} accepts
    \end{itemize}
    \pause
    Then $L(M) = L(M_1) = L$, and $M$ halts for every input.
  \end{block}
\end{frame}