The Busy Beaver, the Placid Platypus and other Crazy Creatures*
James Harland,  School of CS&IT, RMIT
Seminar 13th May, 2005
    *Thanks to Jeanette Holkner, Michael Winikoff and Sandra Uitdenbogerd for assistance with zoological names and descriptions

Introduction
Beaver machines are a particular type of Turing machine:
 Question: For a given number of states, what is the largest number of 1's that can be printed by a beaver machine which halts?

Known busy beavers

      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×10865 ≥ 3×101730
7
 ....
 ....

    Consider that a 6-state machine can be represented in 55 bits  ...  (and 10865 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 2 ⇒ k-state amphibian machine MF : x 1's → F(x)  1's

Consider M: X then MF  then MF where X: blank → x 1's. Note X has x states.

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

Now F(x) ≥ x 2 > 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 ◊

Green (1964): for any computable f,  f(bb(n)) < bb(n+1)

Hopefully this doesn't apply for n = 5, as otherwise for f(m) =  m m we get bb(6) > 4098 4098 ≈ 10 14,804       (!?!?!)

Searching for bb(5) and bb(6) (aka the hunt for the great white whale :-)

How many machines are there?

For n =5 we "only' have to search through 230,400,000,000 = 2.3 ×1011 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:
    
Using equivalences and some other reduction techniques, it seems the number of 5-state candidates is "down" to 69,471,096 ie 6.9 ×107

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

Loop checking 
Of course, loop checking cannot find all loops, but how close can we get?

Code

      
Other  Creatures

Revisit first table above

States
 Name
 Final Ones
 Maximum Ones
Hops
 Diagram
3
 bb3
 6
 6
 14
3
 lb3
 6
 6
 11
3
 ff3
 5
 5
 21
4
 bb4
 13
 13
 107
4
 lb4
 13
 13
 96
5
 m1
 4098
 12,288
 
47,176,870

5
 m2
 4098
   6,144
 
 11,798,826
5
 m3
 4097
 
 23,554,764

5
 m4
 4097
 
11,798,796
5
 m5
 4096
 
11,804,910
5
 m6
 4096
 
11,804,896
5
 m7
 1471
 
  2,358,064

6
 ddd
 1.29×10865
3×101730


n-state machine prints m 1's ⇒

Question: what is the minimum number of states needed to print m 1's?

We call this function the placid platypus which we denote by pp(m).

An n-state machine which prints m 1's thus shows that bb(n) ≥  m  and pp(m) ≤ n.
     pp(m): minimum number of states of a terminating beaver machine which prints n 1's
         ww(m): minimum number of state transitions made by a terminating beaver machine which prints n 1's

n
 1
 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...
pp(n) 1 2 2 2 3 3 4 4 4 4 4 4 4 5? 5? 5? 5? 5? 5? 5? ...
ww(n) 1 1 5 4 7 11 12 14 19 30 40 53 96 ?? ?? ?? ?? ?? ?? ?? ??


Not clear that we can fill in every entry in this table.
Question: Is it true that there is a 5-state machine which prints m 1's for each bb(4) ≤ m ≤ bb(5)?

Note that this is certainly false for the range bb(5) to bb(6).
There are at least 10800 numbers to cover, and "only"  (4 × 7)12  = 232,218,265,089,212,416 = 2.3 × 10 17 machines.

So what is the distribution of placid platypus machines?

Consider how one could print 6 1's.
Name
 		States
 		Ones
Hops

4
 		10
 		30

5
 		10
 		26

4
 		12
 		53

5
 		12
 		49
lb3
 3
 6
 11
int4
 4
 6
 9
int5
 5
 6
 8
rr6
 6
 6
 6


     


These are all equivalent in some sense. Can we generate the others from the 6-state version?

Mysteries
 To Do List