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. 



Relation between Turing degrees and functions computable with them
*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.


