Suppose $A<_T B$ ($A$ is a set computable from $B$ but not vice versa). Is it always the case that there exists a $B$-computable function which eventually outgrows all $A$-computable functions?

Of my main interest is the case when $A\equiv_T 0$, and then the problem becomes: does there, for every nonrecursive set, exist a function computable relative to this set which eventually outgrows all recursive functions?

Thanks in advance.


2 Answers 2


Throughout, "function" means "total function."

The answer is no! In fact, there are nonzero Turing degrees which only compute functions which are bounded by some computable function. Such degrees are called "hyperimmune-free", or (more understandably) "computably bounded." See "The degrees of hyperimmune sets" by Martin and Miller (http://onlinelibrary.wiley.com/store/10.1002/malq.19680140704/asset/19680140704_ftp.pdf;jsessionid=E405B74AF3BACA6B19A8C2AB89A2B18F.f01t04?v=1&t=i2rw976w&s=b6a32a82943c14873f71c5872ff6a63cf96db9a8). And, of course, this relativizes nicely: for every degree $d$, there is a degree $e>_Td$ such that every function in $e$ is dominated by some function in $d$.

Note that there are no c.e. (or r.e.) hyperimmune-free degrees. If $C$ is a c.e. set, it is computable from any function which outgrows its modulus, which in turn is computable from $C$.

EDIT: Actually, this is true for all $\Delta^0_2$ degrees, i.e. all degrees below $0'$, by the same argument: by the limit lemma, every $\Delta^0_2$ set is the limit of some computable function, and this provides the relevant notion of "modulus." So every degree $\le_T 0'$ is hyperimmune.

You may find section 5 of this paper http://www.math.uconn.edu/~damir/papers/pi01classes.pdf by Soare, Dzhafarov, and Diamondstone to be interesting.

As with the case of high sets, the class of hyperimmune-free sets is meagre and has measure zero; see the computability menagerie http://bing.math.wisc.edu/menagerie#coloring=measure,showKey=false,showHelp=false. Note that in comparison with Bjorn's answer, not every non-high set is hyperimmune-free (e.g., a low c.e. set); a non-high degree has the property that every function in it is escaped by some computable function, but only the hyperimmune-free degrees have every function dominated by some computable function.

  • $\begingroup$ So let me get this straight - if there is $A$-computable function which isn't bounded by any computable function, then degree of $A$ is hyperimmune, and "most" of degrees are hyperimmune, in particular all recursively enumerable degrees are hyperimmune. Is this right? $\endgroup$
    – Wojowu
    Nov 21, 2014 at 20:12
  • $\begingroup$ Yes, that seems correct. It's worth noting that there are three common senses of the word "most" in computability theory - comeager, measure 1, and "on a cone." Generally, properties which imply computability-theoretic strength fail for comeager- and measure 1-many sets, but hold on a cone (this last bit is usually quite trivial to prove; it amounts to "strength is preserved upwards"): so, for example, the set of reals computing some fixed (uncomputable) $X$ is measure 0 and is meager, but of course holds on the cone above $X$. Hyperimmunity is a strength property, so it follows this pattern. $\endgroup$ Nov 21, 2014 at 22:39
  • $\begingroup$ Two further comments. First, note that there are absolutely no dependencies between the three notions of "most:" the sets $\{$1-randoms$\}$, $\{$1-generics$\}$, and $\{$computing 0'$\}$ are large only in the measure, category, and cone senses, respectively. Second, and more interestingly, the fact that - in this case - the r.e. degrees reflect "analytic mostness" is a phenomenon which only happens some of the time. For example, comeager and measure 1-many degrees fail to compute a complete consistent theory extending PA, but there are such degrees which are c.e. $\endgroup$ Nov 21, 2014 at 22:42
  • $\begingroup$ (Quibble: all nonzero c.e. degrees are hyperimmune.) $\endgroup$ Nov 21, 2014 at 22:43
  • $\begingroup$ Further, note that "$B$ hyperimmune" does not imply that $B$ computes a function dominating every computable function. To show this, it suffices to (a) prove Martin's domination theorem (this is the theorem of Bjorn's answer), and then (b) construct a non-high noncomputable c.e. degree via any of the standard arguments (the construction of a low simple set is probably fastest). $\endgroup$ Nov 21, 2014 at 22:48

Your condition is equivalent to $A''\le_T B'$, that is $B$ is high above $A$. Here $'$ is the Turing jump operator, i.e., the relativized halting problem operator.

In the case $A=0$, $B$ is high. The high degrees have measure zero, and are meager, so it is really a rather uncommon behavior.


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.