2 of 18

Busy Beaver

Radó's Sigma Function: ∑(n,k)

A n-state k-symbol Turing Machine can write no more than ∑(n,k) symbols to the tape in S(n,k) steps before halting.

Assumptions

Turing Machine starts with blank tape (all zeros)

n = number of states in the Turing Machine

TM must halt

k Symbols ( often k=2: 0 & 1 ) on the tape

S(n,k) is the number of steps the machine takes

∑(n,k) is the number of symbols written to the tape

3 of 18

For n states and k symbols: (2k(n + 1))^kn

possible Turing Machines

4 of 18

Busy Beaver - n = 1 state

5 of 18

Busy Beaver - n = 1 state

∑(1) = 1

6 of 18

Busy Beaver - n = 2 states

7 of 18

Busy Beaver - n = 2 states

0 State A�10 State B�11 State A�0111 State B�1111 State B�1111 Halt

∑(2) = 4

8 of 18

Busy Beaver - n = 3

9 of 18

Busy Beaver - Known Values

S(5) was finally confirmed in 2024 by bbchallenge.org

10 of 18

Busy Beaver - Ms We Know About

11 of 18

∑(n) is Noncomputable - Proof Sketch

We defined ∑(n) as the maximum number of symbols an n-state Turing Machine can write. Assume for contradiction that a Turing Machine E exists, with a fixed number of states e, that given n on the tape, outputs the number ∑(n), both in unary.

We can derive a contradiction by wiring in two additional TMs:

Double doubles the number on the tape, taking d states (d<=3, see next slide).

Write writes w=d+e+d ones onto the tape, using w states.

Write+Double+E+Double thus has w + d + e + d = 2w states, and its output is 2*∑(2w).

This means it writes more than ∑(2w) output, but it only has 2w states! This contradiction proves no fixed Turing Machine E can exist to compute ∑(n) for all n (in particular, for n > e).

12 of 18

∑(n) is Noncomputable - d=3 Unary Doubling Function

; Double the count of 1's on tape (unary). Start state s

; Start on top of the first 1.

s 1 _ l add1

s _ _ l halt-accept

add1 _ 1 r findspace

add1 1 1 l add1

findspace _ 1 r s

findspace 1 1 r findspace

13 of 18

Busy Beaver Solution => Halting Problem Solution

If Busy Beaver solver S(n) existed

Then you could build a Halting Problem solution:

Any TM that runs for more than S(n) steps must be in an infinite loop.

(This may take eons, but it's known and finite!)

14 of 18

Halting Problem Solution => Busy Beaver Solution

If Halting Problem solution existed:

Then a Busy Beaver solution would exist:

for (each possible Turing Machine TM with n states)

if (Halts(TM))

∑=max(∑,TM.run().tape.length);

15 of 18

Busy Beaver Implications

∑(n) grows very quickly–faster than exponential, then faster than iterated exponential, then *faster than that*.
Turing Machines can get "smarter" very quickly as you add states, or equivalently, add pre-initialized tape data
We know ∑(4), so all of human civilization is at least as smart as a 4-state binary Turing Machine.

(For some 5-state Turing Machines, we still have a few doubts.)

16 of 18

Busy Beaver: Global Leaderboard

http://www.logique.jussieu.fr/~michel/bbc.html

17 of 18

Busy Beaver: Online Short Example

https://lawlorcode.com/2024/turing_pp.html

; Brady (1983) maximum 4-state Turing Machine

; Start state is 'a', initial tape is empty

; R W M State

a _ 1 r b

a 1 1 l b

b _ 1 l a

b 1 _ l c

c _ 1 r halt-accept

c 1 1 l d

d _ 1 r d

d 1 _ r a

18 of 18

Busy Beaver: Online Looong Example

https://lawlorcode.com/2024/turing_pp.html

; Marxen and Buntrock (1990), maximum(?) 5-state Turing Machine

; Start state is 'a', initial tape is empty

; R W M State

a _ 1 r b

a 1 1 l c

b _ 1 r c

b 1 1 r b

c _ 1 r d

c 1 _ l e

d _ 1 l a

d 1 1 l d

e _ 1 r halt-accept

e 1 _ l a