Green's machines
Jump to navigation
Jump to search
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