\begin{frame}{The Halting Problem is Undecidable}
  \begin{proof}
    \emph{Assume the halting problem was decidable.} Then there is a Turing machine $\mathcal{H}$
    that, given $(M,x)$ decides if $M$ halts on $x$.
    \pause\medskip

    Then \emph{every recursively enumerable language was recursive}!\!\!\!\\
    \pause\medskip
    
    Let $M$ be a deterministic Turing machine and $x$ a word.
    \pause\medskip
    
    We can decide $x \in L(M)$ as follows:
    \begin{itemize}
    \item If according to $\mathcal{H}$, $M$ does not halt on $x$, \\
      then $x \not\in L(M)$.
    \item If according to $\mathcal{H}$, $M$ halts on $x$, \\
      then execute $M$ on $x$ to see whether $x \in L(M)$.
    \end{itemize}
    \pause
    The algorithm always terminates, so $L(M)$ is recursive.
    \pause\medskip
    
    \emph{Contradiction:}
    not every recursively enumerable language is recursive.
  \end{proof}  
\end{frame}

\themex{The Halting Problem is Undecidable - Proof 2}