Do non-computable functions grow asymptotically larger?

Question

I read about busy beaver numbers and how they grow asymptotically larger than any computable function. Why is this so? Is it because of the busy beaver function's non-computability? If so, then do all non-computable functions grow asymptotically larger than computable ones?

Edit:

Great answers below but I would like to explain in plainer english what I understand of them.

If there was a computable function f that grew faster than the busy beaver function, then this means that the busy beaver function is bounded by f. In other words, a turing machine would simply need to run for f(n) many steps to decide the halting problem. Since we know the halting problem is undecidable, our initial presupposition is wrong. Therefore, the busy beaver function grows faster than all computable functions.

Answer 1

If you take any noncomputable set of natural numbers, the characteristic function of the set takes only the values $\{0,1\}$ and is noncomputable. So it is not the case that every noncomputable function grows very quickly, they can even be bounded.

The Busy Beaver function grows more quickly than every computable function because it is constructed to do so. The proof that it is noncomputable proceeds by first proving that it grows faster than any computable function.

More generally, say that a set $A \subseteq \mathbb{N}$ has "hyperimmune-free degree" if every function computable from $A$ is bounded by a computable function. Certainly every computable set has hyperimmune-free degree. It is known that there are also many noncomputable sets that have hyperimmune-free degree. So it is not the case that everything noncomputable will have to compute some fast-growing function.

However, it is also the case that an r.e. set that is noncomputable will not have hyperimmune-free degree. If $B$ is r.e., and enumerated by index $e$, the function $f$ such that $f(n) = k$ if $e$ enumerates $n$ in $k$ steps, and $f(n) = 0$ if $e$ does not enumerate $n$, is computable from $B$ but this function is bounded by a computable function if and only if $B$ is computable.

Answer 2

If a function $f$ grows faster (or slower) than any function in a set $F$ of functions, that is $f \in \omega(g)$ (or $o(g)$) for all functions $g \in F$, then clearly $f \notin F$. This is what is used to show that the busy-beaver function is not computable. Another example is the proof that the -- computable and total -- Ackermann function is not primitive recursive.

The reverse does not necessarily hold. The Halting problem function takes values in $\{0,1\}$ so it is in $O(1)$¹; clearly there are computable functions growing as fast and faster.

There are certainly sets of functions for which runtime is both a necessary and sufficient membership criterion, namely those that are characterised by runtime, such as

$\qquad \displaystyle \mathrm{Poly} = \{f : \mathbb{N} \to \mathbb{N} \mid \exists k.\, f \in O(n^k)\}$.

---

1. That only makes a limited amount of sense. The parameter of the HP function is a Turing machine encoding and a natural number; its size is no measure of how complicated it is to decide halting.