The halting problem is the most complicated of all recursively enumerable problems Wikipedia says that the following is true:

A set is many-one reducible to the halting problem if and only if it is recursively enumerable. This says that with regards to many-one reducibility, the halting problem is the most complicated of all recursively enumerable problems.

More precisely, the following conditions for a set $X\subset N$ are equivalent:


*

*$X=\{x:\phi_q(x)\downarrow\}$ for some program $q$ 

*there exists a computable function $f:N\to N$ such that $x\in X$ if and only if $fx\in\{p:\phi_p()\downarrow\}$ (i.e. $\phi_{fx}()\downarrow)$
(I'm using the notation from the 8th example here.)
How to prove this statement? I'm having a trouble defining the $f$ we need for one direction. And for the second it's also not very clear how to use the given $f$ to find $q$.
 A: As for how to use $f$ to find $q$: $q$ is the program which, on input $x$, computes the index $f(x)$ and then runs $\phi_{f(x)}(f(x))$. Computing $f(x)$ can be done because $f$ is by hypothesis computable; once that's done, $\phi_q(x)$ will converge if and only if $\phi_{f(x)}(f(x))$ does. Note that this $q$ is not necessarily the only program which will enumerate $X$, or even the most natural one; it's just a program that can do it.
For the other direction: given $x$, let $f(x)$ be the function which runs the program $q$ on $x$, regardless of input; in other words, $\phi_{f(x)}(y) = \phi_q(x)$ for all $x$ and all $y$. Then $\phi_{f(x)}(f(x))$ converges if and only if $\phi_q(x)$ does.
A: Suppose $X$ is recursively enumerable, that is: the domain of some partial function $\phi_e$. The function $\alpha(x, y) \simeq \phi_e(x)$ is partially computable, so by $smn$ there is a computable injection $f$ such that $\phi_{f(x)}(y) = \alpha(x, y)$. Now $\phi_{f(x)}(f(x))$ converges precisely when $\phi_e(x)$ does, so this is a many to one reducibility to the halting set.
Suppose $X$ many to one reduces to $K$ by $g$. Then $x \in X \iff g(x) \in K$. The halting set $K$ is the domain of some partially computable function $\phi$, so $X$ is the domain of $\phi \circ g$ which is also computable.  
