[tromp]

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

[gpm]

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.

[pinkmuffinere]

Apologies if this feels adversarial, but I think your informal proof has an error, and I think I can explain it!

Your proof rests primarily on this assertion:

> BB has to grow faster than any computable sequence.

This is almost true! BB(n) has to grow faster than any computable sequence _defined by an n-state Turing machine_. That last part is really important. (Note that my restatement is probably incorrect too, it is just correct enough to point out the important flaw I saw in your statement). This means that up-arrow^f(n) _can_ be larger than BB(n) — up-arrow^f(n) is not restricted by a Turing machine at all. As an easy example, consider f(n) = BB(n)^2.

You may still be right about BB(7) being bigger than Graham’s number, even if your proof is not bulletproof

[btilly]

No, the original was correct.

Any computable sequence S(n) must be computed by a specific finite program of fixed length.

Once n gets big enough, BB(n) will include the function S(2^n), and therefore will exceed that computable sequence.

Given computable sequences may exceed BB(n) for a finite number of terms. But eventually BB(n) will outgrow them, and will never look back.

[pinkmuffinere]

Just replying to say you’re right! Thanks!

[gpm]

Math's a cooperative endeavor, I want to know if I'm wrong!

I'm not sure I understand the distinction you're trying to make though, and I'm not sure it's right...

The argument that BB has to grow faster than any computable sequence is that if we have a computable f(n) where for all n f(n) > BB(n) then we can solve the halting problem by simulating turing machines of size n for f(n) steps and checking if they halt. Even if we can't prove f(n) > BB(n) the mere existence of this f would mean we could solve the halting problem (even though we couldn't prove we had done so).

I agree my "proof" (intuition really) rests on that assertion.

> As an easy example, consider f(n) = BB(n)^2.

This, like BB(n), isn't computable?

[pinkmuffinere]

Thanks for the good attitude!

Ah, I didn't realize 'computable' had a specific meaning in this domain -- showing the limits of my experience a bit. After looking at the wikipedia page and rereading your sketch, I think it is true that

> it eventually needs to grow faster than any computable operator we define

I'm not sure if this has implications about how quickly BB() grows compared to the "operator strength" ladder though? It's familiar/convenient to refer to tetration, pentation, etc as f() for convenience, but this is just notational -- not related to computability. When comparing BB(n) and tetration(n), pentation(n), etc(n), I don't think there is really anything that can be said 'easily' about which values are larger. BB(n) will be larger than anything that can be computed in n steps. But pentation(n) is not necessarily computable in n steps, it may take much more. We may find pentation(n) > BB(n) for all n greater than some threshold. I might be misunderstanding a logical step here though that connects them?

[throwaway81523]

> We may find pentation(n) > BB(n) for all n greater than some threshold.

No, that is impossible. Tetration, pentation, etc. are all computable sequences and BB grows faster than any computable sequence. So you have the > sign where you really want a < sign.

[meindnoch]

>BB(n) will be larger than anything that can be computed in n steps

Who said anything about "n steps"?

BB(n) is about an n-state Turing machine, not "n steps".

[adgjlsfhk1]

one of the things that does come out of BB is that BB(n)^2>>BB(n+c) for some very small constant c (I would be surprised if c>2)

[pinkmuffinere]

Sure, but the example I'm providing is just meant to illustrate that BB(n) is not greater than arbitrary f(n). I'm not trying to provide the biggest number, I'm trying to illustrate that the sketched-out proof is incorrect. If you want me to provide a bigger number, I suppose another easy example is to define f(n) = BB(BB(n)).

Edit: Oh sorry, I see I misread the direction of your greater than signs. Leaving comments as-is though, hopefully that results in the least confusion

[adgjlsfhk1]

oops, my greater than signs are in the wrong direction. specifically, for any computable function f, there exists some constant c such that f(BB(n))<<BB(n+c)

[pinkmuffinere]

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!

[gpm]

:)