Green's machines: Difference between revisions
Jump to navigation
Jump to search
(List of Milton Green's Machines) |
(they are not champions 🥀) |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
In 1964, Milton W. Green hand-crafted a family of fast-growing Turing Machines with n-states, 2-symbols for all <math>n \ge 4</math>.<ref>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%2FSWCT.1964.3 https://doi.org/10.1109/SWCT.1964.3]</ref> This family grows roughly as fast as the Ackermann function<math display="block">BB_{2n} \approx 3 \uparrow^{n-2} 3</math> | In 1964, Milton W. Green hand-crafted a family of fast-growing Turing Machines with n-states, 2-symbols for all <math>n \ge 4</math>.<ref>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%2FSWCT.1964.3 https://doi.org/10.1109/SWCT.1964.3]</ref> This family grows roughly as fast as the Ackermann function:<math display="block">BB_{2n} \approx 3 \uparrow^{n-2} 3</math> | ||
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 <math>BB(9) > 10 \uparrow\uparrow 1820</math> and <math>BB(10) > 10 \uparrow\uparrow\uparrow\uparrow\uparrow 4 </math>. | |||
== Machines == | == Machines == | ||
| Line 9: | Line 11: | ||
|- | |- | ||
|4 | |4 | ||
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1RD1RA}} | |{{TM|1LB1RZ_0LC1LC_0LD0LC_1RD1RA|halt}} | ||
|7 | |7 | ||
|- | |- | ||
|5 | |5 | ||
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1RE1RC}} | |{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1RE1RC|halt}} | ||
|13 | |13 | ||
|- | |- | ||
|6 | |6 | ||
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1RF1RD}} | |{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1RF1RD|halt}} | ||
|35 | |35 | ||
|- | |- | ||
|7 | |7 | ||
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1RG1RE}} | |{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1RG1RE|halt}} | ||
|22,961 | |22,961 | ||
|- | |- | ||
|8 | |8 | ||
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1RH1RF}} | |{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1RH1RF|halt}} | ||
|<math> \frac{7 \cdot 3^{93} - 3}{2} </math> | |<math> \frac{7 \cdot 3^{93} - 3}{2} </math> | ||
|- | |- | ||
|9 | |9 | ||
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1RI1RG}} | |{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1RI1RG|halt}} | ||
|<math> > 3 \uparrow\uparrow 31 </math> | |<math> > 3 \uparrow\uparrow 31 </math> | ||
|- | |- | ||
|10 | |10 | ||
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1RJ1RH}} | |{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1RJ1RH|halt}} | ||
|<math> > 3 \uparrow\uparrow 3 \uparrow\uparrow 4 </math> | |<math> > 3 \uparrow\uparrow 3 \uparrow\uparrow 4 </math> | ||
|- | |- | ||
|11 | |11 | ||
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1RK1RI}} | |{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1RK1RI|halt}} | ||
|<math> > 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 2 </math> | |<math> > 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 2 </math> | ||
|- | |- | ||
|12 | |12 | ||
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1RL1RJ}} | |{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1RL1RJ|halt}} | ||
|<math> > 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 4 </math> | |<math> > 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 4 </math> | ||
|- | |- | ||
|13 | |13 | ||
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1RM1RK}} | |{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1RM1RK|halt}} | ||
|<math> > 3 \uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow 2 </math> | |<math> > 3 \uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow 2 </math> | ||
|- | |- | ||
|14 | |14 | ||
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1LM1RJ_0LN0LM_1RN1RL}} | |{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1LM1RJ_0LN0LM_1RN1RL|halt}} | ||
|<math> > 3 \uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow 4 </math> | |<math> > 3 \uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow 4 </math> | ||
|- | |- | ||
|15 | |15 | ||
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1LN1RK_0LO0LN_1RO1RM}} | |{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1LN1RK_0LO0LN_1RO1RM|halt}} | ||
|<math> > 3 \uparrow\uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow\uparrow 2 </math> | |<math> > 3 \uparrow\uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow\uparrow 2 </math> | ||
|} | |} | ||
Latest revision as of 08:51, 28 August 2025
In 1964, Milton W. Green hand-crafted a family of fast-growing Turing Machines with n-states, 2-symbols for all .[1] This family grows roughly as fast as the Ackermann function:
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 and .
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)
|
|
| 9 | 1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1RI1RG (bbch)
|
|
| 10 | 1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1RJ1RH (bbch)
|
|
| 11 | 1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1RK1RI (bbch)
|
|
| 12 | 1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1RL1RJ (bbch)
|
|
| 13 | 1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1RM1RK (bbch)
|
|
| 14 | 1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1LM1RJ_0LN0LM_1RN1RL (bbch)
|
|
| 15 | 1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1LN1RK_0LO0LN_1RO1RM (bbch)
|
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