2022/07/11/bb-16-graham

[utterances-bot]

BB(16) > Graham’s Number | sligocki

Almost exactly 12 years ago, I wrote an article1 describing an idea on how to hand-build a a Turing Machine which runs for more steps than Graham’s number (g{64}) (A famously huge number). Doing so would give a constructive upper bound to the (N) such that (BB(N) > g{64}) and perhaps provide a little more intuition on how the Busy Beaver function grows. The original article was actually posted on my Wikipedia User page of all places! And, honestly, that location has served me well. That article has been preserved and is still available 12 years later, at no cost, ad free and even with a detailed change history! That said, I did recently copy it to this blog. ↩

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

[alreadydone]

Great analysis! Minor typo: Correlary -> Corollary

[alreadydone]

There's a small disagreement: Nagaj said "Ackermann growth with 9 states" in the announcement but you says 10 states. What's happening here? I also found "Ackermannian growth using 8 states" on Wythagoras's page (September 2016); could it be plugged in here to reduce 16 to 15? Wythagoras claimed $\Sigma(15)>\{3,3,10^{10^{10^{10^{18705352}}}}\}$ but I don't know what notation that is and how it compares to Graham's.

[sligocki]

There's a small disagreement: Nagaj said "Ackermann growth with 9 states" in the announcement but you says 10 states. What's happening here?

Yeah, the exact number here is a bit subjective. It basically depends on the precise way that you choose to split this TM into modules. I guess that looking at my 10 state Ackerman component, clearly two of those states could be combined (A12 and A5). My intention here wasn't to say that 10 states in the minimum for Ackermann growth! Instead it was to say that this 10 state machine has very precisely defined Ackermann growth :)

I also found "Ackermannian growth using 8 states" on Wythagoras's page (September 2016); could it be plugged in here to reduce 16 to 15?

Maybe, but probably not. In order to be able to "plug it in" you would need to prove that Wythagoras's 8 state TM has exactly the behavior described by "Rule D" and "Rule A". I'm guessing that it does not have exactly this behavior, but instead some closely related (but different) behavior. If that's the case, you need to see if you can build the following components on top of that different specification.

This is the annoying thing about programming in Turing Machines and the reason people call it a Turing Tarpit, heh.

[alreadydone]

Thanks for the answers! 🎉