Green's machines: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
(Added :) |
||
| 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> | ||
== Machines == | == Machines == | ||
Latest revision as of 12:42, 5 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:
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