Fast-growing noncomputable functions

Question

A famous 1962 paper by Tibor Radó shows that the "busy beaver" function $h$ (which computes the maximal number of steps for which a halting Turing machine with $n$ states can run for) satisfies the property

• (A) for every computable total function $f\colon\mathbb{N}\to\mathbb{N}$ we have $h(n) \geq f(n)$ eventually (i.e., there exists $N$ such that for all $n\geq N$ we have $h(n) \geq f(n)$)

Now what is very easy to prove is the weaker

• (B) for every computable total function $f\colon\mathbb{N}\to\mathbb{N}$ we have $h(n) \geq f(n)$ infinitely often (i.e., for each $N$ there exists $n\geq N$ such that $h(n) \geq f(n)$)

(because if there were a computable $f$ such that $f(n)\geq h(n)$ eventually we could find one such that $f(n)\geq h(n)$ always, and then we could solve the halting problem for $n$ state Turing Machines by waiting at most $f(n)$ steps).

Now Radó's proof is fairly opaque, it looks like a bit of magic, I can't figure out the deep reason why he is able to prove (A) and not just (B): is it something really specific to the busy beaver function, or is there some general trick that makes it possible to derive (A) from (B)? So:

Does an increasing function $h$ that satisfies (B) automatically satisfy (A)? If not, is there some simple condition we can add to get (A) from (B) that would "explain" Radó's proof?

And, if the previous questions do not make this trivial:

Are there Turing degrees containing functions $h$ satisfying (B) but no function satisfying (A)?

Answer 1

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.

Answer 2

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).

Answer 3

(Posting a second answer for clarity because this relates to a different part of my question.)

Inspired by Henning Makholm's answer, I can prove the following statement which does not make any reference to a specific model of computability like Turing machines:

Let $\varphi_e$ be a standard enumeration of partial computable functions $\mathbb{N}^k\rightharpoonup\mathbb{N}$: the crucial fact in “standard” is that the s-m-n theorem holds with primitive recursive substitution function, i.e., there exists $s$ primitive recursive such that $\varphi_e(m,n) = \varphi_{s(e,m)}(n)$.

Let $h\colon\mathbb{N}\to\mathbb{N}$ be defined by $h(n) := \max\{\varphi_e(e) : 0\leq e\leq n \land \varphi_e(e)\downarrow\}$. (It is fairly obvious that $h$ satisfies (B).)

To be proven: In fact, $h$ satisfies (A), i.e., if $f\colon\mathbb{N}\to\mathbb{N}$ is computable then there exists $N$ such that $h(n) \geq f(n)$ for $n\geq N$.

Proof: Let $\gamma\colon\mathbb{N}\to\mathbb{N}$ be the diagonal Ackermann function. (What we need is that $\gamma$ is computable, increasing, and eventually dominates all primitive recursive functions, i.e. satisfies the analogue of (A) for primitive recursive $f$.)

Let $f\colon\mathbb{N}\to\mathbb{N}$ be any computable function. We want to show that $h(n) \geq f(n)$ for all $n$ sufficiently large. We define $g(k, j) := \max\{f(i) : 0\leq i\leq \gamma(k)\}$ (the variable $j$ is ignored). Let $p$ be an index for $g$, i.e., $g = \varphi_p$.

Now we have $\varphi_{s(p,k)}(j) = \varphi_p(k,j) = g(k,j) = \max\{f(i) : 0\leq i\leq \gamma(k)\}$ (again, $j$ is ignored). So if $n \geq s(p,k)$ and $i \leq \gamma(k)$ then $h(n) \geq f(i)$. In particular, if $s(p,k) \leq n \leq \gamma(k)$ then $h(n) \geq f(n)$.

But since $s(p,k+1)$ is a primitive recursion function of $k$, there exists $k_0$ such that if $k \geq k_0$, we have $\gamma(k) \geq s(p,k+1)$. Then if $n \geq s(p,k_0)$, there clearly exists $k$ such that $s(p,k) \leq n \leq \gamma(k)$, which implies $h(n) \geq f(n)$ as just explained. This proves that $h$ eventually dominates $f$. QED

Note that the proof works verbatim if we define $h$ by $h(n) := \max\{\varphi_e(0) : 0\leq e\leq n \land \varphi_e(0)\downarrow\}$ (the argument to $\varphi_e$ is only there because it is sometimes disturbing to consider and enumerate partial computable functions of $0$ arguments).

Applying this to Turing machines, it says that the function $h$ which maps $n$ to the maximal possible output of those among the $n$ first Turing machines which halt (for any “reasonable” numbering), eventually dominates any computable function. Since the maximal possible halting output of the $n$ first Turing machines is certainly at most equal to the maximal possible halting output of the at-most-$n$-state Turing machines, we recover Radó's result on the standard busy beaver function. But what I find interesting about this approach is that if makes it clear that we need to assume very little on the numbering: for any programming language in which composition is primitive recursive (a very weak requirement), the maximal possible halting output of the $n$ first programs will eventually dominate any computable function.

(How was I inspired by Henning Makholm's answer? Basically he uses $\gamma(k) = 2^k$ in saying “we can construct the number $2^k$ in $O(k)$ states”, something which is sufficient for the case of Turing machines and if we just count their number of states: it is this key “bootstrap” argument that I failed to understand in Radó's proof and that I sought to make explicit above.)