6 ms·
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.
by emtel 11mo ago
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.
- baruchel 11mo ago> 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.
- henry2023 11mo agoOne of the curiosities about this function is that computing BB(748) is independent of ZFC. https://scottaaronson.blog/?p=4916 https://scottaaronson.blog/?p=4916
- Sniffnoy 11mo agoThe 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.
- red75prime 11mo agoIn other words, Turing machine creates mathematical reality, which is independent from our assumptions.
- emtel 11mo agoNope, 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.
- cwillu 11mo agoNo, 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.
- tromp 11mo agoThe 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 https://oeis.org/A107668 [2] https://oeis.org/A333479 https://oeis.org/A333479 [3] https://en.wikipedia.org/wiki/Graham%27s_number https://en.wikipedia.org/wiki/Graham%27s_number
- Eliezer 11mo agoIt 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.
- tromp 11mo agoThe 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.
- JulianChastain 11mo agoIt 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.
- tromp 11mo agoI 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 https://senseis.xmp.net/?ShodanGoBet
- throwaway81523 11mo ago> best current lower bound Well is there a best current UPPER bound, or at least a "probvious" one?
- cevi 11mo agoThere 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).
- shawnz 11mo agoI 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
- throwaway81523 11mo agoSure, but I only asked about the single case x=6.
- thaumasiotes 11mo agoIf you want an unproven-but-almost-certainly-correct upper bound on BB(6), consider BB(12).
- sligocki 11mo agoNot 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.
- shawnz 11mo agoThe 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