Halting Problem is Not Algorithmically Decidable

Theorem

Let $H: \N^2 \to \N$ be the function given by:

$\map H {m, n} = 1$ if $m$ codes a URM program which halts with input $n$

$\map H {m, n} = 0$ otherwise.

Then $H$ is not recursive.

Proof

We perform a proof by Cantor's Diagonal Argument.

Aiming for a contradiction, suppose $H$ is recursive.

Consider the universal URM computable function $\Phi_1: \N^2 \to \N$.

Let $f: \N \to \N$ be the function given by:

$\map f n = \begin{cases}

\map {\Phi_1} {n, n} & : \map H {n, n} = 1 \\ 0 & : \text{otherwise} \end{cases}$

As $H$ is recursive, the relation $\map H {n, n} = 1$ is also recursive.

The universal function is recursive as all URM computable functions are recursive.

Also, $\map {\Phi_1} {n, n}$ is defined when $\map H {n, n} = 1$.

The constant $0$ is (primitive) recursive and always defined.

So $f$ is total, and by Combination of Recursive Functions it is also recursive.

It follows immediately that the function $g: \N \to \N$ given by:

$\map g n = \map f n + 1$

is also recursive.

So by Universal URM Computable Functions there exists some $e \in \N$ such that:

$\forall n: \map g n = \map {\Phi_1} {e, n}$

that is, the URM program coded by $e$ computes $g$.

Hence:

$\map g e = \map {\Phi_1} {e, e}$

But since $e$ codes a URM program which halts with input $e$, we have:

$\map H {e, e} = 1$

and so:

$\map f e = \map {\Phi_1} {e, e}$

Therefore, by definition of $g$, we have:

$\map g e = \map {\Phi_1} {e, e} + 1$

This contradiction arose because we assumed that $H$ is recursive.

Hence the result.

$\blacksquare$