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$.
Best Answer
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.