The busy beaver — a concretely uncomputable function

Parent: famous-machines

Radó (1962): among all n-state, 2-symbol Turing machines that halt when started on a blank tape, how long can one run?

Busy beaver

S(n) = the maximum number of steps taken by any halting n-state 2-symbol machine on a blank tape (the twin Σ(n) counts 1s left on the tape).

It is uncomputable — and why

Theorem

S(n) grows faster than every computable function; S is not computable.

Proof

If S were computable, halting would be decidable: to test whether an n-state machine M halts on blank, run it for S(n)+1 steps — if it hasn't halted by then, no halting machine of its size runs that long, so M never halts. That decides halting (history) — contradiction. And S dominates any computable f, else f would give such a bound. ∎

The values (a wall appears fast)

S(1)=1, S(2)=6, S(3)=21, S(4)=107, and S(5) = 47,176,870 — the 5-state case was only settled in 2024 (the bbchallenge collaboration). S(6) is already astronomically large (known lower bounds are towers of exponentials) and open. Nudging n by one leaps past what's provable.

How the small ones are found (by hand)

S(n) is found by exhaustive search: enumerate all n-state 2-symbol machines (finitely many), simulate each on the blank tape, keep the halters, take the max steps. The genuinely hard part is proving the non-halters never halt — that's why S(5) took until 2024. For n = 1, 2 it's tiny:

S(1) = 1. One working state A (plus halt H). The only way to halt is on the first read: A,0 → 1,R,H — write a 1, halt. 1 step, one 1. (Any rule that stays in A loops forever.) So S(1)=1, Σ(1)=1.

S(2) = 6. The champion (states A, B, halt H):

        read 0      read 1
  A:    1,R,B       1,L,B
  B:    1,L,A       1,R,H

Trace from the all-blank tape (start state A, head at cell 0):

step	state	reads	rule applied	action
1	A	0	`A,0 = 1,R,B`	write 1, move R, → B
2	B	0	`B,0 = 1,L,A`	write 1, move L, → A
3	A	1	`A,1 = 1,L,B`	write 1, move L, → B
4	B	0	`B,0 = 1,L,A`	write 1, move L, → A
5	A	0	`A,0 = 1,R,B`	write 1, move R, → B
6	B	1	`B,1 = 1,R,H`	write 1, move R, HALT

Six steps, and the tape ends holding four 1s → S(2)=6, Σ(2)=4. (This particular machine is the maximizer; every other halting 2-state machine stops sooner.)

Why it matters

The busy beaver is the concrete face of the uncomputable horizon: "wait long enough and you'll know if it halts" is true, but the waiting time S(n) is uncomputable — you cannot know how long is long enough. It also pins the edge of provability: knowing S(n) for large n would settle famous open problems (a machine can be built to halt iff, say, Goldbach fails), so S(n) is unprovable in ZFC beyond some point.