Fast-growing noncomputable functions

I haven't read Radó's proof closely, but the following way to (A) seems to be pretty straightforward, at least for the busy-beaver output function $BB_o$, where $BB_o(n)$ is the maximal number of 1s left on the tape after an $n$-state machine terminates:

Let $f$ be any total computable function. Then there is a number $m$ such that the program

 1. X = m;
 2. X = f(X);
 3. X = X+1;
 4. output X

can be implemented in a machine with exactly $m$ states. (Basically this is just a matter of observing that we can construct the number $2^k$ using $O(k)$ states, for example). Furthermore we can insert any number of X=X+1 between steps 1 and 2, each costing exactly one state (namely move left and write a 1 on the tape). So the above program can actually be implemented in $m$ states for all sufficiently large $m$.

Now if $f(m) \ge BB_o(m)$ for infinitely many $m$, then one of those $m$s must be sufficiently large, but that leads to a contradiction, because the machine alluded to above has $m$ states, and so by definition $BB(m)$ must be at least $f(m)+1$.

Thus we must have $f(n) < BB_o(m)$ eventually.

Your goal is for the busy-beaver time function, $BB_t(n)$ is maximum number of steps an $n$-state machine can take before it terminates. But this easy reduces to the above case: since $BB_t(n)\ge BB_o(n)$, a function that exceeds $BB_t(n)$ infinitely often must also exceed $BB_o(n)$ infinitely often -- which we've just seen is impossible for computable functions.


For a $h$ that satisfies (B) but not (A) we can take

$$ h(n) = \begin{cases} 42 & \text{if } n=0 \\ BB(n) & \text{if } h(n-1) < (n-1)^2 \\ h(n-1)+1 & \text{otherwise} \end{cases} $$

Then $h(n) < n^2$ infinitely often, so $f(n)=n^2$ is a counterexample to (A).

On the other hand $h(n)=BB(n)$ infinitely often, so an $f$ that eventually exceeds $h(n)$ would exceed $BB(n)$ infinitely often, which is impossible by the above argument.


After some digging I can answer the part about Turing degrees in my own question. It turns out that condition (B) is, indeed, weaker, than condition (A) at the Turing degree level. More precisely:

  • A Turing degree $\mathbf{a}$ is "hyperimmune" iff there is an $\mathbf{a}$-computable function $h$ that satisfies (B), i.e., that is not dominated by any computable function $f$. (See, e.g., Downey & Hirschfeldt, Algorithmic Randomness and Complexity (Springer, 2010), definition 2.17.1 on p. 67, or Miller & Martin, "The Degrees of Hyperimmune Sets", Z. Math. Logik 14 (1968), corollary 1.1 on p. 160.)

  • A Turing degree $\mathbf{a}$ is satisfies $\mathbf{a}'\geq 0''$ (when $\mathbf{a} \leq 0'$ this condition is called "high") iff there is an $\mathbf{a}$-computable function $h$ that satisfies (A), i.e., that dominates any computable function $f$. (See, e.g., Downey & Hirschfeldt, Algorithmic Randomness and Complexity (Springer, 2010), theorem 2.33.7 on p. 97, or Martin, "Classes of Recursively Enumerable Sets and Degrees of Unsolvability", Z. Math. Logik 12 (1966), lemmata 1.1 and 1.2.)

So my question was whether there is a Turing degree which satisfies the first but not the second. But in fact, any computably enumerable degree other than $0$ is hyperimmune (this was essentially my argument why busy beaver satisfies (B): see here, which in fact answers my question inter alia), and not all such degrees are high (e.g., there exist low c.e. degrees).