17/116
\begin{frame}{The Halting Problem is Undecidable (Proof 1)}
  \begin{proof}
    Assume that there was a deterministic TM $\mathcal{H}$
    that, given $(M,x)$ decides whether $M$ halts on $x$ (\,that is, $(M,x) \in H$\,).
    \pause\medskip

    Then 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}