Busy Beaver Challenge

Created by Pavel Klavík

Every N-state Turing machine either runs forever or halts after some number of steps. The machine halting after most steps is called the Nth Busy Beaver, and the number of its steps is BB(N). Recently, a Discord math community was able to establish BB(5) and are currently working on BB(6) and other related problems. This map describes their progress, the current challenging machines and relation of this problem to general math and computer science: Gödel's incompleteness theorems in logic and Halting problem in computability.

#Turing machine, #challenge, #complexity, #computability, #computer science, #math

Space-time diagrams

Certain machines can be quickly understood by drawing their tape configurations after each step. Here, we show an example of a 2-state binary counter. Its behavior is immediately clear from the picture.

ChatGPT Image Oct 8, 2026, 05 53 56 PM

Turing machine

A mathematical model of a computer consists of:

Memory represented by infinite tape.
Program described by a state machine.

Turing Machine Model Davey 2012

Memory

Memory is an infinite tape extending in both directions and consisting of linearly ordered cells. Each cell has one symbol written in it. For binary Turing machines, it is either 0 or 1. The initial contents of the tape encode the machine's input.

Turing machine 2b.svg

The machine has a head that is at some position at each step. The head reads the symbol and writes a new one (potentially the same as before).

Example of halting machine

This is an example of a 2-state Turing machine which halts at the 3rd step.

	0	1
A	1RB	HALT
B	1LA	0RB

Play the video to see how it behaves.

Alan turing header

Program

The machine consists of $k$ different states, named $A$ , $B$ , $C$ , … The initial state is $A$ .

At each step, the machine is in some state and reads the current symbol from the tape. Based on its state and the symbol it reads, it does the following:

Writes a new symbol at this position.
Moves the tape's head one cell to the left or right.
Switches to a new program state.

The transition can instead be HALT, which immediately stops the computation.

Goldbach's Conjecture

Goldbach's conjecture states that every even number $n \ge 4$ can be written as a sum of two prime numbers:

$\begin{aligned} &4 = 2+2, &\qquad&12 = 5+7,\\ &6 = 3+3, &\qquad&14 = 7+7,\\ &8 = 3+5, &\qquad&16 = 5+11,\\ &10 = 5+5, &\qquad&18 = 7+11. \end{aligned}$

The conjecture was computationally verified for all $n \le 4 \cdot 10^{18}$ , but a general proof is not yet known.

The conjecture may seem unlikely, but it appears to hold. As $n$ grows, one always has to be lucky to match two primes together; on the other hand, the number of possible primes to choose from grows with $n$ .

There is a weaker version of Goldbach's conjecture stating that every odd number $n \ge 7$ can be written as a sum of three prime numbers. This was proved by Helfgott in 2013. Note that if the three-prime statement held for all numbers $n\ge6$ , not only odd ones, it would imply Goldbach's conjecture.

Table description

Each $n$ -state Turing machine with $b$ symbols can be described by a table having $n$ rows and $b$ columns. Each cell specifies one transition for a state and read symbol, for example 1RB specifies that the newly written symbol is 1, the head moves to the right and the new state is $B$ . If the transition is halting, it is described as --- or HALT.

BBChallenge uses the format where the entire table is written into a single line such as

1RB1LB_1LA---

Here, _ is the line separator, so this is a 2-state binary Turing machine. The code 1RB1LB gives the transitions in state $A$ : the machine transitions either to 1RB if it reads 0, or to 1LB if it reads 1. Similarly, in $B$ state, the machine follows 1LA---, so it transitions to 1LA if it reads 0 and halts if it reads 1. This machine is the second Busy Beaver champion.

Example of endless loop

Here is another 2-state Turing machine which runs forever.

	0	1
A	1RB	1RB
B	0LA	HALT

Play the video to see how it behaves.

BB(25) would solve Goldbach's conjecture

There certainly exists a Turing machine which implements the described pseudocode. It can be further optimized into the following 25-state Turing machine which halts if and only if there exists a counterexample for Goldbach's conjecture:

If we knew $\operatorname{BB}(25)$ , we could run this machine for $\operatorname{BB}(25)+1$ steps: if it did not halt, no counterexample would exist.

So would knowing $\operatorname{BB}(25)$ actually help us in solving Goldbach's conjecture? Not really. First of all, $\operatorname{BB(25)}$ would be so huge that simulating a Turing machine for this number of steps wouldn't be feasible anyway.

But computing $\operatorname{BB}(25)$ would require deciding, for every 25-state Turing machine, whether it halts. In particular, $\operatorname{BB}(25)$ includes Goldbach's conjecture as a subproblem, as well as many harder problems, some of which might even be unprovable in a chosen formal theory. So working on the Busy Beaver number is not a way to solve hard math problems.

Halting would solve Goldbach's conjecture

A simple machine for testing Goldbach's conjecture works as follows. It checks even numbers $n=4,6,8,10,\dots$ one by one. For each $n$ , it checks for all numbers $2 \le p \le {n \over 2}$ whether both $p$ and $q=n-p$ are prime. To check whether $p$ is prime, we only need to check that $p$ has no divisor between $2$ and $\sqrt p$ .

isPrime(p):
  for l = 2, 3, ..., sqrt(p):
    if p % l = 0:
      return false;
  return true;

for n = 4, 6, 8, 10, ...:
    found := false

    for p = 2, ..., n/2:
        q := n - p
        if isPrime(p) and isPrime(q):
            found := true
            break

    if not found:
        HALT

So if we could solve halting for this program, we would know whether Goldbach's conjecture is correct.

BB(120) would solve Riemann Hypothesis

For

$\zeta(s) = \sum_{n=1}^\infty {1 \over n^s},\qquad \textrm{where }\Re(s) > 1,$

The Riemann zeta function is obtained by meromorphic continuation to $\mathbb C$ . It has trivial zeros for $s=-2,-4,-6,\dots$ . The Riemann Hypothesis asks whether all other non-trivial zeros lie in the critical line $\frac12+c\cdot i$ where $c \in \mathbb R$ . It is a famous unresolved problem of mathematics, one of the Millennium Prize Problems with a $1,000,000 prize, deeply related to the distribution of prime numbers. Recently, OpenAI proved in a preprint that there are no zeros for $\Re(s) > \frac 78$ .

On September 23, 2026, a 120-state Turing machine was constructed which tests the Riemann Hypothesis. It halts if and only if the Riemann Hypothesis is false. Instead of searching for non-trivial zeros outside the critical line, it verifies certain arithmetical equalities involving

$A_n = n! \!\!\!\!\!\!\prod_{p \le n : p\textrm{ is prime}} \!\!\!\!\!\!\!p.$

If any of them is invalid, a counterexample to the Riemann Hypothesis is found.

To solve $\operatorname{BB}(120)$ , one would need to solve Riemann Hypothesis among many other very hard problems.

Bouncers

bouncers

Machines repeatedly sweeping across an expanding region. A proof can often use an inductive rule describing how each sweep transforms the tape.

Bells

bells

Their space-time diagrams have characteristic widening and narrowing, bell-like shapes. Some exhibit polynomial growth or inverted-bell patterns.

Translated cyclers

translated-cyclers

The machine constructs the same local pattern at a different tape position, often continually moving left or right. This behavior is also quite simple to analyze, but it may emerge only after a large number of initial steps.

Graph representation

Instead of a table, we can create a graph where each machine state is represented by a node. From each node, there are at most $b$ outgoing labeled edges, describing the read symbol, the written symbol, and how the head moves. The target node is the new state. When the outgoing edge is missing, the machine halts.

For example, here is the mentioned 2nd Busy Beaver champion.

How many Turing machines exist?

Each $n$ -state binary Turing machine is described by $2n$ transitions. Each transition may be halting (1 choice) or specifies a new state ( $n$ choices) + tape direction (2 choices) + written symbol (2 choices), so in total there are $4n+1$ choices. Since transitions can be chosen independently, there are $(4n+1)^{2n}$ different $n$ -state binary Turing machines.

When studying all these machines, some of them behave the same, and we just need to understand one of them. So we can identify machines up to symmetry and removal of unreachable states, yielding so-called TNF (Tree Normal Form), which significantly decreases the number of studied machines. Further, after unifying symmetries and ignoring machines which clearly run forever, we know that A0 either transitions to 0RB or 1RB. A commonly used restriction only studies machines where A0 transitions to 1RB, denoted TNF-1RB.

$\boldsymbol n$	All $\boldsymbol{\operatorname{BB}(n)}$ machines	TNF-1RB candidates
1	25	1
2	6,561	41
3	4,826,809	4,057
4	6,975,757,441	620,261
5	16,679,880,978,201	126,891,605
6	59,604,644,775,390,625	≈33,436,000,000

BB(n) grows faster than any computable function

The reason is that $\operatorname{BB}(n)$ has to grow really fast. It grows faster than any computable function $f : \mathbb N \to \mathbb N$ . Why?

Suppose that there were some computable function $f$ which is an upper bound for $\operatorname{BB}(n)$ . Then one could solve the halting problem for any $n$ -state Turing machine by first computing $f(n)$ and then simulating the machine for $f(n)$ steps. If the machine stops beforehand, it halts. Otherwise it runs longer than $\operatorname{BB}(n)$ and we know that it will run forever.

So $\operatorname{BB}(n)$ grows faster than exponential functions, tower functions, the Ackermann function, and everything else whose values can be computed.

Counters

counters

The machine encodes an integer that is incremented or transformed. Variants include binary, Fibonacci, exponential, and superexponential counters.

Types of machines

Cyclers

cyclers

These are the simplest machines: they repeatedly go through the same pattern. They are easiest to analyze.

BB(n) grows really fast

Let's take a look at the first few values of $\operatorname{BB}(n)$ . They grow very fast:

$\operatorname{BB}(1) = 1$ ,
$\operatorname{BB}(2) = 6,$
$\operatorname{BB}(3) = 21$ ,
$\operatorname{BB}(4) = 107,$
$\operatorname{BB}(5) = 47,176,870$ ,
$\operatorname{BB}(6) > 10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8$ .

How large is $\operatorname{BB}(6)$ ? The notation $a \uparrow\uparrow b$ is the tower of $a$ 's of height $b$ . So just

$10 \uparrow \uparrow 8 = 10^{10^{10^{10^{10^{10^{10^{10}}}}}}}$

is incredibly huge, already so much larger than a googolplex $10^{10^{100}}$ . But next it has another tower raised to this huge height, and the humongous result is used as the height of another tower.

Why is Halting useful?

Usually when working with programs, we care whether they compute something correctly and how fast the computation runs. For example, if we want to sort numbers, we care that the resulting sequence is correctly sorted and whether the algorithm runs in $\mathcal O(n^2)$ or $\mathcal O(n \log n)$ steps.

So why is the Halting problem even interesting? This was not explained to me clearly when I was studying computer science at university. There is a practical programming motivation: to know whether a program gets stuck in an infinite loop. But the theoretical reason is that we can encode a lot of different questions into whether some program halts or runs forever.

Holdouts

Holdouts are Turing machines that are not yet understood. They may halt or run forever.

Why is BB(n) undecidable?

Computing $\operatorname{BB}(n)$ is equally hard as solving the Halting problem for $n$ -state Turing machines. Why?

If we could solve the Halting problem, we could just check all $n$ -state Turing machines one by one. A hypothetical solution to the Halting problem would identify those that run forever; we could then simulate the others until the last one stops. Then we know how large is $\operatorname{BB}(n)$ .

On the other hand, if we knew $\operatorname{BB}(n)$ , we could just simulate the given $n$ -state Turing machine for $\operatorname{BB}(n) + 1$ steps. If it halts beforehand, it halts. Otherwise it runs forever.

Cryptid Lovecraft beaver

Cryptids

cryptids

Cryptids are Turing machines which correspond to a known mathematical problem. So they are fully analyzed, but finding out whether they halt or run forever depends on whether a mathematical conjecture is true or false. So resolving them might be hard and might require the discovery of new mathematics.

Busy Beaver problem

Consider all $n$ -state Turing machines with binary tapes starting at all zeros. Some of the machines run forever, so we ignore these. Others halt after some number of steps.

$\operatorname{BB}(n)$ is the maximum number of steps a halting $n$ -state Turing machine takes. So the $n$ -th Busy Beaver machine is the halting $n$ -state machine which takes the most steps before halting.

Similarly, $\operatorname{BB}(n,k)$ asks the same for all $n$ -state Turing machines using $k$ different tape symbols; so $\operatorname{BB}(n) = \operatorname{BB}(n,2)$ .

Halting problem

Is it possible to construct a machine which decides whether other machines halt or run forever? It is of course possible to simulate the machine, but if it keeps running, we never know whether it will run forever or halt just after a few more steps.

Cantor's diagonalization argument

Two sets $A$ and $B$ are of equal size if there exists a bijection between them, pairing their elements.

We want to show that the set of all infinite binary sequences is larger than $\mathbb N$ . We therefore want to show that not all binary sequences can be numbered by $1,2,\dots$ . For contradiction, suppose that they can, so $s_1,s_2,\dots$ are all binary sequences. Write them as an infinite table. Consider the diagonal of this infinite table and construct $s$ by flipping all values on it. It is a valid binary sequence $s$ which is different from all numbered sequences in the table. For $s_i$ , it is different in the $i$ -th value. So not all binary sequences were enumerated.

Cantor used this argument to prove that $|\mathbb N| < |\mathbb R|$ and for every set $A$ , the set of all its subsets $2^A$ is larger: $|A| < |2^A|$ .

Georg Cantor2

Current BB values and bounds

See BBChallenge Wiki for up-to-date values.

Orange and tan values have known cryptids, so solving the Busy Beaver problem for them might require new mathematics.

How is this related to diagonalization

Consider the two-input halting function $H(P_i,P_j)$ , which states whether $P_i$ halts on $P_j$ . Construct an infinite table containing all programs and their halting behavior on all inputs, so $H(P_i,P_j)$ . The key point is that every program appears as a row in this table.

Consider the diagonal formed by $H(P_i,P_i)$ . The construction of $D$ negates the values on the diagonal so

$D(P_i)=\neg H(P_i,P_i).$

Now, if a program computing $D$ exists, it would be equal to some program $P_k$ and would appear in the table. But this is impossible: $D(P_k)=\neg H(P_k,P_k)$ , while the table gives the opposite value $H(P_k,P_k)$ . So no program computes $D$ .

Scott Aaronson - The Busy Beaver Frontier

The Busy Beaver Frontier.pdf

What is known about BB(6)

See its status page.

Beaver Math Olympiad

Reformulating hard Turing machines as mathematical problems lets mathematicians solve them without considering the details of Turing machines and their tape structures:

https://wiki.bbchallenge.org/wiki/Beaver_Math_Olympiad

Number of BB(6) holdouts

As of October 7th 2026, only 778 representative 6-state Turing machines have to be solved to resolve $\operatorname{BB}(6)$ .

bfa5518c-c901-4c6f-b027-222db1a36517

a88df6c7-cb33-4a38-8255-fb6b2bd1ef6c

Halting problem is undecidable

Turing proved that there is no Turing machine solving the halting problem. The argument uses Cantor's diagonalization.

Programs can be encoded as integers and numbered $P_0,P_1,\dots$ . Their inputs are integers and we will be using their codes as inputs. Let $P_i(x)$ be the output of the program $P_i$ on the input $x$ .

Suppose for contradiction that there exists a program $H$ which solves halting. We construct a new program $D$ by negating $H$ . $D$ on the input $P_i$ runs the halting subprogram $H(P_i)$ so it learns in finite time whether $P_i$ halts on $P_i$ . Then it does the opposite:

if  halts:
  loop forever
else:
  halt

We conclude the proof by showing that $D$ does not exist, implying that also $H$ does not exist.

What happens when $D$ runs on the input $D$ ? It first runs $H(D)$ , so it learns in finite time whether $D$ halts on the input $D$ . But then it does the opposite, which contradicts correctness of $H(D)$ . If $D$ halts on $D$ , it does not halt on $D$ , and vice versa. Therefore $D$ cannot exist and thus the halting program $H$ does not exist.

Is BB(6) almost done?

Efforts over the last three years have reduced the total number of machines from 33 billion to just 778 remaining representative holdout machines. So is $\operatorname{BB}(6)$ almost done?

Not really. Most machines are quite easy to solve: they either stop quickly or clearly run forever. The remaining machines are actually the true hard part of the $\operatorname{BB}(6)$ problem. This includes some cryptids: their Turing machines are fully understood, but whether they halt or run forever seems to be a hard question in number theory.

Proof based on diagonalization

Statements and proofs can be numbered. This allows arithmetic to make statements about which formulas are provable. Gödel constructs a sentence that refers to its own provability and thereby escapes what the formal theory can prove.

Second Gödel's Theorem

A theory $T$ is consistent if it cannot prove both a statement $\varphi$ and its negation $\neg \varphi$ . Equivalently, no contradiction, such as $0 = 1$ , is provable.

Second Gödel's Theorem states that any sufficiently powerful consistent theory $T$ cannot prove its own consistency.

If $T$ is inconsistent, it is possible to prove anything from a contradiction. So a sufficiently strong theory can prove its own consistency only if it is inconsistent.

Note that it still might be possible to prove consistency of $T$ inside a stronger theory $T'$ . For example, it is possible to prove consistency of PA inside ZFC.

Space Needle Cryptid

What about BB(3,3)

Another research direction is the study of 3-state Turing machines with 3 symbols 0, 1, 2. We are relatively close: only six machines need to be solved. Unfortunately, their behavior is also already quite complex. So resolving $\operatorname{BB}(3,3)$ might take a long time and might be very difficult.

In particular, Bigfoot is doing a Collatz-like recurrence and it is likely non-halting. Wily Coyote and its variants are also quite complex.

BB(n) is unprovable already for a fixed n

By Gödel's Second Theorem, no sufficiently powerful consistent theory $T$ can prove its consistency. On the other hand, for some $n_T$ , it is possible to construct an $n_T$ -state Turing machine which examines proofs in $T$ one-by-one and checks for a contradiction, say $0=1$ . Therefore $BB(n)$ for every $n \ge n_T$ cannot be proven inside a consistent theory $T$ , otherwise it could be used to prove its own consistency.

Antihydra

One of the remaining 6-state Turing machines. When carefully analyzed, the machine simulates the following recurrence on pairs of integers $(a,n)$ , called the hydra function.

When $n$ is even, it is mapped to $(a+2,3n\, /\, 2)$ .
When $n$ is odd, it is mapped to $\bigl(a-1,(3n-1)\,/\,2\bigr)$ .

The machine reaches $(0,8)$ after some initial steps. It halts if $a$ ever reaches $-1$ .

Space Needle

One of the remaining 6-state Turing machines. When analyzed, the machine simulates the following recurrence on $b$ starting at 6. Let $b = 2^k\cdot m$ , where $m$ is odd.

If $m=1$ , then $b$ is a power of two, so the machine halts.
Otherwise, $b$ becomes $b+k+\frac 32 \left ({b \over 2^k} - 1\right ).$

The first few steps are:

$6 \rightarrow 10 \rightarrow 17 \rightarrow 41 \rightarrow 101 \rightarrow 251 \rightarrow 626 \rightarrow 1095 \rightarrow 2736 \rightarrow 2995 \rightarrow \cdots$

First Gödel's Theorem

A theory $T$ is complete if for every statement $\varphi$ expressible in $T$ , either $T$ proves $\varphi$ or $\neg\varphi$ .

First Gödel's Theorem states that any sufficiently powerful consistent theory $T$ is incomplete, so there exist statements $\varphi$ for which there is no proof for $\varphi$ and $\neg\varphi$ .

So in a sufficiently powerful consistent theory, there are statements which cannot be proven or disproven.

For example, consider the Continuum Hypothesis (CH) stating that there is no set whose size is strictly between $|\mathbb N|$ and $|\mathbb R|$ . In ZFC, assuming its consistency, CH cannot be proven or disproven, it is independent.

Young Kurt G%C3%B6del as a student in 1925

Mossy Tentacle-Eyed Cryptid Monster

Is it halting?

As of September 2026, the trajectory of $b$ was computed for 100,000,000 steps. No power of 2 was encountered. The highest encountered $k$ was just 25 for $n = 23{,}145{,}881$ . The final value $b$ has 94,125,050 bits (28,334,464 decimal digits) and it seems quite unlikely that $b$ will ever be a power of 2.

Of course, this is not a proof that the machine runs forever; perhaps it will eventually be exceptionally lucky.

Bigfoot

One of the 3-state 3-symbol Turing machines. Analysis shows that its high-level behavior iterates triples $(a,b,c)$ by rules according to divisibility of $b$ by six:

$\begin{aligned} (a,6b,c)&\longrightarrow(a,8b+c-1,2),\\ (a,6b+1,c)&\longrightarrow(a+1,8b+c-1,3),\\ (a,6b+2,c)&\longrightarrow(a-1,8b+c+3,2),\qquad a\ge1,\\ (a,6b+3,c)&\longrightarrow(a,8b+c+1,5),\\ (a,6b+4,c)&\longrightarrow(a+1,8b+c+3,2),\\ (a,6b+5,c)&\longrightarrow(a,8b+c+5,3) \end{aligned}$

The machine starts at $(2,1,2)$ and halts if it ever reaches $(0,6b+2,c)$ .

After 24,000,000 steps, $a = 3{,}999{,}888$ . It is very unlikely that the machine will ever halt. If its behavior were modeled as a random process, it would be twice as likely that $a$ increases by one than that it decreases by one. It would then be a random walk biased toward $+\infty$ . Of course, it is not a random process but a fully deterministic process, so this is not a valid mathematical proof that Bigfoot runs forever.

BB(372) is unprovable in PA

There is a construction of a 372-state Turing machine which searches for a contradiction in PA and halts if it finds one. So the value of $\operatorname{BB}(372)$ cannot be proven inside PA, unless it is inconsistent.

PA (Peano Arithmetic)

PA is a formal theory for natural numbers. It contains 0, the successor operation $S$ , addition and multiplication, and axioms describing how they behave. For example, the axiom of induction states this:

If $0 \in K$ and for every $n\in K$ implies $S(n) \in K$ , then $K$ contains every natural number.

This makes PA a natural framework for proving general statements about natural numbers.

A proof in PA is a finite sequence of simple formal steps that can be checked mechanically. For example, it can be proved that addition is commutative. PA is a precise foundation for elementary arithmetic, even though it does not directly speak about arbitrary sets, functions or real numbers.

Why is it likely not halting?

If the parity of $n$ behaved randomly, the process would resemble a biased random walk: with probability $1 \over 2$ , it would move two steps to the right, and with probability $1 \over 2$ , one step to the left. It would therefore tend toward $+\infty$ .

Antihydra was simulated for $2^{38}$ steps, during which $a$ reached $2^{37}$ and never hit $-1$ . It is very unlikely that the walk will ever reach $-1$ .

This is not a proof: the parity of $n$ in the process is fully determined, not random.

BB(423) is unprovable in ZF

There is a construction of a 423-state Turing machine which searches for a contradiction in ZF (without the Axiom of Choice) and halts if it finds one. So the value of $\operatorname{BB}(423)$ cannot be proven inside ZF, unless it is inconsistent.

ZFC

ZFC is the usual foundational theory of sets. It takes sets as its basic objects and describes which sets may be formed from other sets. The final letter, C, stands for the Axiom of Choice, a principle used throughout much of mathematics.

Natural numbers can be constructed inside ZFC:

$0 = \emptyset,\qquad 1 = \{\emptyset\},\qquad 2 = \bigl\{\emptyset, \{\emptyset\}\bigr\},\qquad 3 = \Bigl\{\emptyset, \{\emptyset\}, \bigl\{\emptyset, \{\emptyset\}\bigr\}\Bigr\},\qquad \dots$

Ordinary arithmetic and PA can be expressed within it. ZFC therefore provides a common formal language in which a large part of modern mathematics can be developed.

Its axioms allow building other familiar mathematical objects from sets, including functions, real numbers, spaces, and many other structures.

Collatz-like behavior already for some small Turing machines

These are recurrences starting with some number $n$ which is updated at each step according to divisibility of the current number. When some Turing machines are carefully analyzed, these recurrences are simulated over multiple low-level steps. The question whether such a Turing machine halts then becomes a problem in number theory.

Even though these recurrences are similar to Collatz Conjecture, we don't know whether they are really hard. Not much research effort has been devoted to them, so there might be some simple arguments that solve them.

Busy Beaver might shed some light into Gödel's Theorems

By Gödel's Theorems, we know that in every sufficiently strong consistent mathematical theory, there exist statements which are undecidable. But the proof constructs artificial self-referencing statements, unlike common problems which are solved in mathematics. So a natural question is to ask how close is the boundary of undecidability?

The Busy Beaver problem might allow us to gain a better understanding of this. What is the first $\operatorname{BB}(n)$ which is unprovable in PA or ZF? We can improve upper bounds by constructing better Turing machines solving unprovable problems. It is very unlikely that the current machine upper bounds are optimal, since relatively little overall effort has been devoted to their construction. Scott Aaronson conjectured in The Busy Beaver Frontier.pdf that $\operatorname{BB}(10)$ is already unprovable in PA and $\operatorname{BB}(20)$ in ZF.

On the other hand, by investigating Turing machines for smaller values of $n$ , we push the lower bound for $\operatorname{BB}(n)$ up. Even if we cannot determine the precise value of $\operatorname{BB}(n)$ , we can still catalog and understand possible $n$ -state Turing machines.

BB(5) machine

The fifth Busy Beaver machine simulates the following recurrence. It starts at number $0$ . At each step, according to its residue modulo 3:

When $n \equiv 0\ (\mathrm{mod}\ 3)$ , it becomes $5n+18 \over 3$ .
When $n \equiv 1\ (\mathrm{mod}\ 3)$ , it becomes $5n+22 \over 3$ .
When $n \equiv 2\ (\mathrm{mod}\ 3)$ , the machine HALTS.

The recurrence goes through the following sequence of numbers:

0 → 6 → 16 → 34 → 64 → 114 → 196 → 334 → 564 → 946 → 1584 → 2646 → 4416 → 7366 → 12284 → HALT.

It runs for 47,176,870 steps because it simulates this recurrence incredibly slowly.

Collatz Conjecture

A famous unsolved mathematical problem that is incredibly simple to state. Start with any positive integer $n$ and apply these rules repeatedly:

When $n$ is odd, replace it with $3n+1$ .
When $n$ is even, replace it with $n\,/\,2$ .

Collatz Conjecture: For all starting numbers $n$ , the process eventually reaches $1$ .

Example

Example of two starting values:

$12 \to 6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$
$\begin{align} 19 \to 58 \to 29 \to 88 \to 44 \to 22 \to 11 \to 34 \to 17 \to 52 \to\\ 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1 \end{align}$

The behavior is chaotic and very hard to predict. Starting at $n=27$ , the process takes 111 steps to finish and even reaches 9232 before eventually falling to 1.

Current knowledge

It was computationally verified for all numbers below $2^{71} \approx 2.36 \cdot 10^{21}$ . This is strong evidence, not a proof.
Tao (2019) proved that for almost all starting values, an orbit eventually drops below any chosen function tending to infinity, however slowly.
When the process is modeled as a random walk, an overall descent is predicted. But there are exceptional numbers which jump up a lot before descending towards one. This makes a general proof difficult.

15

23

11

93

45

35

141

69

17

Tree of odd values

Behavior on some small odd values. Even values in the middle are skipped for clarity.