Green's machines - Revision history

Polygon: Fixed capitalisation in category:Individual machines

2025-12-04T18:13:30Z

Fixed capitalisation in category:Individual machines

← Older revision		Revision as of 18:13, 4 December 2025
Line 66:		Line 66:
	<references />		<references />

	[[Category:Individual ~~Machines~~]]		[[Category:Individual machines]]

Polygon: Added category:individual machines

2025-11-02T19:29:28Z

Added category:individual machines

← Older revision		Revision as of 19:29, 2 November 2025
Line 65:		Line 65:
	== References ==		== References ==
	<references />		<references />

			[[Category:Individual Machines]]

Int-y1: they are not champions 🥀

2025-08-28T08:51:32Z

they are not champions 🥀

← Older revision		Revision as of 08:51, 28 August 2025
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 ==

Int-y1: remove empty column

2025-08-25T08:40:38Z

remove empty column

← Older revision		Revision as of 08:40, 25 August 2025
Line 55:		Line 55:
	\|{{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>
	\|
	\|}		\|}

Polygon: Added :

2025-08-05T12:42:30Z

Added :

← Older revision		Revision as of 12:42, 5 August 2025
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 ==

DF376 at 13:31, 13 August 2024

2024-08-13T13:31:13Z

Sligocki: List of Milton Green's Machines

2024-07-12T02:18:42Z

List of Milton Green's Machines

New page

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 ==
{| class="wikitable"
|+
!# States
!TM
!Sigma Score
|-
|4
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1RD1RA}}
|7
|-
|5
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1RE1RC}}
|13
|-
|6
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1RF1RD}}
|35
|-
|7
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1RG1RE}}
|22,961
|-
|8
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1RH1RF}}
|<math> \frac{7 \cdot 3^{93} - 3}{2} </math>
|-
|9
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1RI1RG}}
|<math> > 3 \uparrow\uparrow 31 </math>
|-
|10
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1RJ1RH}}
|<math> > 3 \uparrow\uparrow 3 \uparrow\uparrow 4 </math>
|-
|11
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1RK1RI}}
|<math> > 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 2 </math>
|-
|12
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1RL1RJ}}
|<math> > 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 4 </math>
|-
|13
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1RM1RK}}
|<math> > 3 \uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow 2 </math>
|-
|14
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1LM1RJ_0LN0LM_1RN1RL}}
|<math> > 3 \uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow 4 </math>
|-
|15
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1LN1RK_0LO0LN_1RO1RM}}
|<math> > 3 \uparrow\uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow\uparrow 2 </math>
|
|}

== External Links ==

* Shawn Ligocki. Green's Machines. 2023. https://www.sligocki.com/2023/10/19/greens-machines.html

== References ==
<references />

← Older revision		Revision as of 13:31, 13 August 2024
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>
	\|		\|