Table of contents

1. Goal
2. Turing machines
   1. Interactive simulator
   2. Space-time diagrams
   3. Will it halt or not?
3. The busy beaver function BB
   1. Definition of BB
   2. What is known about BB
   3. BB(5)
4. Possible outcomes of the challenge
5. Similar projects
   1. Skelet’s 43 undecided machines
   2. Hertel’s 100 holdouts
6. References
7. Related Links

Goal

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

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, explicitly formulated in [Aaronson, 2020], is based on the pioneer work of [Marxen and Buntrock, 1990] who discovered the current 5-state busy beaver champion, a machine with 5 states that halts after 47,176,870 steps:

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.

You can help!

Turing machines

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:

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:

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

The machine will halt (i.e. cease functioning) 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).

Interactive simulator

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

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

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.

Machine ID

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

Will it halt or not?

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:

Here is another machine that halts after 105 steps:

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 that will never halt starting from all-0 tape although it has plenty undefined transitions:

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:

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.

The busy beaver function BB

Definition of BB

We can now properly define the busy beaver function BB (called S originally) as introduced in [Rado, 1962]:

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].

What is known about BB

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 [Marxen and Buntrock, 1990] [Aaronson, 2020]. 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) $> 10 \uparrow \uparrow {15}$ [Kropitz, 2022]
• 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ⁿ“. [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.

The busy beaver scale

These results provide a scale, the busy beaver scale, on which we can measure the complexity of various mathematical problems. 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) $> 10 \uparrow \uparrow {15}$ [Kropitz, 2022] as there is a 6-state Turing machine halting after roughly that many steps, which is way bigger than the estimated number of atoms in the universe 10⁸⁰.

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

BB(5)

The above motivates the Busy Beaver Challenge: let’s try to collaboratively find BB(5), the smallest currently unknown 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?

Possible outcomes of 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 🥳

Similar projects

Skelet’s 43 undecided machines

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.

Hertel’s 100 holdouts

In 2009, Joachim Hertel published a method that claims to leave only 100 machines undecided. The method seems to be very robust and an independent reproduction of these results would be very interesting.

References

• [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]

Related Links

• Heiner Marxen’s website
• Pascal Michel’s website
• Rensselaer RAIR Lab
• Skelet’s website
• Busy Beaver Discuss (Google Groups)