5
$\begingroup$

This is a question about two reducibility notions in computability theory. I suspect the answer is a fairly simple construction, and I'm just not seeing it.

For sets $X, Y\subseteq\omega$, we say $X$ is Turing reducible to $Y$ if there is a Turing machine $\Phi$ which, when given $Y$ as an oracle, yields (the characteristic function of) $X$, and we write $X\le_T Y$. We say $X$ is many-one reducible to $Y$ if there is some computable function $f$ such that $f(x)\in Y\iff x\in X$, and we write $X\le_mY$. Clearly many-one reducibility strictly implies Turing reducibility. A bit less clearly, the many-one degrees within a single Turing degree form a surprisingly large and interesting structure (see e.g. http://www.jstor.org/stable/2695042?seq=1, which among other things taught me that "objective" and "subjective" are technical terms in computability theory).

My question is the following:

Suppose $X\le_T Y$. Is there a set $A\equiv_T X$ such that $A\le_mY$?

Note that it is important that $Y$ is kept fixed, here: we of course always have $X\le_m Y\oplus X$, so allowing $Y$ to vary would make the question trivial. This observation amounts to saying that the relation $\le_m\subseteq deg(X)\times deg(Y)$ is total; and the question I am asking is whether it is surjective as well.

$\endgroup$
1
  • 3
    $\begingroup$ The answer is no. Let $Y$ be the halting problem and $X$ be a 1-generic set below $Y$. $\endgroup$
    – 喻 良
    Apr 2, 2014 at 2:17

1 Answer 1

12
$\begingroup$

No. A set is $m$-reducible to the Halting Problem iff it is computably enumerable, so let $Y$ be the Halting Problem and let $X$ be any $\Delta^0_2$ set not of c.e. Turing degree.

$\endgroup$
1
  • 1
    $\begingroup$ Very nice, I definitely should have seen that! $\endgroup$ Apr 2, 2014 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.