The Busy Beaver Problem

You're viewing a comment by Bill Carson and its responses.

Bill Carson Permalink
November 23, 2011, 22:30

Wrong! There is no evidence to conclude that the Ackermann function is slower growing than the Busy Beaver Sigma.
The fact that a function is not computable doesn't necessarily mean it needs to be fast growing (e.g. convert the halting problem to a function that returns a boolean: not very fast growing, is it?)

Reply to this comment

Comment Responses

November 25, 2011, 23:08

Ackermann function is a computable function and for any computable function f(BBSigma(n)) < BBSigma(n+1).

Reply to this comment
Thomas Permalink
March 07, 2012, 14:20

Bill is right about there being no evidence that the Ackermann function grows slower than a non-computable function in general, but for the busy beaver function there is a proof that it grows faster than any computable function. See the wikipedia article for a proof.

Reply to this comment

Reply To This Comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Comment Help

Type first 3 letters of your name: (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.