←back to thread

BusyBeaver(6) Is Quite Large

(scottaaronson.blog)
271 points bdr | 2 comments | | HN request time: 0.001s | source
Show context
tromp ◴[] No.44407552[source]
People on the bbchallenge Discord server are keen to speculate on how many Turing Machine states are needed to surpass Graham's Number, which is vastly larger than the 2^^2^^2^^9 achieved by the latest BB(6) champion.

We know from the functional busy beaver [1] that Graham behaviour can come surprisingly early; a 49-bit lambda term suffices. There are only 77519927606 closed lambda terms of at most that size [2], compared to 4^12*23836540=399910780272640 unique 6-state Turing Machines [3].

With the achievement of pentation in only 6 states, several people now believe that 7 states should suffice to surpass Graham's. I would still find that rather surprising. A few days ago, I made a large bet with one of them on whether we would see proof of BB(7)>Graham's within the next 10 years.

What do people here think?

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

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

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

replies(1): >>44407834 #
gpm ◴[] No.44407834[source]
I can't pretend to be an expert, but I'll argue BB(7) is probably larger than Graham's number.

BB has to grow faster than any computable sequence. What exactly that means concretely for BB(7) is... nothing other than handwaving... but it sort of means it needs to walk up the "operator strength" ladder very quickly... it eventually needs to grow faster than any computable operator we define (including, for example, up-arrow^n, and up-arrow^f(n) for any computable f).

My gut feeling is that the growth between 47 million and 2^^2^^2^^9 is qualitatively larger than the growth between 2^^2^^2^^9 and graham's number in terms of how strong the operator we need is (with gramah's number being g_64 and g here being roughly one step "above" up_arrow^n). So probably we should have BB(7)>Graham's number.

replies(2): >>44409272 #>>44411034 #
1. pinkmuffinere ◴[] No.44411034[source]
I can’t edit my original comment anymore, but replying to say I went on a Wikipedia binge and I think you’re right. Thanks for humoring me and helping me learn!
replies(1): >>44412802 #
2. gpm ◴[] No.44412802[source]
:)