Busy Beaver talk

Gamekeeping for the Zany Zoo: How to Hunt Busy Beavers, Placid Platypodes* and other Alliterative Animals
James Harland, School of CS&IT, RMIT
Seminar at CS&IT, RMIT University 11th August, 2006

^*There is no universally accepted plural for "platypus". This is one possibility; others include "platypuses", "platypode" and "platypus". The once-common "platypi" is now deprecated.

Introduction
Beaver machines are a particular type of Turing machine:

Deterministic (at most one transition for any state and input symbol)

Two-way infinite tape

Tape alphabet is only blank (B) and 1

Initially tape is entirely blank

Single halt state

Question (busy beaver): For a given number of states, what is the largest number of 1's that can be printed by a beaver machine which halts?

Question (placid platypus): For a given number of 1's, what is the smallest number of states required to print them by a beaver machine which halts?

Known busy beavers

Cases n = 1,2,3 solved by Lin and Rado in 1960's

Case n = 4 solved by Brady in 1970's

Cases n = 5,6 had some monster machines found in 1990's and 2000's, but still open

     bb(n): maximum number of 1's printed by a terminating beaver machine with n states (often written Σ(n) )
          ff(n): maximum number of state transitions made by a terminating beaver machine with n states (often written S(n))
          prod(M): number of 1's printed by machine M (undefined if M does not halt)

    Hence bb(n) is the maximum value of prod(M) for all n-state machines M.
    Naturally ff(n) ≥ bb(n) and is typically much larger. Possible that the values of bb(n) and ff(n) arise from different machines.

n	bb(n)	ff(n)
1	1	1
2	4	6
3	6	21
4	13	107
5	≥ 4098	≥ 47,176,870
6	≥ 1.29×10⁸⁶⁵	≥ 3×10¹⁷³⁰
7	....	....

Consider that a 6-state machine can be represented in 55 bits ... (and 10⁸⁶⁵takes about 2,800 bits)

3-state busy beaver	4-state busy beaver

5-state busy beaver candidate	6-state busy beaver candidate

Non-computability

The busy beaver function is non-computable, because it grows faster than any computable function!

Proof: Let f be any computable function.
f computable ⇒ so is F(x) = Σ _{0 ≤ i ≤ x} f(i) + i ² ⇒ k-state machine M_{F :}x 1's → F(x) 1's

Consider M: X then M_Fthen M_Fwhere X: blank → x 1's. Note X has x states.

M behaves as follows:

M first writes x 1's
M mimics M_F, writing F(x) 1's on the tape
M mimics M_F again, writing F(F(x)) 1's on the tape

M has x + 2k states ⇒bb(n+2k) ≥ 1's output by M = x + F(x) + F(F(x))

Now F(x) ≥ x ²> x + 2k for x > m, and F(x) > F(y) when x > y, and so F(F(x)) > F(x+2k) > f(x+2k)

So bb(x+2k) ≥ x + F(x) + F(F(x)) > F(F(x)) > F(x+2k) > f(x+2k)

Hence, as f was arbitrary, bb is not computable ◊

Searching for bb(n)

How many machines are there?

n-state machine, 2n transitions, 2 outputs, 2 directions and n+1 possible new states ⇒ (4 (n+1)) ²ⁿ
only ever one halt state ⇒2n × (4n) ^2n-1
fix first transition (output 1, direction R, state 2, not halt) ⇒(2n-1) × (4n)^2n-2

For n =5 we "only' have to search through 230,400,000,000 = 2.3 ×10¹¹machines ...

Naive generate and test won't work; the trick is how to incorporate the test into the generation.

Input	1	2	3	4	5
B	O1 = 1, D1 = R, N1 = 2	not (D3 = R, N3 = 2), N3 ≠ h	O5, D5, N5	O7, D7, N7	O9, D9, N9
1	O2, D2, N2	O4, D4, N4	O6, D6, N6	O8, D8, N8	O10, D10, N10

Some "global" constraints can be used as well, such as avoiding N3 = 3, D3 = R, N5 = 2, D5 = R.

Tree normal form:

emulate machine as the transitions are generated
add the halt state only when there is only one "slot" left
generate states in numerical order
detect loops as early as possible

Loop detection is critical! Mining the data for the 117,440,512 machines with 4 states:

ones	5	6	7	8	9	10	11	12	13
machines	73,617	13,029	1981	475	79	13	6	5	2

89,207 machines terminate and print at least 5 1's
only 2,561 machines terminate and print more 1's than the 3-state busy beaver
loops abound!

Looping machines (or who's who in the zoo :-)

Machine	Description	Diagram
ignoble iguana	can be ignored in the search
perennial pigeon	repeats a configuration
road runner	moves to infinity
phlegmatic phoenix	makes tape blank
meandering meerkat	cannot execute halt transition
dizzy duck	"travelling loop"

What about remaining cases?

.... 11{C}1 → ... 11{C}111 → ... 11{C}11111 ...

Form conjecture that 11{C} 1 (11)^N → 11{C} 111(11)^N

Then compute from state 11{C} 1 (11)^N to state 11{C} 111(11)^N on hypothetical engine
To compute with L {S} I^NR:

{S}IX → O{S}X --- can directly transform L {S} I^NR to L O^N {S} R wild wombat
L {S}IX → NewL {S}X --- make this L2.L1 {S}I^NR to L2.(L3)^N.L1 {S} R slitering snake
L {S}I I^N R → NewL {S} I^N NewR --- make this L2.L1 {S}I^NR to L2.(L3)^N.L1 {S} I NewR maniacal monkey

Code

currently about 5,000 lines of Ciao Prolog ( around half of which is redundant)

will be cleaned up and published by the end of August

close to naive emulation seems fine

can do all 5-state monsters within about 1 minute at worst

wild wombat, slithery snake and manical monkey all implemented (but last one may be still a little buggy)

The Blue Bilby, the Ebony Elephant, the White Whale and the Demon Duck of Doom

Name	States	Machines	Status
Blue Bilby	3	1,720	24 wild wombats, 2 slithery snakes
Ebony Elephant	4	278,570	some maniacal monkeys, some killer kangaroos and monster dizzy ducks, 53 machines unclassified
White Whale	5	69,471,096	monsters abound
Demon Duck of Doom	6	???	need better weapons

Killer Kangaroo

1⁶{D}0 →... 1¹⁸{D}0 → ... 1⁴²{D}0 → ... 1⁹⁰{D}0 → ...
Conjectures are simple enough, but the hypothetical engine needs work ...

Current State of the Placid Platypus

Machines exist for productivities 1-73, 75-83, 87-91, 99, 112, 501, 1471, 1915, 4096, 4097, 4098 with minor variants for 46, 48, 50, 75, 77, 80, 82, 90 ...

Mysteries