The Busy Beaver, the Placid Platypus and other Crazy Creatures*
James Harland,  School of CS&IT, RMIT
Seminar at CSSE, Melbourne University  16th August, 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 machine MF : x 1's → F(x)  1's


Consider M: X then
Mthen 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

Preliminary Results for n=5 (or where is the white whale? :-)

Status
%
halts
31.9
cycle
5.2
"growing"
41.3
blank
21.5
unclassified
0.1


    Note that classifying 99.9%  of the machines leaves "only" 0.1% or around 65,000 to classify ....
   Work is underway on an inductive prover for non-termination of the form

                        {C}  1N
→  {C} 1N+3


Loop checking 
Of course, we may not be able to find all loops automatically, 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 ≤41 ≤45 ≤50 ≤57 ≤63 ≤43 ≤63


n 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
pp(n) 5 5 5 5 5 5 5 5 ? ? 5
5 5 ? 5 5 ? ? 5 ?
ww(n) ≤72 ≤98 ≤69 ≤223 ≤520 ≤298 ≤343 ≤102 ≤?? ≤?? ≤512 ≤427 ≤559 ≤?? ≤496 ≤494 ≤?? ≤?? ≤856 ≤??

The table below gives the best 5-state machine to print the given number of ones (which coincides with pp(n) for n >
14).

n
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
min hops
8
12 13
16
19
23
29
35
41
45
50
57
63
43
62
72
98
69
223
520
298
343
102

max hops 216 159 276 262 186
312
226 349 314
298 492 420 296 189 611
419
642
855 488
825
949
923

n 31 32 33 34 35 36 37 38 39 40
min hops 619 632 559
496 808



max hops 619 632 559
691 808




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?

Equivalence (??)

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