Total Turing reducibility

218 Views Asked by At

For $x, y\in 2^\omega$, say $x$ is totally reducible to $y$ - and write "$x\le_{Tot}y$" - if there is some Turing machine $\Phi_e$ which is total on every oracle (that is, $\Phi_e^z$ is total for all $z\in 2^\omega$) such that $\Phi_e^y=x$.

It is a neat exercise* to show that $\le_{Tot}$ is not the same as standard Turing reducibility, $\le_T$. On the other hand, it does share some basic properties:

  • $\le_{Tot}$ is a preorder on $2^\omega$ with the countable predecessor property.

  • The induced degree structure $\mathcal{T}=2^\omega/\equiv_{Tot}$ is an upper semilattice (with the usual join).

  • $\mathcal{T}$ has the exact pair property (the usual argument still works).

  • And some other basic properties, too.

I'm interested in anything that is known about the poset $\mathcal{T}$, and in particular, comparing $\mathcal{T}$ with the standard poset of Turing degrees $\mathcal{D}=2^\omega/\equiv_T$. Since there's a lot of potential questions here, let me ask specifically:

Does $\mathcal{T}$ have greatest lower bounds of pairs of elements?

Of course, glbs of pairs of elements do not always exist in $\mathcal{D}$, but as far as I can tell that proof does not immediately apply to $\mathcal{T}$.


*Fix $x$ non-computable and let $\Phi_c$ be the oracle machine which, with oracle $z$ and input $n$, halts and outputs 0 if “$01^{2n}0$” occurs before “$01^{2n+1}0$” in $z$, and halts and outputs 1 if “$01^{2n+1}0$” occurs before “$01^{2n}0$” in $z$. We can build a $y$ such that $\Phi_c^y=x$ but $x\not\le_{Tot}y$, by diagonalizing against every total-on-all-oracles index. Letting $e$ be such an index, and having built some initial segment $y_s$ of $y$, we can just “add enough 0s”: there is some $k$ such that $\Phi_e^{y_s^\smallfrown 0^k}(m)\downarrow\not=x(m)$ for some $m$ (since $x$ is not computable). The reduction $\Phi_c$ ignores strings of zeroes, so we can alternate between coding $x$ into $y$ and adding long strings of zeroes to diagonalize against total-on-all-oracles reductions.

1

There are 1 best solutions below

1
On BEST ANSWER

A classical theorem of Nerode shows that a set $A$ is truth-table reducible to a set $B$ if and only if there is a Turing reduction $\Phi$ of $A$ to $B$ such that $\Phi^X$ is total for every set $X$. So you have rediscovered truth-table reducibility.

There is a very large literature on truth table reducibility. It is mentioned in all the classic texts, and covered in some detail in the books by Rogers and Odifreddi, and elsewhere.