News for hackers. Stuff that matters.
Re:Why Busy Beaver hunters fear the Antihydra by emtel on Monday October 27, 2025 @04:29PM (#45725906)
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.

Re:Why Busy Beaver hunters fear the Antihydra by henry2023 on Monday October 27, 2025 @06:14PM (#45726966)
One of the curiosities about this function is that computing BB(748) is independent of ZFC.

https://scottaaronson.blog/?p=4916

Re:Why Busy Beaver hunters fear the Antihydra by Sniffnoy on Monday October 27, 2025 @09:22PM (#45728322)
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.
Re:Why Busy Beaver hunters fear the Antihydra by srcreigh on Monday October 27, 2025 @11:57PM (#45729078)
Any links?
Re:Why Busy Beaver hunters fear the Antihydra by Sniffnoy on Tuesday October 28, 2025 @07:29PM (#45740686)
Thank you!
Re:Why Busy Beaver hunters fear the Antihydra by red75prime on Tuesday October 28, 2025 @01:02AM (#45729346)
In other words, Turing machine creates mathematical reality, which is independent from our assumptions.
Re:Why Busy Beaver hunters fear the Antihydra by cwillu on Tuesday October 28, 2025 @06:58AM (#45731288)
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.

Re:Why Busy Beaver hunters fear the Antihydra by emtel on Tuesday October 28, 2025 @04:11PM (#45738460)
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.
Re:Why Busy Beaver hunters fear the Antihydra by tromp on Monday October 27, 2025 @06:43PM (#45727203)
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.

[1] https://oeis.org/A107668

[2] https://oeis.org/A333479

[3] https://en.wikipedia.org/wiki/Graham%27s_number

Re:Why Busy Beaver hunters fear the Antihydra by Eliezer on Tuesday October 28, 2025 @02:59AM (#45729870)
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.
Re:Why Busy Beaver hunters fear the Antihydra by tromp on Tuesday October 28, 2025 @03:35AM (#45730057)
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.
Re:Why Busy Beaver hunters fear the Antihydra by JulianChastain on Tuesday October 28, 2025 @11:06AM (#45733804)
It seems totally inconceivable to me that you could accurately predict how long until we will know whether BB(7) is greater than Graham's Number.
Re:Why Busy Beaver hunters fear the Antihydra by tromp on Tuesday October 28, 2025 @11:39AM (#45734293)
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].

[1] https://senseis.xmp.net/?ShodanGoBet

Re:Why Busy Beaver hunters fear the Antihydra by baruchel on Monday October 27, 2025 @05:08PM (#45726324)
> 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.

Re:Why Busy Beaver hunters fear the Antihydra by throwaway81523 on Monday October 27, 2025 @07:44PM (#45727694)
> best current lower bound

Well is there a best current UPPER bound, or at least a "probvious" one?

Re:Why Busy Beaver hunters fear the Antihydra by cevi on Monday October 27, 2025 @08:29PM (#45728010)
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).
Re:Why Busy Beaver hunters fear the Antihydra by shawnz on Monday October 27, 2025 @08:30PM (#45728022)
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
Re:Why Busy Beaver hunters fear the Antihydra by throwaway81523 on Tuesday October 28, 2025 @02:08AM (#45729646)
Sure, but I only asked about the single case x=6.
Re:Why Busy Beaver hunters fear the Antihydra by thaumasiotes on Tuesday October 28, 2025 @06:32AM (#45731133)
If you want an unproven-but-almost-certainly-correct upper bound on BB(6), consider BB(12).
Re:Why Busy Beaver hunters fear the Antihydra by sligocki on Tuesday October 28, 2025 @04:46PM (#45738920)
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.
Re:Why Busy Beaver hunters fear the Antihydra by shawnz on Tuesday October 28, 2025 @08:48AM (#45732156)
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
Re:Why Busy Beaver hunters fear the Antihydra by throwaway81523 on Thursday October 30, 2025 @06:07PM (#45765970)
For arbitrary n, that proof is arbitrarily hard, even undecidable for large enough n. Again though, for the specific case n=6, that difficulty has not yet been demonstrated, especially if you're willing to accept probabilistic arguments instead of rigorous proofs. n-by-n checkers is PSPACE-complete but the specific case n=8 that people actually play, has been completely solved using computers.
Re:Why Busy Beaver hunters fear the Antihydra by chtl on Tuesday October 28, 2025 @05:40PM (#45739599)
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).