nLab busy beaver function

Idea

What is now called the busy beaver function $BB \colon \mathbb{N} \longrightarrow \mathbb{N}$ (originally discussed by Radó 1962 who spoke of the shift function $S$) is defined such that $BB(n)$ is the maximum number of steps that can be taken by halting Turing machines with (2 symbols and) $n$ states.

Variants of this function include the “ones function” $\Sigma \colon \mathbb{N} \longrightarrow \mathbb{N}$, giving the maximal number of times that halting Turing machines with 2 symbols and $n$ states print a given one of these two symbols.

Properties

The busy beaver function is non-computable.

Some of its values are known or have been argued to be independent of the ZFC-axioms of set theory [Riebel 2023].

The values of the busy beaver function grow excessively fast with $n$. The first few values are (bounded below by)

(1)$$\begin{array}{ll} BB(1) & = 1 \\ BB(2) & = 6 \\ BB(3) & = 21 \\ BB(4) & = 107 \\ BB(5) & \geq 47,176,870 \\ BB(6) & \geq {}^15 10 \coloneqq 10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10}}}}}}}}}}}}}} \end{array}$$

(from Aaronson 2020 p. 9, 2022)

References

The original article:

• Tibor Radó: On non-computable functions, Bell System Technical Journal 41 3 (1962) 877–884 [doi:10.1002/j.1538-7305.1962.tb00480.x, ark:/13960/t3rv1w56b, pdf, pdf]

Early discussion:

• Allen H. Brady: The Determination of the Value of Rado’s Noncomputable Function $\Sigma(k)$ for Four-State Turing Machines, Mathematics of Computation 40 162 (1983) 647-665 [doi:10.1090/S0025-5718-1983-0689479-6, pdf]

Review:

• Scott Aaronson: The Busy Beaver Frontier, ACM SIGACT News 51 3 (2020) 32-54 [doi:10.1145/3427361.342736, pdf]

• Ling (Esther) Fu, Sarah Pan: The Busy Beaver Problem, MIT Menezes Challenge PRIMES Circle (2022) [pdf]

See also:

• Wikipedia: Busy beaver

• The Busy Beaver Challenge Wiki [web]

On undecidability of values of the busy beaver function:

• Johannes Riebel: The Undecidability of BB(748) – Understanding Gödel’s Incompleteness Theorems, Bachelor Thesis, Augsburg (2023) [pdf]

• Scott Aaronson, Life, blogging, and the Busy Beaver function go on, blog entry (5 July 2023) [web]

• Independence from ZFC, the Busy Beaver Challenge Wiki [web]

For an argument that BB(6) will be hard to find in a technical sense (it requires solving a Collatz-like problem for a candidate TM), see

• Shawn Ligocki, BB(6) is Hard (Antihydra), blog post