# Asymptotic bound to all computable functions lower than the Busy Beaver function

The busy beaver function $BB$ asymptotically bounds any computable function. It is easy to show that there are lower bounds, for example, $log(BB)$.

Is there a function $f$ that asymptotically bounds all computable functions, so that $BB$ is not computable even by a machine with an oracle to $f$? (obviously, $f$ has to be lower than $BB$)

Yes.

The Busy Beaver function has Turing degree $$0'$$: if I know $$BB$$, I can tell whether a given Turing machine will halt.

A function dominating every total computable function, meanwhile, can be constructed by any high Turing degree (this is Martin's domination theorem), and there are high degrees strictly $$<_T0'$$ (this was first proved by Friedberg I believe; Sacks constructed a c.e. high degree below $$0'$$, but that's not needed here).

So how do we build such a function? WARNING: This is pretty technical.

EDIT: To clarify, what's going on below is the construction of an $$f$$ which bounds all computable functions but doesn't compute $$BB$$. This is not the same as a high degree $$<_T0'$$, and indeed that's a bit more complicated to construct - the difference is that the construction below is not actually $$0'$$-effective.

A condition is a pair $$(p, S)$$ where

• $$p$$ is a map from some finite set $$\{0, 1, . . . , n\}$$ to $$\mathbb{N}$$,

• $$S$$ is a finite set of naturals, and

• each $$e\in S$$ is the index of a total computable function.

We say $$(p, S)$$ extends $$(q, T)$$ - and write $$(p, S)\le (q, T)$$ (no, that's not a typo - this notation can seem confusing at first, but there's a good reason for it) - if $$p$$ extends $$q$$, $$S$$ contains $$T$$, and for each $$n\in dom(p)\setminus dom(q)$$ and $$e\in T$$, $$p(n)>\varphi_e(n)$$.

We'll build a sequence of conditions $$(p_i, S_i)$$ such that

• $$(p_0, S_0)\ge(p_1, S_1)\ge(p_2, S_2)\ge...$$,

• $$dom(p_i)\supseteq \{0, 1, . . . , i\}$$, and

• $$e_i\in S_i$$ where $$e_i$$ is the $$i$$th index for a total computable function.

These properties ensure that the function $$f=\bigcup p_i$$ is in fact a function from $$\mathbb{N}$$ to $$\mathbb{N}$$, which dominates all computable functions.

Additionally, we'll ensure that $$\Phi_e^f\not=BB$$ for any $$e$$. This is the tricky part.

We begin the construction with $$p_0=\emptyset$$, $$S_0=\emptyset$$, and proceed inductively. Let's say we've defined $$(p_n, S_n)$$.

Is there some $$k\in\mathbb{N}$$ and some finite map $$q$$ with domain strictly larger than that of $$p_n$$ such that $$(q, S_n)\le (p_n, S_n)$$ but $$\Phi_n^q(k)\downarrow\not=BB(k)$$?
If yes: Let $$p_{n+1}=q$$, $$S_{n+1}=S_n\cup\{t_n\}$$ (where $$\{t_i: i\in\mathbb{N}\}$$ is the set of indices of total computable functions).
If no: Let $$p_{n+1}$$ be any finite partial map such that $$(p_{n+1}, S_n)\le (p_n, S_n)$$, and let $$S_n=S_n\cup\{t_n\}$$.