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

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

In 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)}$$

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.
Let $$f(x)=1$$ if we can write $$x=2^a3^b$$ where $$BB(a)=b$$, and $$f(x)=0$$ otherwise. This $$f$$ is also noncomputable, and takes values only in $$\{0,1\}$$.