
> 
> Do all non-computable functions grow faster than computable functions?
> 
> 
> 


In [*Does the Busy Beaver function grow faster than the Tree function?*](https://www.quora.com/Does-the-Busy-Beaver-function-grow-faster-than-the-Tree-function), the informal proof hinges on non-computable functions such as Busy Beaver growing faster than computable ones such as TREE. *Is this necessarily given?* For example, a trivially non-computable function which grows slower than TREE would be the sum of reciprocals of Busy Beaver: $$\sum\_{i=1}^n\frac{1}{BB(n)}$$



Do all non-computable functions grow faster than computable functions?
Your example gives a counterexample to your question, if you allow real-valued functions. Another is $f$ defined by $f(n)=0$ if the $n$th Turing machine halts, else $f(n)=1$. The key thing about Busy Beaver isn't just that it's noncomputable, it's that it gives an upper bound on how long a terminating Turing machine can run, and thus on the size of any computable function. There are lots of other noncomputable functions out there that don't do this.


