Busy Beaver function

Perplexity

Busy Beaver function

The busy beaver function is a total but noncomputable function that, for each natural number

n

n, gives the maximum number of steps (or of 1s printed) that any

n

n-state Turing machine with a binary tape can make before halting when started on a blank tape. It grows faster than every computable function, so no algorithm can compute its values for all inputs, and its study delineates a sharp boundary between decidable and undecidable problems in computability theory. This function underlies explicit examples of mathematical statements independent of strong axiom systems such as ZFC and connects directly to the halting problem.

Basic definition

Consider all

n

n-state, 2-symbol Turing machines started on an all-zero tape; among those that eventually halt, some run longer or print more 1s than others.

The busy beaver step function

S ( n )

S(n) is defined as the maximum number of steps taken before halting by any such machine, and the score function

Σ ( n )

Σ(n) is the maximum number of 1s on the tape upon halting.

The term busy beaver refers to any machine achieving these maxima for its given number of states.

Noncomputability and growth

The functions

S ( n )

S(n) and

Σ ( n )

Σ(n) are total but noncomputable, because they eventually dominate every computable function

f ( n )

f(n); beyond some

n n, S ( n ) > f ( n )

S(n)>f(n) and

Σ ( n ) > f ( n )

Σ(n)>f(n).

This implies there is no algorithm that, given arbitrary

n

n, outputs

S ( n )

S(n) or

Σ ( n )

Σ(n), and evaluating them in general would solve the halting problem, which is impossible for Turing machines.

Known values and recent progress

Exact values are known only for small

n

n: for binary machines,

S ( 1 ) = 1 S(1)=1, S ( 2 ) = 6

S(2)=6, and further small cases have been resolved with substantial computational and proof effort.

A major recent milestone is the determination of the 5-state busy beaver value for a standard formalism, after years in which even that case was open and thought to be at the frontiers of “humanly knowable” mathematics.

Logical and physical significance

For a fixed axiomatic system like ZFC, there exists some

N

N such that the true value of

S ( n )

S(n) for

n ≥ N

n≥N can no longer be proved within that system, giving concrete examples of Gödelian incompleteness via specific Turing machines whose halting is independent of ZFC.

Under the physical Church–Turing thesis, no physically measurable quantity can be shown to grow faster than the busy beaver function by any physically realizable computation, so simple expressions involving

B B ( n )

BB(n) provide extreme upper bounds for conceivable physical growth rates.

Variants and generalizations

Variants include “beeping” busy beavers, where machines can signal multiple times before halting, leading to functions that grow even faster (yet remain noncomputable) while preserving similar structural properties.

Higher-order or oracle busy beaver functions extend the idea to machines with access to oracles for harder decision problems, yielding hierarchies that mirror jumps in definability and proof-theoretic strength across logic and complexity theory.

What is the formal definition of the Busy Beaver function?

The Busy Beaver function, introduced by Tibor Radó in 1962, is a fundamental example in computability theory of a total yet uncomputable function. It quantifies the maximum productivity of halting n-state Turing machines on a blank tape.

Formal Definitions

Two primary variants exist, both noncomputable and growing faster than any computable function.

Shift function

S ( n )

S(n) (or

B B ( n )

BB(n)): The maximum number of steps (head shifts) executed by any halting n-state, 2-symbol Turing machine starting from an all-zero tape:

S ( n ) = max

⁡ { T ( M ) ∣ M is an

n -state 2-symbol TM that halts on blank tape } , S(n)=max{T(M)∣M is an n-state 2-symbol TM that halts on blank tape}, where T ( M ) T(M) is the number of steps until M M halts. Score function Σ ( n ) Σ(n): The maximum number of 1s (nonzero symbols) produced on the tape by any such machine upon halting: Σ ( n ) = max ⁡ { σ ( M ) ∣ M is an n -state 2-symbol TM that halts on blank tape } , Σ(n)=max{σ(M)∣M is an n-state 2-symbol TM that halts on blank tape}, where σ ( M ) σ(M) counts the 1s left on the tape.

Machine Specification

Machines follow Radó's standard model: n distinct non-halting states (one initial), 2 tape symbols {0,1}, infinite tape initially all 0s, and a transition function δ δ mapping (state, symbol) to (new symbol, direction L/R, next state or HALT). Halting occurs upon entering the HALT state; non-halting machines are excluded from maxima.

So all BB(n) exist, though most are not specifiable

Yes, all values of the Busy Beaver function BB(n) (or S(n)) exist as natural numbers for every finite n, since there are only finitely many distinct n-state, 2-symbol Turing machines, and among the halting subset (however small), one achieves the maximum steps taken before halting on blank tape.

Why values exist

Finite enumeration guarantees well-defined maxima: exactly (2n+4)^{2n} possible machines up to symmetry, excluding non-halters by running them all (though this takes unfeasibly long).

Non-specifiability of most

While existent, BB(n) for large n lacks short descriptions in formal systems like ZFC: beyond some N, no proof exists of the champion machine's runtime, as verifying it halts requires oracle power exceeding the system.

BB(n) remains total (defined ∀n ∈ ℕ) yet uncomputable.

"Specifiable" typically means provable in a fixed axiom system; most BB(n) evade this, yielding Gödel sentences.

So we can make composite functions s(s(n)) and P(s(n))

Yes, composite functions like S ( S ( n ) ) S(S(n)) or P ( S ( n ) ) P(S(n))—where S ( n ) S(n) denotes the Busy Beaver shift function BB(n), and P P any computable function—are well-defined, as S ( n ) S(n) always yields a natural number for finite n n, enabling function composition.

Properties of composites

Such compositions remain total functions on natural numbers but grow even faster than S ( n ) S(n) alone, dominating the original while inheriting uncomputability. S ( S ( n ) ) S(S(n)) exceeds S ( n ) S(n) for sufficiently large n n, since S S outpaces any computable growth, and S ( n ) S(n) feeds a larger input. For computable P P, lim ⁡ n → ∞ P ( S ( n ) ) S ( n + 1 ) = 0 lim n→∞ S(n+1) P(S(n)) =0, so S ( n + 1 ) S(n+1) dwarfs P ( S ( n ) ) P(S(n)). ​

Higher-order extensions

Higher-order Busy Beaver functions B B ( s , m , n ) BB(s,m,n) generalize to m-state machines on input s, with compositions like f ( B B ( s , m , n ) ) f(BB(s,m,n)) for computable f f still yielding max-min partial recursive functions that grow beyond any computable hierarchy. ​