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