3 ms·
Would a tl;dr here be: Is BB(26) - BB(25) greater than or less than BB(25)?
by scarmig 11y ago
Would a tl;dr here be:
Is BB(26) - BB(25) greater than or less than BB(25)?
- strictnein 11y agoGoogle didn't help me. What's BB(#)?
- betenoire 11y agoBusy Beaver
- startling 11y agoI think people are downvoting you because they're assuming you're not serious. :(
- gresrun 11y agoLink: https://en.wikipedia.org/wiki/Busy_beaver#The_busy_beaver_function_.CE.A3 https://en.wikipedia.org/wiki/Busy_beaver#The_busy_beaver_fu...
- ScottBurson 11y agoFun discussion to be found at: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html
- btilly 11y agoI am certain it is greater. BB(n) grows super-exponentially. In fact I would be willing to bet serious money that BB(n+1)/BB(n) is greater than BB(n) if 3 < n. (This is, of course, assuming that one assumes that BB(n) is well-defined. That is an interesting point of philosophy given the existence of Turing machines which can't be proven to not halt.)
- schoen 11y ago> In fact I would be willing to bet serious money that BB(n+1)/BB(n) is greater than BB(n) if 3 < n. BB(n) grows faster than any computable function. In order for BB(n+1)/BB(n) > BB(n) to hold, BB(n) merely has to grow faster than a sequence whose new terms are obtained by repeated squaring (like k^2ⁿ). That's computable, indeed primitive recursive, so BB(n) definitely grows dramatically faster than it. https://en.wikipedia.org/wiki/Primitive_recursive_function https://en.wikipedia.org/wiki/Primitive_recursive_function Edit: another way of looking at this is that the Ackermann function grows unbelievably faster than functions that easily satisfy the property you describe, and the Busy Beaver function grows unbelievably faster than the Ackermann function. Somehow putting it this way feels like an understatement, though!
- btilly 11y agoIt is unfortunately not that easy. Consider the following function, if n is even then f(n) = BB(n/2), else f(n) = BB(2n). Then f(n) grows faster than any computable function, but still if n is odd, then f(n+1) < f(n). However you have encapsulated the reason why I would be confident of this result. :-)