Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 1 / 12G / a / Solution

Fix an effective enumeration ${\phi }_0,{\phi }_1,\dots$ of unary partial computable functions. The diagonal halting set isIt is a computably enumerable set: on input $e$, simulate ${\phi }_e(e)$ and accept if that computation halts.

Suppose $K$ were a computable set. A program could then halt on input $e$ exactly when the decider says $e\notin K$. Let $d$ be its own index. If $d\in K$, the program does not halt, while if $d\notin K$, it halts. Both alternatives contradict the definition of $K$. Thus $K$ is computably enumerable but not computable.