= Solution
The <S-m-n theorem> says that parameters can be compiled effectively into program indices: for a standard effective numbering, there is a <total computable function> $s_m^n$ with $\varphi_{s_m^n(e,\mathbf a)}(\mathbf x)=\varphi_e(\mathbf a,\mathbf x)$ for partial computable functions of $m+n$ arguments.
Write $K=\{e:\varphi_e(e)\text{ halts}\}$, a <recursively enumerable> <halting problem>. If $X$ is <recursively enumerable>, make a program with parameter $x$ which ignores its input and runs a semidecision procedure for $x\in X$, halting when that procedure halts. By the <S-m-n theorem> its index $f(x)$ is total computable and $f(x)\in K\iff x\in X$. Conversely, $X\leq_mK$ implies that $X$ is <recursively enumerable> by the previous construction. Thus $\boxed{X\text{ is r.e.}\iff X\leq_mK}$.
Back to article page
