Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If $f$ and $g$ are partial functions $\mathbb{N} \to \mathbb{N}$, define six preorder relations $f \preceq g$ as follows:

  • $f \mathop{\preceq_{\mathrm{S}}} g$ ("$f$ is strict/Sasso reducible to $g$") when there exists a Turing machine with oracle that, when given $g$ as oracle, computes $f$ (with the convention that whenever the computation calls $g$ on an undefined value, it does not terminate; and by "computes $f$", we mean that the computation terminates on input $n$ exactly when $f(n)$ is defined and, when this is the case, it returns $f(n)$);

  • $f \mathop{\preceq_{\mathrm{N}}} g$ ("$f$ is nondeterministic/enumeration reducible to $g$") when there exists a nondeterministic Turing machine with oracle that, when given $g$ as oracle, computes $f$ in the sense that there is at least one terminating branch of computation on input $n$ exactly when $f(n)$ is defined and, when this is the case, all terminating branches return $f(n)$ (again with the convention that whenever a branch of computation calls $g$ on an undefined value, it does not terminate);

  • $f \mathop{\preceq_{\mathrm{W}}} g$ ("$f$ is weak reducible to $g$") when there exists a nondeterministic Turing machine with oracle as above, but with the additional constraint that whatever the oracle $h$ (a partial function $\mathbb{N} \to \mathbb{N}$) given to it, and whatever the input $n$, all terminating branches of computation (if there are any) must return the same value, i.e., the machine defines a "recursive operator" on partial functions $h$;

  • $f \mathop{\preceq_{\mathrm{S}*}} g$, $f \mathop{\preceq_{\mathrm{N}*}} g$ and $f \mathop{\preceq_{\mathrm{W}*}} g$ (perhaps call this "subreducible"?) mean that there exists a partial function $\hat f$ such that $\hat f \mathop{\preceq_{X}} g$ (for the corresponding subscript $X$ without the asterisk) and $f \subseteq \hat f$ (in other words, the Turing machine is permitted to compute more values than $f$).

(From what I understand, $\mathop{\preceq_{\mathrm{S}}}$ was defined by Leonard Sasso and $\mathop{\preceq_{\mathrm{N}}}$ is supposed to be equivalent to enumeration reducibility as defined in §9.7 of Roger's book on Recursive functions.)

Each of these six relations is reflexive and transitive, and is equivalent to ordinary Turing reduction when $f$ and $g$ are, in fact, total functions. So we get six different notions of "partial Turing degree" (S-degrees, N-degrees, etc.), all of which contain a subset isomorphic to the usual (total) Turing degrees. Also, $f \mathop{\preceq_{\mathrm{S}}} g$ implies $f \mathop{\preceq_{\mathrm{W}}} g$ which in turn implies $f \mathop{\preceq_{\mathrm{N}}} g$ and none of these implications can be reversed (Rogers §13.6, th. XIX); obviously each $f \mathop{\preceq_{X}} g$ implies $f \mathop{\preceq_{X*}} g$, and none of the converse (consider $g=0$ and $f$ the restriction of $g$ to a non recursively enumerable set). Furthermore, there exist N-degrees (and consequently W-degrees and S-degrees) which are do not contain a total function (=which are not total Turing degrees): see Rogers, §13.6, th. XVIII.

But my question is mostly about $(X*)$-degrees:

  • do they have a standard name? have they been studied?

  • is it even true that there exist $(X*)$-degrees which do not contain a total function, as it is true for the $X$-degrees?

  • are $\mathop{\preceq_{\mathrm{S}*}}$ and $\mathop{\preceq_{\mathrm{N}*}}$ distinct?

share|improve this question
    
When you refer to $X$-degrees and $f\leq_X g$ and so on, do you mean that $X$ is meant to indicate either $S$, $N$ or $W$ (but not $S^\ast$, $N^\ast$ or $W^\ast$)? –  Joel David Hamkins Nov 17 '12 at 0:54
    
Making this CW prevents answerers from earning the few necessary points to use the site properly. If all you want is not earning points for your contributions, let me suggest the following alternative. Make all your answers CW but leave your questions in normal mode. After a while take all the points you earned on the question and offer them as a bounty to the best answer. Then make the question CW to avoid earning more points (which will not affect the existing answers but will affect future answers). –  François G. Dorais Nov 17 '12 at 13:32
    
@Joel David Hamkins: I do, but I don't see which sentence could be ambiguous. @François G. Dorais: I didn't realize that making a question CW implied that all answers also automatically became CW: I thought it just meant anybody could edit the question. My bad. Apologies to Dan Turetsky for not getting points for his nice answer. –  Gro-Tsen Nov 22 '12 at 0:05

1 Answer 1

up vote 3 down vote accepted

I've never encountered these before, so I don't know anything about your first question.

Concerning your second question, you can force with finite extensions to build a non-trivial $g$ such that every total $f$ with $f \preceq_S g$ is computable. Given $g\upharpoonright n$, consider the oracle machine $\Phi_e$. Either there is some $m$ such that $\Phi_e^{g\upharpoonright n}(m)$ attempts to consult its oracle beyond $n$, or not. In the first case, take the first such spot beyond the input and commit to $g$ not being defined there; then by the reduction convention, $\Phi_e^{g\upharpoonright n}$ is partial. In the second case, since it only uses finitely much of its oracle, $\Phi_e^{g}$ must be computable.

Now, for total $f$, $f \preceq_{S*} g$ is the same as $f \preceq_S g$, so the $S*$-degree of $g$ contains no total function. I imagine something similar will work for the other reductions, but it would need to be a bit more sophisticated.

As for your third question, yes $\preceq_{S*}$ and $\preceq_{N*}$ are distinct. Fix $f$ your favorite total non-computable function. For every $x$, we will pick some $y_x$ and define $g(x,y_x) = f(x)$, and $g(x,z)$ undefined for all $z \neq y$. Clearly $f \preceq_{N*} g$, by non-deterministically trying all $y$.

On the other hand, we can arrange our choices of $y_x$ such that $f \not \preceq_{S*} g$. Suppose we have chosen $y_x$ for finitely many $x$, and now we wish to diagonalize against oracle-machine $\Phi_e$. Since $f$ is non-computable, in order to have $\Phi_e^g = f$, the machine must consult infinitely much of its oracle. So for some $m$, $\Phi_e^g(m)$ consults $g(x,z)$ such that we have not yet defined $y_x$. Choose $y_z \neq z$, to arrange that $\Phi_e^g(m)$ does not converge.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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