2022/07/11/bb-16-graham about sligocki.github.io HOT 4 OPEN

Great analysis! Minor typo: Correlary -> Corollary

from sligocki.github.io.

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.

from sligocki.github.io.

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.

from sligocki.github.io.

Thanks for the answers! 🎉

from sligocki.github.io.