Green's Machines
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
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 (
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
G Component
The main workhorse is the
State | 0 | 1 |
---|---|---|
… | … | … |
… | … | … |
Where the
This component has a single entry state (
These compute a series of fast-growing functions
Setup Components
There are two different setup components
Three-State Setup
The
State | 0 | 1 |
---|---|---|
where
When attached to A
and halt state Z
).
Four-State Setup
The
State | 0 | 1 |
---|---|---|
where
which, when attached to A
and halt state Z
).
Example Machines
Putting this all together and converting into Standard Text format we get for example:
:1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1RG1RE
(on bbchallenge) :1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1RH1RF
(on bbchallenge) :1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1RI1RG
(on bbchallenge) :1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1RJ1RH
(on bbchallenge)
Note:
- 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.
- 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 M
, as a Class G Machine (with entry state
In words:
- When started in its entry state (
) on a0
- with a string on
1
s 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 (
) - with a string
1
s to its left (and nothing else).
- with a string on
- When started in its entry state (
) on a1
,- it moves immediately to the right and enters the exit state (
).
- it moves immediately to the right and enters the exit state (
We will say that M
computes the function
Recurrence
Note: An immediate consequence of the above specification is that:
G Components
Each
Base Case
We can see directly that
State | 0 | 1 |
---|---|---|
is a Class G Machine (with entry state
Inductive Step
We can build
State | 0 | 1 |
---|---|---|
Now, assuming that
First, the easy part:
in a single step.
Second, we will use the inductive assumption which tells us that
in order to prove:
thus proving that
Fast-growing Hierarchy
Thus we can see that
# States | Function | |
---|---|---|
1 | ||
3 | ||
5 | ||
7 | ||
9 |
Setup Components
While the sequence of
Three-State Setup
Starting from any
State | 0 | 1 |
---|---|---|
Then we can see, that, starting in state A
on a blank tape we get the trajectory:
Which halts with exactly 1
s on the tape (this TMs “score”).
Note that:
so we can rewrite these scores as
Four-State Setup
Starting from any
State | 0 | 1 |
---|---|---|
Prerequisites
This setup is more subtle to prove. It actually depends upon the fact that
This turns out to be true for all
Specifically, we use this fact below in the following transitions:
Since
We also need to prove a general rule first:
Applying this recursively we get:
Behavior
Finally, we can see, that, starting this TM in state A
on a blank tape we get the trajectory:
Which halts with exactly 1
s on the tape (this TMs “score”).
Once again, we can simplify:
Summary
Putting this all together, Green defined components 1
s upon halting. Precisely,
Values and Bounds
We can compute the following exact values and (reasonably tight) bounds using Knuth up-arrow notation:
And similarly for
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
.
When Green published his paper in 1964, all
was surpassed in 1972 by Donald Lynn: was surpassed in 1990 by Marxen and Buntrock: and was surpassed in 2000 by Marxen and Buntrock:
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
Green Machine | Busy Beaver Bound |
---|---|
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
-
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. ↩