Many-one completeness of the halting problem
= Many-one completeness of the halting problem
Every <recursively enumerable set> many-one reduces to the <diagonal halting set>. If a program halts exactly on $X$, the <S-m-n theorem> produces from $x$ an index $g(x)$ for a unary program that ignores its input and performs that computation on $x$. Then
$$
x\in X\Longleftrightarrow g(x)\in K.
$$
Conversely, a computable preimage of a recursively enumerable set is recursively enumerable.