- Goal
- Turing machines
- The busy beaver function BB
- Possible outcomes of the challenge
- Similar projects
- References
- Related Links

The goal of the Busy Beaver Challenge (bbchallenge for short) is to collaboratively prove or disprove the following conjecture [Aaronson, 2020]:

BB(5) = 47,176,870

This conjecture says that if a 5-state Turing machine runs for more than 47,176,870 steps without halting then it will never halt (starting from all-0 memory tape).

The conjecture is based on earlier work [Marxen and Buntrock, 1990] which discovered the current 5-state busy beaver champion, a machine with 5 states that halts after 47,176,870 steps:

0 | 1 | |
---|---|---|

A | 1RB | 1LC |

B | 1RC | 1RB |

C | 1RD | 0LE |

D | 1LA | 1LD |

E | --- | 0LA |

Achieving the goal of the Busy Beaver Challenge implies to study **88,664,064 Turing machines** and decide whether they halt or not, see Method.

The introduction of Turing machines by Alan Turing in 1936 is arguably one of the founding events of computer science, [Turing, 1936].

Turing machines can be thought as a primitive computer architecture providing (i) a runtime environment consisting of a moving read/write head over a memory tape divided in adjacent memory cells and (ii) a programming language allowing us to control the behavior of the head depending on the content of the memory cell where it is currently at.

The Turing machines we work with have one bi-infinite memory tape where each cell is either containing a 0 or a 1.

The programmer specifies the code of the machine in a table with 2 columns and q rows. Rows are called **states**. Here is the code of the current 5-state busy beaver champion:

0 | 1 | |
---|---|---|

A | 1RB | 1LC |

B | 1RC | 1RB |

C | 1RD | 0LE |

D | 1LA | 1LD |

E | --- | 0LA |

Each entry of the table is called a **transition** and instructs us what to do when reading a 0 or a 1 at the current head’s position on the memory tape in a given state. For instance, in the above machine, reading a 0 in state A will:

- write a 1 at the current head position (i.e replacing the read 0 with a 1)
- move the head to the right
- jump to state B for the next instruction

The machine will **halt** (i.e. cease functionning) if it ever tries to execute an **undefined transition** denoted by **---**. Here, it would happen only if ever reading a 0 in state E .

In the context of the Busy Beaver Challenge, machines are always executed starting in state A and with a memory tape that is initially all 0 (i.e. all memory cells are 0).

As with probably any programming language, the best way to understand Turing machines is to play with them:

Machine code

1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA

Copy for https://turingmachine.io/0 | 1 | |
---|---|---|

A | 1RB | 1LC |

B | 1RC | 1RB |

C | 1RD | 0LE |

D | 1LA | 1LD |

E | 1RZ | 0LA |

Memory tape

Step #0

A more detailed simulator is available at https://turingmachine.io. Here is the code of the above machine in their format:

blank: '0' start state: A table: A: 0: {write: 1, R: B} 1: {write: 1, L: C} B: 0: {write: 1, R: C} 1: {write: 1, R: B} C: 0: {write: 1, R: D} 1: {write: 0, L: E} D: 0: {write: 1, L: A} 1: {write: 1, L: D} E: 1: {write: 0, L: A}

Space-time diagrams provide a condensed way to visualise the behavior of Turing machines. The space-time diagram of a machine is a 2D image where the i^{th} row represents the memory tape of the machine at the i^{th} iteration. Black pixels are used for memory cells containing 0 and white for 1.

Here is the space-time diagram of the first 10,000 iterations of the 5-state busy beaver champion:

Additional green and red colors are used to track the head position and its movement: green when the head has moved to the left and red when it has moved to the right.

By default, these space-time diagrams are re-scaled to fit a 400x500 canvas, hence they can be inexact due to the scaling algorithm, especially at small scales (i.e. few simulation steps).

If you tick **Explore mode** you will enter a more precise visualisation of space-time diagrams that are accurate at small scales and that will give you additional coloured information about the state of the machine at each step.

The Busy Beaver Challenge is based on a seed database of 88,664,064 undecided 5-state machines, see Method. We can consequently refer to undecided machines with their ID in this database.

For instance: https://bbchallenge.org/55897188

Turing machines have an important property: starting from a given memory tape (all-0 in our case), they either **halt** or don’t. By halting we mean that the machine tries to execute an undefined transition and, since it is undefined, stops functioning. Here is a machine that halts after 4 steps:

Machine code

1RB1RB_1LA---_------_------_------

Copy for https://turingmachine.io/0 | 1 | |
---|---|---|

A | 1RB | 1RB |

B | 1LA | --- |

C | --- | --- |

D | --- | --- |

E | --- | --- |

Memory tape

Step #0

Here is another machine that halts after 105 steps:

Machine code

1RB1LC_0LB1LA_1RD1LB_1RE0RD_0RA---

Copy for https://turingmachine.io/0 | 1 | |
---|---|---|

A | 1RB | 1LC |

B | 0LB | 1LA |

C | 1RD | 1LB |

D | 1RE | 0RD |

E | 0RA | --- |

Memory tape

Step #0

If a machine has no undefined transition it is sure that it will never halt as it cannot ever encounter an undefined transition.

However, it is not because a machine has an undefined transition that it will halt one day. The most simple example to support this statement is the following machine^[1. This machine can be thought as the “while true” of Turing machines.] that will never halt starting from all-0 tape although it has plenty undefined transitions:

Machine code

0RA---_------_------_------_------

Copy for https://turingmachine.io/0 | 1 | |
---|---|---|

A | 0RA | --- |

B | --- | --- |

C | --- | --- |

D | --- | --- |

E | --- | --- |

Memory tape

Step #0

In this case it is easy to convince ourselves that the machine will never halt starting from all-0 tape. However, if we take our earlier example:

Machine code

1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA

Copy for https://turingmachine.io/0 | 1 | |
---|---|---|

A | 1RB | 1LC |

B | 1RC | 1RB |

C | 1RD | 0LE |

D | 1LA | 1LD |

E | 1RZ | 0LA |

Memory tape

Step #0

Will this one halt or not starting from all-0 tape?

Answering this question does not look simple. Here, patience can answer it for us because the machine **does halt**, after 47,176,870 steps. However, this fact would have been quite difficult to predict just from looking at the code of the machine.

To this day, no 5-state Turing machine is known to halt after more than 47,176,870 steps.

With the Busy Beaver Challenge, we hope to discover if that 47,176,870 record can be beaten or not among 5-state machines. This implies to decide, for all machines with 5 states, whether they halt or not.

But why focusing on 5 states? Let’s first reformulate the problem in terms of busy beavers.

We can now properly define the busy beaver function BB as introduced^[2. BB(n) was called S(n) in [Rado, 1962] and the name S(n) is frequent is the literature.] in [Rado, 1962]:

BB(n) =

Maximum number of steps done by a halting Turing machine with n states starting from all-0 memory tape

Note that there is a finite number of Turing machines with n states, $(4n+1)^{2n}$ to be exact, hence BB(n) is well defined.

BB(n) is a very powerful number to know because it gives you a way to decide any machine with n states: run the machine and if it runs for BB(n)+1 steps you know that it will never halt.

This means that the function n ↦ BB(n) is not computable otherwise the halting problem of Turing machines would be decidable. Find more properties of BB in [Aaronson, 2020].

Only 4 values of BB are known:

- BB(1) = 1, [Rado, 1962]
- BB(2) = 6, [Rado, 1962]
- BB(3) = 21, [Rado and Lin, 1963]
- BB(4) = 107, [Brady, 1983]

The fact that BB(4) = 107 means that if a 4-state Turing machine does not halt after 107 steps starting from all-0 tape then it will never halt.

Proving the value of BB(n) implies to be able to decipher the behavior of any machine with n-states (starting from all-0 tape). The number of machines grows exponentially with n hence making the task overwhelmingly hard very quickly.

Currently, BB(5) is unknown but is conjectured to be BB(5) = 47,176,870 [Aaronson, 2020] [Marxen and Buntrock, 1990]. The naïve space of 5-state Turing machines contains $21^{10} \simeq 1.6\times 10^{13}$ machines, see Method for how we can reduce and search this space efficiently.

Apart from concrete values of BB, the following is also known:

- BB(5) >= 47,176,870 [Marxen and Buntrock, 1990]
- BB(6) $> 7.514\times 10^{36,534}$ [Kropitz, 2010]
- BB(7) $\geq 10^{10^{10^{18,705,352}}}$ [Wythagoras, 2014] [Cloudy176, 2014] [Michel, 2009]
- BB(15) is at least as hard as Erdős’ conjecture on powers of 2: “for n > 8, there is at least one digit 2 in the base-3 representation of 2
^{n}“. [Stérin and Woods, 2021] - BB(27) is at least as hard as Goldbach conjecture: “for n > 2, every even integer is the sum of two primes” unverified construction [Aaronson, 2020]
- BB(744) is at least as hard as Riemann Hypothesis [Matiyasevich and O’Rear and Aaronson, unpublished]
- BB(748) is independent of ZF [O’Rear, unpublished]
- BB(5,372) is at least as hard as Riemann Hypothesis [Yedidia and Aaronson, 2016]
- BB(7, 910) is independent of ZFC [Yedidia and Aaronson, 2016]

All these results come from constructing explicit Turing machines. For instance, in [Stérin and Woods, 2021], the authors construct an explicit 15-state Turing machine which enumerates all powers of two in base 3 until it finds a counterexample to Erdős’ conjecture on powers of 2. Hence the machine halts if and only if the conjecture is false!

Knowing the value of BB(15) would imply that we’d know if that particular 15-state Turing machine halts or not, it means that knowing BB(15) is at least as hard as solving Erdős’ conjecture.

These results provide a scale, **the busy beaver scale**, on which we can measure the complexity of various mathematical problems^[3. Not all mathematical conjectures can be weighted on the busy beaver scale as you need the set of counterexamples to the conjecture to be recursively enumarable. For instance, it is not known whether the set of counterexamples to the Collatz conjecture is r.e. or not: how would an algorithm recognise a divergent Collatz trajectory?.]. For instance, according to this scale (and current knowledge), Erdős’ conjecture on powers of 2 is less complex than Goldbach conjecture since it can be encoded as the halting problem of a smaller Turing machine.

These results also drastically reduce the hope that we’d ever know the value of BB even for small values such as 15. Even worse, BB(6)
$> 7.514\times 10^{36,534}$ [Kropitz, 2010] as there is a 6-state Turing machine halting after roughly that many steps (exact number given in [Kropitz, 2010]), which is way bigger than the estimated number of atoms in the universe 10^{80}.

Hence, the frontier between tractable and intractable values of BB seems to be situated at BB(5).

The above motivates the Busy Beaver Challenge: **let’s try to collaboratively find BB(5)**, the smallest currently unkown BB value.

Prior work exhibited the current 5-state busy beaver champion halting after 47,176,870 steps [Marxen and Buntrock, 1990] which has not been beaten in the past 30 years.

This led to [Aaronson, 2020] conjecturing that BB(5) = 47,176,870.

Go to Method and Contribute to see how we plan to find BB(5) and how you can contribute.

Are you up for the challenge?

Here are some possible outcomes to the quest of looking for BB(5):

We decide the halting problem of all 5-state machines (from all-0 tape), see Method, which as a result gives the value of BB(5) 🥳

We find a 5-state machine that halts after more than 47,176,870 steps hence improving Aaronson’s conjecture [Aaronson, 2020] 🥳

We establish a fine-grained Zoology of the behaviors of 5-state Turing machines which allows us to understand what they are capable of and where complexity lies 🥳

We decide as many machines as we can but fail to decide some of them. Their individual halting problems compete for the title of “simplest open problem in mathematics” (on the busy beaver scale) which is also 🥳

In 2003, Skelet released ≈6000 lines of Pascal that aim at achieving the same result as the Busy Beaver Challenge (but ~20 years before): decide the behavior of all 5-state Turing machines from all-0 tape. Skelet’s program left only 164 machines undecided which he reduced further to only 43 “hardly non-regular” machines. This is claimed to have since been reduced even further to a mere 21 machines by various authors including Dan Briggs. Significant work has been made by these authors to manually decide the behavior of Skelet’s 43 machines.

This represents a substantial and truly impressive effort.

However, we do not believe that Skelet’s program has been reviewed independently, and proving 6,000 lines of uncommented Pascal correct would be difficult (How can we be sure that the original set of 164 machines is not erroneous? I.e we’d need a proof that some machines were not overlooked or nor decided using incorrect arguments.).

In contrast, it is one of the core mission of the Busy Beaver Challenge to provide collaborative, open source, concise, modular, tested and proved correct code in order to facilitate peer-review and increase trust in the final outcome of the challenge. See our reproducibility and verifiability statement.

The full list of Skelet’s 43 machines and their equivalents in the Busy Beaver Challenge is available here.

In 2009, Joachim Hertel published a method that he claims leaves only 100 machines undecided (called “holdouts”). The method seems to be very robust and an independent reproduction of these results would be very interesting.

- [Aaronson, 2020]
- [Brady, 1983]
- [Cloudy176, 2014]
- [Marxen and Buntrock, 1990]
- [Michel, 2009]
- [Rado, 1962]
- [Rado and Lin, 1963]
- [Stérin and Woods, 2021]
- [Yedidia and Aaronson, 2016]
- [Wythagoras, 2014]