Green's machines: Difference between revisions
Jump to navigation
Jump to search
(List of Milton Green's Machines) |
No edit summary |
||
| Line 9: | Line 9: | ||
|- | |- | ||
|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> | ||
| | | | ||
Revision as of 13:31, 13 August 2024
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