Main Page

The Busy Beaver function BB (called S originally) was introduced by Tibor Radó in 1962 for 2-symbol Turing machines and later generalised to m-symbol Turing machines:

BB(n,m) = Maximum number of steps done by a halting m-symbol Turing machine with n states starting from all-0 memory tape

The busy beaver function is not computable and, few of its values are known:

Small busy beaver values

	2-state	3-state	4-state	5-state	6-state
2-symbol	BB(2) = 6	BB(3) = 21	BB(4) = 107	BB(5) = 47,176,870	BB(6) > $10\uparrow \uparrow 15$
3-symbol	BB(2,3) = 38	BB(3,3) > $10^{17}$	BB(4,3) > $10^{14072}$
4-symbol	BB(2,4) = 3,932,964	BB(3,4) > 2(^15)5 + 14
5-symbol	BB(2,5) > 6.5 × $10^{38033}$

In the above table, cells are highlighted in orange when there are known Mathematically-hard machines, machines that are believed hard to prove halting or non-halting (although, generally believed non-halting), such as Cryptids.

bbchallenge.org

bbchallenge.org is a massively collaborative research project whose general goal is to obtain more knowledge on the Busy Beaver function. In practice, it mainly consists in collaboratively building Deciders, programs that automatically prove that some Turing machines do not halt. Other efforts also include:

• Formalising results using theorem provers (such as Coq)
• Maintaining lists of Holdouts for small busy beaver values
• Proving the behavior of Individual Machines
• Finding Mathematically-hard machines
• Building Accelerators to simulate halting machines faster

Notably, as part of bbchallenge.org, in June 2024 the 5th busy beaver value BB(5) was proven in Coq to be equal to the lower bound found in 1989: 47,176,870.