The best current lower bound for BB(6) is 2↑↑2↑↑2↑↑9 (google "Knuth Up Arrow" if this makes no sense), a number so inconceivably large it gives me the willies.
In particular, this means that in going from BB(5) to BB(6), you have already crossed the line where the actual busy beaver TM can no longer be simulated step by step in the lifetime of our universe (or a googol lifetimes of our universe for that matter).
It really is mind bending how fast this function grows.
The record's been lowered since then, I should note. At least down into the 600s, I've seen claims of down in the 400s. But I haven't really kept up with this.
No, that's a misconception. If you add BB(748)==‹any N but the correct number›, you get an inconsistent system that will either claim that a machine doesn't halt even though it does (e.g. the real BB champion), or that some machine does halt at N steps, which you can then disprove by enumerating all the turing machines of the relevant number of states for N steps, and showing that no machine halts at that step.
Either way, the only BB axiom you can add without blowing up ZFC is the correct one.
Nope, that’s the crazy thing. busy beaver numbers are simple arithmetical constructions. There is a fact of the matter about each value of BB(n)! We just can’t ever know more than a small handful of them.
The BB function does grow mind bendingly fast. The machine running for 2↑↑2↑↑2↑↑9 steps is one of the 4^12*23836540 = 399910780272640 differently behaving 6-state machines [1].
A similarly fast growing function is the functional busy beaver [3]. Among all 77519927606 closed lambda terms of size <= 49 bits, there is one whose normal form size exceeds the vastly larger Graham's Number [3].
Several beaver fans believe that BB(7) might exceed Graham's Number as well, which struck me as unlikely enough to offer a $1k bet against it, the outcome of which will be known in under a decade.
It would not surprise me at all for bb7 to exceed Graham's number. Just a Kirby-Paris hydra or a Goodstein sequence gets you to epsilon zero in the fast-growing hierarchy, where Graham is around omega+2.
The 79-bit lambda term λ1(λλ2(λλ3(λ312))(1(λ1)))(λλ1)(λλ211)1 in de-Bruijn notation exhibits f_ε0 growth without all the complexities of computing Kirby-Paris hydra or Goodstein sequences. Even that is over 60% larger than the 49-bit Graham exceeder (λ11)(λ1(1(λλ12(λλ2(21))))). I think one should be quite surprised if you can climb from f_4 (2↑↑2↑↑2↑↑9) to f_{ω+1} (Graham) with just 1 additional state.
I do not predict that. We just need the bet to have a time limit because BB(7) will always have holdouts as long as I live. I chose 10 years because I have prior experience with that timeframe [1].
> It really is mind bending how fast this function grows.
While the BB function is obviously a well-defined function over the integers, I find it helpful to think of it as a function over qualitatively heterogeneous items—such as stones, bread toasters, mechanical watches, and computers. The key idea is to view the underlying computing devices not as “a little more powerful” than the previous ones, but as fundamentally different kinds of entities.
I think finding an upper bound is basically just as difficult as finding the actual value itself, since both would require proving that all of the programs which run longer than that will run forever. That's why we can say BB(x) grows faster than any computable function. Being able to compute BB(x) algorithmically or any faster growing function would let you solve the halting problem
The point stands: the hard part is proving that all the programs with longer runtime than your upper bound will never terminate, and once you've solved that, getting the exact value is just a little extra work
Not sure if this is a joke, but actually that is guaranteed to be true. It is proven that for all n: BB(n+1) >= BB(n) + 3. But it is not proven that BB(n+1) >= BB(n) + 4, haha.
There is of course not currently any upper bound on BB(6).
I find the question about a probvious upper bound more interesting - There is also not a probvious upper bound on BB(6), as this would require at least some understanding of the high-level behavior of all remaining holdout machines. However, there may soon be a 'probvious' upper bound on the value of BB(3,3) (BB for 3-state, 3-symbol machines). Up to equivalence, there are four remaining machines to decide to find the value of BB(3,3). One is a 'probviously halting' machine which will be the new champion if it halts, and for which probabilistic models of its behavior predict with high probability an exact halting time. One is a 'probviously nonhalting' machine. The two other machines are not well-understood enough to say whether they have any probvious long term behavior, but some suspect that they both 'probviously nonhalt'. If this is true it could be said that a 'probvious' upper bound exists for BB(3,3).
There is no general procedure for computing upper bounds on busy beaver numbers (this can be proven). We haven't even come close to enumerating all of the interesting six-state Turing machines, so right now we don't even have a wild guess for an upper bound on BB(6).
In particular, this means that in going from BB(5) to BB(6), you have already crossed the line where the actual busy beaver TM can no longer be simulated step by step in the lifetime of our universe (or a googol lifetimes of our universe for that matter).
It really is mind bending how fast this function grows.