In 1964 (only 2 years after Tibor Radó first described the Busy Beaver game), Milton W. Green of the Stanford Research Institute hand-crafted a family of fast-growing Turing Machines with n states, 2 symbols for all n4.1 At the time of publication, Green’s Machines were the Busy Beaver champions for BB(n) for all n6. This family grows roughly as fast as the Ackermann function

BB2n3n23

and (as far as I can tell) some of them have not been beaten to this day.

Green’s Machines are still referenced often in discussion about Busy Beavers. However, I have not seen much discussion about the machines themselves. Even reading the original paper is a bit of a challenge. In it Green defines 4 different families of Turing Machines (MN,GN,BN,BBN) and I find the subtleties of how each is defined and extended to the other families to be quite confusing every time I read it. In order to support more widespread understanding of the details of Green’s constructions, this post will describe Green’s Machines and their scores in modern notation.

Note: I use names in this article that are adapted from Green’s names, but are not quite identical. The difference is somewhat subtle.

The Machines

The Green Machines are made up of two components, split up by states. These components will be a setup component Sk and a compute component Gn.

G Component

The main workhorse is the Gn component. For every odd n, Gn defined by the transition table:

State 0 1
Qn 1LTn 1RQn+2
Tn 0LQn2 0LTn
Qk 1LTk 1RQk+2
Tk 0LQk2 0LTk
Q1 1RQ1 1RQ3

Where the Qk,Tk are defined this way for all odd 3kn.

This component has a single entry state (Qn) which the setup component should transition into when it wants to run the Gn component and a single exit state (Qn+2) which the component will transition out to when it is done with it’s computation.

These compute a series of fast-growing functions Gn(k) that I will describe in detail below.

Setup Components

There are two different setup components S3 and S4 (with 3 and 4 states respectively). Either can be added to any Gn component in order to make a Green Machine of either even or odd number of states (respectively).

Three-State Setup

The S3 component is defined by:

State 0 1
A=Qn+2 1LB 1RZ
B 0LT 1LT
T 0LQn 0LT

where Qn is the entry state and A=Qn+2 is the exit state of the Gn component.

When attached to G2k+1, this produces an even state BB2k+4 Green Machine (with start state A and halt state Z).

Four-State Setup

The S4 component is defined by:

State 0 1
A 1LT 1LB
B 1LZ 1LA
C=Qn+2 0LB 1LT
T 0LQn 0LT

where Qn is the entry state and C=Qn+2 is the exit state of the Gn component.

which, when attached to G2k+1, this produces an odd state BB2k+5 Green Machine (with start state A and halt state Z).

Example Machines

Putting this all together and converting into Standard Text format we get for example:

  • BB7: 1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1RG1RE (on bbchallenge)
  • BB8: 1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1RH1RF (on bbchallenge)
  • BB9: 1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1RI1RG (on bbchallenge)
  • BB10: 1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1RJ1RH (on bbchallenge)

Note:

  1. I have not normalized these to TNF. Instead I’ve left them with the same directions and state order as Green described them for ease of comparison.
  2. I am using state Z in all of these as the halt state. H is not a halt state, but instead the 8th state.

Class G Machines

In order to motivate the Gn component, Green defines a general specification for TMs: Class G Machines. A TM, M, as a Class G Machine (with entry state Min and exit state Mout) if it conforms to the following behavioral specification:

01kMin>001mMin>Min>11Mout>

In words:

  • When started in its entry state (Min) on a 0
    • with a string on k0 1s to its left (and nothing else),
    • it performs some computation without ever traveling to the right of the initial location
    • until it eventually leaves to the right in the same state (Min)
    • with a string 1s to its left (and nothing else).
  • When started in its entry state (Min) on a 1,
    • it moves immediately to the right and enters the exit state (Mout).

We will say that M computes the function M(k)=m.

Recurrence

Note: An immediate consequence of the above specification is that:

01kMin>0r101Mr(k)+1Mout>

G Components

Each Gn component is a Class G Machine (with entry state Qn and exit state Qn+2). We can see this via induction.

Base Case

We can see directly that G1

State 0 1
Q1 1RQ1 1RQ3

is a Class G Machine (with entry state Q1, exit state Q3) which computes the function:

G1(k)=k+1

Inductive Step

We can build Gn by simply adding two states to Gn2:

State 0 1
Qn 1LTn 1RQn+2
Tn 0LQn2 0LTn

Now, assuming that Gn2 is a Class G Machine (with entry state Qn2, exit state Qn), we will prove that Gn is a Class G Machine (with entry state Qn, exit state Qn+2):

First, the easy part:

Qn>11Qn+2>

in a single step.

Second, we will use the inductive assumption which tells us that

01kQn2>0r101Gn2r(k)+1Qn>

in order to prove:

01kQn>001k<Tn10<Tn0k10<Qn20k+11=0Qn2>0k+2101Gn2k+2(0)+1Qn>

thus proving that Gn is a Class G Machine and also that

Gn(k)=Gn2k+2(0)+1

Fast-growing Hierarchy

Thus we can see that Gn are all Class G Machines which compute a fast-growing hierarchy of functions. The sequence begins with:

  # States Function
G1 1 G1(k)=k+1
G3 3 G3(k)=G1k+2(0)+1=k+3
G5 5 G5(k)=G3k+2(0)+1=3k+7
G7 7 G7(k)=G5k+2(0)+1=73k+252>3k
G9 9 G9(k)=G7k+2(0)+1>3↑↑k

Setup Components

While the sequence of Gn machines above compute impressively large functions, they need a little help when starting from a blank tape. This is where the Setup Components S3 and S4 come in. These setup components are very clever, they find a way to efficiently use the Gn components to initialize the tape for themselves.

Three-State Setup

Starting from any Gn, we can produce the n+3 state Green Machine BBn+3 by adding the S3 component:

State 0 1
A=Qn+2 1LB 1RZ
B 0LT 1LT
T 0LQn 0LT

Then we can see, that, starting in state A on a blank tape we get the trajectory:

0<A00<Qn0010=0Qn>0001001Gn3(0)+1Qn+2>001Gn3(0)+1<B1001Gn3(0)<T1100<T0Gn3(0)1100<Qn0Gn3(0)+1110=0Qn>0Gn3(0)+211001GnGn3(0)+2(0)+1Qn+2>1001GnGn3(0)+2(0)+2Z>0

Which halts with exactly BBn+3=GnGn3(0)+2(0)+2 1s on the tape (this TMs “score”).

Note that:

Gn+2(k)=Gnk+2(0)+1

so we can rewrite these scores as

BBn+3=GnGn3(0)+2(0)+2=GnGn+2(1)+1(0)+2=Gn+2(Gn+2(1)1)+1

Four-State Setup

Starting from any Gn, we can produce the n+4 state Green Machine BBn+4 by adding the S4 component:

State 0 1
A 1LT 1LB
B 1LZ 1LA
C=Qn+2 0LB 1LT
T 0LQn 0LT

Prerequisites

This setup is more subtle to prove. It actually depends upon the fact that Gn(k) is a “parity swapping function”, in other words that:

Gn(2k)1(mod2)Gn(2k+1)0(mod2)

This turns out to be true for all Gn(k) (which can be proven easily by induction).

Specifically, we use this fact below in the following transitions:

1Gn+2(0)<B<A1Gn+2(0)1Gn+2Gn+2(0)(Gn+2(0))<B<B1Gn+2Gn+2(0)(Gn+2(0))

Since Gn+2(0) is odd and Gn+2Gn+2(0)(Gn+2(0)) is even.

We also need to prove a general rule first:

01kC>101k<T10<T0k10<Qn0k+11=0Qn>0k+2101Gnk+2(0)+1Qn+2>=01Gn+2(k)C>

Applying this recursively we get:

01kC>1r01Gn+2r(k)C>

Behavior

Finally, we can see, that, starting this TM in state A on a blank tape we get the trajectory:

0<A00<Qn010=0Qn>001001Gn+2(0)C>001Gn+2(0)<B00<A1Gn+2(0)00<Qn01Gn+2(0)+10=0Qn>001Gn+2(0)+1001Gn+2(0)C>1Gn+2(0)001Gn+2Gn+2(0)(Gn+2(0))C>001Gn+2Gn+2(0)(Gn+2(0))<B00<B1Gn+2Gn+2(0)(Gn+2(0))00<Z1Gn+2Gn+2(0)(Gn+2(0))+10

Which halts with exactly BBn+4=Gn+2Gn+2(0)(Gn+2(0))+1 1s on the tape (this TMs “score”).

Once again, we can simplify:

BBn+4=Gn+2Gn+2(0)(Gn+2(0))+1=Gn+2Gn+2(0)+1(0)+1=Gn+4(Gn+2(0)1)

Summary

Putting this all together, Green defined components Gn which compute a fast growing hierarchy of functions and two different setup components S3 and S4 which can be added on top in order to produce a sequence of TMs BBn which start on a blank tape and leave large numbers of 1s upon halting. Precisely,

G1(k)=k+1Gn(k)=Gn2k+2(0)+1BB2n=G2n1(G2n1(1)1)+1BB2n+1=G2n+1(G2n1(0)1)

Values and Bounds

We can compute the following exact values and (reasonably tight) bounds using Knuth up-arrow notation:

G1(k)=k+1G1(0)=1G1(1)=2G3(k)=k+3G3(0)=3G3(1)=4G5(k)=3k+7G5(0)=7G5(1)=10G7(k)=73k+252>3k+3G7(0)=29G7(1)=92G9(k)>3↑↑(k+3)G9(0)=733132G11(k)>3↑↑↑(k+3)G2n+5(k)>3n(k+3)

And similarly for BBn values:

BB4=7BB5=13BB6=35BB7=22961>39=332BB8=739332>394>334BB9=G9(28)>3↑↑31>3↑↑3↑↑2BB10>G9(3↑↑4)>3↑↑3↑↑4BB2n+5>G2n+5(3n13)>3n(3n13)=3n3n2BB2n+6>G2n+5(3n4)>3n3n4

Green’s Champions

Update: As of 13 May 2025, none of Green’s machines remain champions due to Pavel Kropitz’s discovery of an Ackermann-level BB(7) TM demonstrating Σ(7)>2112113.

When Green published his paper in 1964, all BBn for n6 were Busy Beaver champions. However, over the years several have been slowly chipped away. According to Pascal Michel’s Historical survey of Busy Beavers:

  • BB6 was surpassed in 1972 by Donald Lynn: Σ(6)42
  • BB7 was surpassed in 1990 by Marxen and Buntrock: Σ(6)136612 and
  • BB8 was surpassed in 2000 by Marxen and Buntrock: Σ(6)>1.4×1060

Yet, beyond this I do not know of any TMs beating Green’s Machines until finally, they are eclipsed by Daniel Nagaj’s massive BB(16) > Graham champion (since BB16g2G).

Green Machine Busy Beaver Bound
BB9 Σ(9)>3↑↑31>10↑↑30
BB10 Σ(10)>3↑↑3↑↑4>10↑↑101012
BB11 Σ(11)>3↑↑↑3↑↑↑2>10↑↑↑1012
BB12 Σ(12)>3↑↑↑3↑↑↑4
BB13 Σ(13)>34342
BB14 Σ(14)>34344
BB15 Σ(15)>35352

Do any of you know of any better results in this range? Let me know in the new comments system below (just set up today!).

Footnotes

  1. 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, doi: 10.1109/SWCT.1964.3