Undecidability of the halting problem

Remarks

Suppose a machine $D$ decides $H$. Build a machine $N$ that, on input $e$, runs $D$ on $(e, e)$, loops forever if the answer is $1$, and halts if the answer is $0$. Let $n$ be a number of $N$. Then $N$ halts on $n$ if and only if $(n, n) \notin H$, that is, if and only if $N$ does not halt on $n$, a contradiction.

The set $H$ is computably enumerable, since a universal machine halts on $(e, x)$ exactly when $M_e$ halts on $x$. So $H$ is an example of a computably enumerable set that is not computable. By the same argument, the diagonal set $K = \set{e : M_e \text{ halts on input } e}$ is not computable.

Going deeper

For a student

This result goes back to Turing's paper of 1936, and it is the standard first example of an undecidable problem. Most other undecidability results are proved by reducing the halting problem to them. Examples are Rice's theorem, the undecidability of first-order validity, and the negative solution of Hilbert's tenth problem. In the arithmetical hierarchy, $H$ is $\Sigma^0_1$-complete.