-1
$\begingroup$

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

$\endgroup$
0

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.