13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Regarding your "plain English" part, where from the answers did you get that? How do you get from a bound on the busy-beaver function to deciding the halting problem in general? Note that deciding halting for any given Turing machine is not uncomputable. $\endgroup$ – Raphael Jul 29 '12 at 21:14
  • $\begingroup$ @Raphael his plain English summary seems correct to me, but not quite complete. The missing detail is that one can reduce deciding if TM $M$ halts on $x$ to deciding if a TM $M'$ halts on the empty tape (hard-wire $x$ into $M'$). Then if $f(n)$ was a computable bound on BB, the algorithm described by OP would solve the halting problem on any $M$ and $x$. $\endgroup$ – Sasho Nikolov Jul 30 '12 at 6:40
14
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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