The Busy Beaver Problem

You're viewing a comment by Peteris Krumins and its responses.

October 29, 2009, 16:08

Michael Richardson: Brian 2 is right -- Busy Beaver bb(n) grows faster than Ackermann or any other computable function f(n).

Reply to this comment

Comment 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
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

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.