\begin{frame}{The Halting Problem is Undecidable}
    \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$.

    Then \emph{every recursively enumerable language was recursive}!\!\!\!\\
    Let $M$ be a deterministic Turing machine and $x$ a word.
    We can decide $x \in L(M)$ as follows:
    \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)$.
    The algorithm always terminates, so $L(M)$ is recursive.
    not every recursively enumerable language is recursive.

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