4
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented 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$
    – Noah Schweber
    Commented 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$
    – Noah Schweber
    Commented Nov 21, 2014 at 22:42
  • $\begingroup$ (Quibble: all nonzero c.e. degrees are hyperimmune.) $\endgroup$
    – Noah Schweber
    Commented 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$
    – Noah Schweber
    Commented Nov 21, 2014 at 22:48
5
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .