BB(16) > Graham's number

[Shawn Ligocki]

This is not a new discovery, several users on the Googology forum have been claiming smaller and smaller TMs which surpass Graham's number for almost a decade now. But the amount of justification is generally pretty limited. I decided to analyze the most recent claim, by Daniel Nagaj in 2021, that BB(16) > Graham's number and my conclusion is that it appears legitimate. I've written up my analysis here:

https://www.sligocki.com/2022/07/11/bb-16-graham.html

How low can this bound go? Obviously this TM is quite structured, so presumably the first TM to beat Graham is much smaller. BB(12), BB(8), BB(6)? But we have a long way to go to be able to analyze such a machine which was not written by a human :)

-Shawn

[Nicholas Drozd]

I think it's entirely possible already that G < BB(6). G is a huge number of course, but it isn't really descriptively complex. You start with up-arrow notation, and then the Graham function is just recursive composition of arrows. Okay, we can't actually compute these numbers, but you could imagine doing it if you had enough time and space. It just doesn't seem all that complicated.

Thanks to Pavel, we now know that BB(6) can do up-arrow stuff. Can BB(6) also do recursive composition of arrows? That's kind of a puny technique in the grand scheme of things, so I don't see why not.

Obviously there is a lot of hand-waving here and this is not a proof. But historically the concrete values of BB have been underestimated over and over and over, to the point where I assume that any estimate must be wrong.

Just consider the logical status of the claim that G > BB(6). To say this is to say that every single 6-state halting machine halts in fewer than G steps. That's quite a bold claim! And one that nobody is even remotely close to being able to prove. So I think it's reasonable to assume BB(6) > G as a live possibility until it can be proved otherwise.