Undecidability of the Halting Problem

Suppose, for contradiction, that such a decider $H$ exists: $H(e,x)=1$ if $\varphi_e(x)\!\downarrow$ (halts) and $H(e,x)=0$ if $\varphi_e(x)\!\uparrow$ (runs forever), and $H$ itself always halts with the correct answer.

Using $H$, build a new program $D$ that, on input $e$: computes $H(e,e)$; if $H(e,e)=1$, then $D$ enters an infinite loop; if $H(e,e)=0$, then $D$ halts immediately. $D$ is built effectively from $H$ (just $H$ plus an if-statement and a loop), so it has some program index $d$, i.e. $D=\varphi_d$.

Now ask the self-referential question: does $\varphi_d(d)$ halt?

Case 1: if $\varphi_d(d)$ halts, then by correctness of $H$, $H(d,d)=1$. But by the definition of $D$, $H(d,d)=1$ makes $D$ loop forever on input $d$ — i.e. $\varphi_d(d)$ does not halt. Contradiction.

Case 2: if $\varphi_d(d)$ does not halt, then by correctness of $H$, $H(d,d)=0$. But by the definition of $D$, $H(d,d)=0$ makes $D$ halt on input $d$ — i.e. $\varphi_d(d)$ does halt. Contradiction.

Both cases are contradictory, so the assumption that $H$ exists is false. The Halting Problem is undecidable. $\blacksquare$