Problem Detail: 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.
Asked By : hollow7
Answered By : Carl Mummert
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2939
