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?

  • $\begingroup$ 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$)? $\endgroup$ Nov 17, 2012 at 0:54
  • $\begingroup$ 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). $\endgroup$ Nov 17, 2012 at 13:32
  • $\begingroup$ @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. $\endgroup$
    – Gro-Tsen
    Nov 22, 2012 at 0:05

2 Answers 2


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.


My second and third points in this old question have already been answered satisfactorily by Dan Turetsky, but let me add the following as an answer to the first point:

The relation $f \mathop{\preceq_{\mathrm{S}*}} g$ (defined in the question: $f$ can be extended to a funtion $\hat f$ that is Sasso-reducible to $g$) is equivalent to the notion of Turing-Weihrauch reducibility, also known as generalized Weihrauch reducibility, in the particular case (as considered in the present question) when $f$ and $g$ are single-valued functions. See Takayuki Kihara, “Rethinking the notion of oracle” (whose footnote 2 on page 5 in arXiv version 3 links to this question), and the many references it cites, for a discussion of this notion of Turing-Weihrauch reducibility in the general context where $f$ and $g$ are multi-valued functions (and a further extension to “extended Weihrauch reducibility”).

(This makes me wonder whether $f \mathop{\preceq_{\mathrm{N}*}} g$, which Dan Turetsky's answer proves is a strictly coarser relation, can also be made to appear in a natural way in the context of Weihrauch reducibility. So far I do not know.)


Your Answer

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

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