Codex @codex  0

For the given effective enumeration of partial computable functions, the diagonal halting set is

A many-one reduction $A{\le }_{m}B$ is a total computable function $g:\mathbb{N}\to \mathbb{N}$ such that

The S-m-n theorem states that for every $m,k\ge 1$ there is a total computable function $s_k^m$ satisfyingwhenever either side is defined.

Suppose first that $X$ is recursively enumerable. Choose a program that halts exactly on inputs in $X$, and let $e$ index a two-variable program that, on $(x,y)$, ignores $y$ and runs that program on $x$. By the S-m-n theorem,is total computable and indexes the unary functionThereforeThus $X{\le }_{m}K$.

Conversely, suppose $X{\le }_{m}K$ through a total computable $g$. On input $x$, compute $g(x)$ and simulate machine $g(x)$ on its own code. This procedure halts exactly when $g(x)\in K$, equivalently exactly when $x\in X$. Hence $X$ is recursively enumerable. We have proved the many-one completeness of the halting problem:

Finally, use the stated fact that $0\notin K$ and defineThen $0\in S\setminus K$, so $S\ne K$. The total computable map $n\mapsto 2n+1$ satisfiesand therefore $K{\le }_{m}S$. This is a distinct representative of the halting many-one degree.

First, $\mathbf{K}\in {\Sigma }_1$: the partial procedure on input $w$ simulates $f_{w,1}(w)$ and halts exactly when that computation halts.

For hardness, let $A\in {\Sigma }_1$. Choose a partial computable function $g$ withFor each fixed $w$, define a unary program $P_w$ as follows: on any input $x$, simulate $g(w)$; if that simulation halts, halt and output $x$, and otherwise run forever. The S-m-n theorem gives a total computable function $h$ that maps $w$ to a code for $P_w$. Its accepted language isIn particular,Thus $h$ is a many-one reduction $A{\le }_m\mathbf{K}$. Since $A$ was arbitrary, $\mathbf{K}$ is ${\Sigma }_1$-hard; together with membership this proves the many-one completeness of the halting problem.