Green's machines: Difference between revisions
Jump to navigation
Jump to search
Added category:individual machines |
→Machines: added scientific notation |
||
| (One intermediate revision by one other user not shown) | |||
| Line 28: | Line 28: | ||
|8 | |8 | ||
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1RH1RF|halt}} | |{{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} > 8.247 \times 10^{44} </math> | ||
|- | |- | ||
|9 | |9 | ||
| Line 66: | Line 66: | ||
<references /> | <references /> | ||
[[Category:Individual | [[Category:Individual machines]] | ||
Latest revision as of 12:21, 25 September 2026
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