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