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$)
 A: 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)$. 
Now we ask:

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\}$.
It's now a fun exercise to show that this works! HINT: in the "no" case, it looks like we're essentially doing nothing at all. That's correct! Think about why this isn't going to be a problem . . .
