2023/10/19/greens-machines

[utterances-bot]

Green’s Machines | sligocki

In 1964 (only 2 years after Tibor Radó first described the Busy Beaver game), Milton W. Green of the Stanford Research Institute hand-crafted a family of fast-growing Turing Machines with (n) states, 2 symbols for all (n \ge 4).1 At the time of publication, Green’s Machines were the Busy Beaver champions for (BB(n)) for all (n \ge 6). This family grows roughly as fast as the Ackermann function Milton W. Green. “A Lower Bound on Rado’s Sigma Function for Binary Turing Machines”, Preceedings of the IEEE Fifth Annual Symposium on Switching Circuits Theory and Logical Design, 1964, pages 91–94, doi: 10.1109/SWCT.1964.3. ↩

https://www.sligocki.com//2023/10/19/greens-machines.html

[nickdrozd]

I can confirm independently that Green-9 halts in ~10↑↑30 steps.

I can't verify the Green-10 result, although I can confirm that if it does halt, it does so in a spectacular number of steps. My simulator can run exponential rules, but not an exponential number of times. If that occurs, there is a line that raises an emergency stop. Green-10 is the first program I've encountered that actually triggered that stop. So as a result of this post, my test coverage is improved!

To clarify, Green-10 is spectacular only with respect to existing BB results. With respect to the "true" BB values, Green's machines are absolutely pitiful, as will be any constructed solution. It is entirely possible that BB(6, 2) already exceeds Green-10.

[sligocki]

@Iijil from Discord just shared this page in which Wythagoras (of BB(7) fame) claims better bounds for 13-15 states: https://googology.fandom.com/wiki/User:Wythagoras/Rado's_sigma_function#Bounds_for_%5C(%5CSigma(n,2)%5C)_and_%5C(S(n,2)%5C) Specifically:

• Sigma(13) > 3 ↑^{2046} 3
• Sigma(14) > 3 ↑^{10 ↑ 18267} 3
• Sigma(15) > 3 ↑^{10 ↑↑ 5 [↑ 7]} 3

[Iijil1]

there is a 12 state encoding of 1RB1RZ1LA2RB_1RC3RC1LA2LB_2LB2RC1LC3RB, the Ack(11) TM found by Pavel mentioned in this comment.

The encoding is 1RB1LL_0RC1RC_1LD1LG_0RE1LC_1LD1RF_1RE1RI_1RH0LA_---0RF_0RB1LJ_---0LK_0LF1LF_1RZ0LA and shows that Sigma(12) > 2{12}4 > Ack(11).