= Solution
Fix an effective enumeration $\varphi_0,\varphi_1,\ldots$ of unary partial computable functions. The <diagonal halting set> is
$$
K=\{e:\varphi_e(e)\downarrow\}.
$$
It is a <computably enumerable set>: on input $e$, simulate $\varphi_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$. \b[Thus $K$ is computably enumerable but not computable.]
Back to article page
