9
$\begingroup$

This question was originally asked and bountied at MSE, but received no answer there, so I'm asking it again here.

Below, I'm specifically interested in weak truth table (wtt) reducibility, but other reducibilities between truth table and Turing are interesting to me, too, if the question happens to be easier to answer for them.

Let $d$ be a Turing degree, and fix a representative $X\in d$. Say $d$ is (wtt-)dodgy if there is some $d$-computable functional $F=\Phi_e^{X\oplus -}$ such that for all $Y$ with $deg(Y)=d$, we have

  • $\Phi_e^{X\oplus Y}=F(Y)$ is total,

  • $F(Y)\equiv_TY$, but

  • $F(Y)\not\le_{wtt}Y$.

(Note that I demand nothing about $F(Z)$ for $Z\not\in d$; in particular, $F$ only needs to output reals when fed elements of $d$, it may fail to be total elsewhere.)

Dodginess is most interesting for "sufficiently large" degrees - for example, above $0'$ every Turing degree splits into infinitely many $wtt$-degrees, so the question is nontrivial. Dodginess is a reasonably definable property, so by Martin's Cone Theorem, either every sufficiently large degree is dodgy or every sufficiently large degree is not dodgy. My question is, Which of these two holds?

My feeling is that a fairly simple trick should show that every sufficiently large (indeed, $\ge_T0'$) degree will not be dodgy; however, I don't see how to do this. In particular, the Recursion Theorem doesn't seem to immediately kill it: suppose $d$ is a sufficiently large degree, and fix $X\in d$. Then $F$ can be identified with a total computable function $g$: $F(\Phi_e^X)\sim\Phi_{g(e)}^X$. Now $g$ is total computable, so it has a fixed point $c$: $\Phi_c^X\sim \Phi_{g(c)}^X$. However, there's no reason to believe that $\Phi_c^X$ is total, let alone an element of $d$, so I don't see how to get any leverage here.

$\endgroup$
6
+150
$\begingroup$

Every sufficiently large degree is dodgy. Assuming $X \geq_T \emptyset'$, we can define $F(Y)$ as follows. First compute a set $Z$ from $X$ and $Y$: Given $n = \langle i,j \rangle$, ask $X$ whether $\Phi_i(n)$ converges. If not then $Z(n)=0$. If yes then ask $X$ whether $\Phi_j^{Y \upharpoonright \Phi_i(n)}(n)$ converges. If not then $Z(n)=0$. If yes then $Z(n)=1-\Phi_j^{Y \upharpoonright \Phi_i(n)}(n)$. This ensures that $Z \nleq_{wtt} Y$. Now let $F(Y)=X \oplus Z$. Then $F$ is total and $F(Y) \nleq_{wtt} Y$ for all $Y$, and if $Y \equiv_T X$ then also $F(Y) \equiv_T Y$.

$\endgroup$
  • $\begingroup$ Thanks! Do you know of any reducibilities stronger than Turing (but, necessarily, weaker than wtt) for which the corresponding notion of dodginess might fail on a cone? $\endgroup$ – Noah Schweber Mar 1 '17 at 21:54
  • $\begingroup$ No, I can't think of any. $\endgroup$ – Denis Hirschfeldt Mar 1 '17 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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