Green's machines: Difference between revisions
Jump to navigation
Jump to search
Added : |
→Machines: added scientific notation |
||
| (4 intermediate revisions by 2 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 26: | 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 55: | Line 57: | ||
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1LN1RK_0LO0LN_1RO1RM|halt}} | |{{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> | ||
|} | |} | ||
| Line 64: | Line 65: | ||
== References == | == References == | ||
<references /> | <references /> | ||
[[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