Green's machines

In 1964, Milton W. Green hand-crafted a family of fast-growing Turing Machines with n-states, 2-symbols for all $n\geq 4$ .^[1] This family grows roughly as fast as the Ackermann function:

BB_{2n}\approx 3\uparrow ^{n-2}3

Over the years, these Turing Machines lost champion status. The last machines to lose champion status were BB(9), BB(10), and BB(11). In August 2024, Racheline discovered the better bounds $BB(9)>10\uparrow \uparrow 1820$ and $BB(10)>10\uparrow \uparrow \uparrow \uparrow \uparrow 4$ .

Machines


# States	TM	Sigma Score
4	`1LB1RZ_0LC1LC_0LD0LC_1RD1RA` (bbch)	7
5	`1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1RE1RC` (bbch)	13
6	`1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1RF1RD` (bbch)	35
7	`1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1RG1RE` (bbch)	22,961
8	`1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1RH1RF` (bbch)	${\frac {7\cdot 3^{93}-3}{2}}$
9	`1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1RI1RG` (bbch)	$>3\uparrow \uparrow 31$
10	`1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1RJ1RH` (bbch)	$>3\uparrow \uparrow 3\uparrow \uparrow 4$
11	`1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1RK1RI` (bbch)	$>3\uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow 2$
12	`1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1RL1RJ` (bbch)	$>3\uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow 4$
13	`1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1RM1RK` (bbch)	$>3\uparrow \uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow \uparrow 2$
14	`1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1LM1RJ_0LN0LM_1RN1RL` (bbch)	$>3\uparrow \uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow \uparrow 4$
15	`1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1LN1RK_0LO0LN_1RO1RM` (bbch)	$>3\uparrow \uparrow \uparrow \uparrow \uparrow 3\uparrow \uparrow \uparrow \uparrow \uparrow 2$

External Links

Shawn Ligocki. Green's Machines. 2023. https://www.sligocki.com/2023/10/19/greens-machines.html

References

↑ Milton W. Green. “A Lower Bound on Rado’s Sigma Function for Binary Turing Machines”, Proceedings of the IEEE Fifth Annual Symposium on Switching Circuits Theory and Logical Design, 1964, pages 91–94, https://doi.org/10.1109/SWCT.1964.3

[1] Milton W. Green. “A Lower Bound on Rado’s Sigma Function for Binary Turing Machines”, Proceedings of the IEEE Fifth Annual Symposium on Switching Circuits Theory and Logical Design, 1964, pages 91–94, https://doi.org/10.1109/SWCT.1964.3

[1]

Green's machines

Machines

External Links

References

Navigation menu