Busy Beaver

The Busy Beaver, the Placid Platypus and other Crazy Creatures

James Harland, School of CS&IT RMIT

Background Terminology Blue Bilby Ebony Elephant White Whale Code Placid Platypus Monsters Papers Talks Observant Otter results

Background

The busy beaver problem is a well-known example of a non-computable function. There are many good references on it, including Heiner Marxen's web page. In a nutshell, the busy beaver problem is to find the largest number of 1's that can be printed by a deterministic Turing machine of a given size. My work on this problem goes in a different direction to many, in that it is about exploring interesting properties of 5-state (and, later on, 6-state machines), rather than searching for champion machines per se.

Terminology

The name "busy beaver" sent me down a zoological and alliterative alley, which I have no intention of leaving! Hence rather than denoting the busy beaver function as the traditional Σ(n) and the number-of-transitions function as S(n), I have rather perversely denoted these as bb(n) and ff(n) respectively (for busy beaver and frantic frog). When it came to finding a name for the "inverse" busy beaver, the natural name seemed to be the placid platypus. A platypus is an Australian monotreme, and hence is native to the southern hemisphere (as the beaver is to the north). The platypus is also known for its shy and retiring nature. Having gone this far, it was then only a small step to denote the corresponding number-of-transitions function as the weary wombat.

Hence, when naming things, alliterative animals tend to get used. In particular, we denote the search for beaver machines with 3, 4, and 5 states as the quest for the blue bilby, ebony elephant, and the white whale respectively. We refer to the search for 6 state machines as the quest for the demon duck of doom, a term used to describe an Australian Thunderbird from the megafauna era thousands of years ago. To find a particular name, please see the Zany Zoo's Glossary.

Quest for the Blue Bilby (n = 1,2,3)

The values of the busy beaver function for n = 1, 2, 3 were determined by Lin and Rado in the 1960's. My particular interest is not so much in the value of the functions, but what the search space looks like. A summary of the search results is below.

States Machines Termites Iguanas Ducks Wombats Snakes Monkeys Kangaroos Unicorns
1 1 1 0 0 0 0 0 0 0
2 11 7 2 2 0 0 0 0 0
3 2,112 903 436 747 24 2 0 0 0

Quest for the Ebony Elelphant (n = 4)

The value of the busy beaver function for n = 4 was determined by Brady in the 1970's. My particular interest is not so much in the value of the function, but what the search space looks like. In addition, I am interested in determining whether or not this case is decidable. In other words, can the number of unicorns in the table below be reduced to 0? I still have to implement the procedure to correctly recognise killer kangaroos, but I believe it is possible to do so.

A summary of the current results is below.

States Machines Termites Iguanas Ducks Wombats Snakes Monkeys Kangaroos Unicorns
1 1 1 0 0 0 0 0 0 0
2 11 7 2 2 0 0 0 0 0
3 2,112 903 436 747 24 2 0 0 0
4 350,440 134,048 84,482 126,735 3,292 1,803 18 41 21

Quest for the White Whale (n = 5)

Code

The code used to derive these results can be found here. Please note though that this is very much a backend system; any pretence to nice interfaces and general usability issues are long gone! There is probably a project in the development of something vaguely usable from this backend for an appropriately qualified enthusiast ...

The Placid Platypus

The busy beaver function may be thought of as seeking the maximum number of 1's that can be printed for a given number of states. We denote this function as bb(n). Hence an n-state machine which prints m 1's shows that bb(n) ≥ m, i.e. that at least m 1's can be printed by an n-state machine. Alternatively we may view this as stating that at most n states are needed to print m 1's. A natural dual problem is then to determine the minimum number of states required to print a given number of 1's. We call this function the placid platypus, and denote it by pp(n). An n-state machine that prints m 1's thus shows both that bb(n) ≥ m and pp(m) ≤ n. Analagously to the busy beaver case, we also consider the minimum number of transitions required to print m 1's; we denote this function as the weary wombat , or ww(n), which is the minimum number of state transitions made by a terminating machine which prints n 1's.

We then ask whether it is true that there is a 5-state machine which prints m 1's for each bb(4) ≤ m ≤ bb(5). Given that bb(5) ≥ 4098, this seems unlikely; however, the interesting part is the distribution of the numbers for which such a 5-state machine exists.
Our current results are summarised in the tables below.

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	5	5	5	5	5	5
ww(n)	≤72	≤98	≤69	≤223	≤155	≤298	≤343	≤102	≤1597	≤299	≤339	≤427	≤383	≤438	≤496	≤494	≤468	≤1038	≤856	≤446

n	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60
pp(n)	5	5	5	5	5	-	5	-	5	-	5	5	5	5	5	5	5	5	5	5
ww(n)	≤1181	≤589	≤1422	≤2166	≤1358	-	≤2135	-	≤1968	-	≤1988	≤1986	≤2767	≤2861	≤2217	≤2136	≤1887	≤2456	≤5108	≤2566

n	61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80
pp(n)	5	5	5	5	5	5	5	5	5	5	5	5	5	-	-	5	-	5	5	-
ww(n)	≤3720	≤4345	≤2398	≤3104	≤4263	≤3355	≤3858	≤3630	≤6956	≤2821	≤3545	≤7383	≤5167	-	-	≤4172	-	≤7036	≤4948	-

n	81	83	87	88	89	91	99	112	501	1471	1915	4096	4097	4098
pp(n)	5	5	5	5	5	5	5	5	5	5	5	5	5	5
ww(n)	≤5230	≤5067	≤3189	≤7706	≤5685	≤8245	≤2411	≤6147	≤134,467	≤2,358,064	≤2,133,492	≤11,804,896	≤11,798,796	≤11,798,826

Put another way: what is the smallest m such that there is no 5-state machine which prints m 1's? More generally, what is the distribution of placid platypus machines? What is the largest interval [m1,m2] such that a platypus machine exists for each value in the interval? What is the largest interval [m1,m2] such that a platypus machine does not exist for each value in the interval?
Note that it is certainly false that there is a 6-state machine which prints m 1's for each m between bb(5)+1 and bb(6). As it is known that bb(6) ≥ 1.29×10⁸⁶⁵ there simply aren't enough machines to cover all the possibilities.

Currently I am performing a search of the 5-state machines to answer such questions. In this case it is not a matter of finding the champion busy beaver machine (although that is certainly of interest), but of exploring the properties of this class of machines; if you like, it is about the machines per se, and not just about the function defined via them.

Note that the missing machines for the productivities 46, 48, 50, 75, 77, 80, 82, 86, 90, 98, and 111 can be filled by a minor tweak for the machines of productivity one greater. For example, the machine with productivity 47 terminates, as do all machines in this search, with the output of the final transition being 1. This means that to get a machine of productivity 46 instead, all we need to do is to make the output of the final transition 0. Hence the first gap of any significance is that for 74 (although, of course, it would be more satisfying to find a machine with productivity 46 directly, as it were).

5-state monsters

Here is the current list of 5-state monsters:

productivity	maximum	transitions	final tape configuration	machine(A0 A1 B0 B1 C0 C1 D0 D1 E0 E1)	diagram
4,098	12,288	47,176,870	101(001)⁴⁰⁹⁵1	1RB 1LC 1RC 1RB 1RD 0LE 1LA 1LD 1RH 0LA	Here
4,098	6,144	11,798,826	1(110)²⁰⁴⁷ 111	1RB 1RA 1LC 1LB 1RA 1LD 1RA 1LE 1RH 0LC	Here
4,097	6,143	23,554,764	1(110)²⁰⁴⁸	1RB 0LD 1LC 1RD 1LA 1LC 1RH 1RE 1RA 0RB	Here
4,097	6,143	11,798,796	1(101)²⁰⁴⁷11	1RB 1RA 1LC 1RD 1LA 1LC 1RH 0RE 1LC 1RB	Here
4,096	6,143	11,804,910	1(011)²⁰⁴⁷01	1RB 1RA 1LC 0RD 1LA 1LC 1RH 1RE 0LE 1RB	Here
4,096	6,143	11,804,896	1(011)²⁰⁴⁷01	1RB 1RA 1LC 0RD 1LA 1LC 1RH 1RE 1LC 1RB	Here
1,915	1,916	2,133,492	1(0101)⁹⁵⁴011	1RB 1LC 0LA 0LD 1LA 1RH 1LB 1RE 0RD 0RB	Here
1,471	1,474	2,358,064	(1110)⁴⁸⁸101010101011	1RB 1RD 1LC 0LE 0RA 0LB 1RE 1RH 1LC 1RC	Here
501	501	134,467	11(0111)¹⁶⁶1	1RB BLC 1RC 1RD 1LA BRB BRE 1RH 1LC 1RA	Here

Papers

James Harland, The Busy Beaver, the Placid Platypus and Other Crazy Creatures, Proceedings of Computing: the Australasian Theory Symposium (CATS'06), Hobart, January, 2006.
James Harland, Analysis of Busy Beaver Machines via Inductive Proofs, Proceedings of Computing: the Australasian Theory Symposium (CATS'07), Ballarat, January, 2007.

Talks