The Busy Beaver, the Placid Platypus and other Crazy Creatures

James Harland, School of Science (formerly CS&IT) RMIT

Background Terminology Observant Otter Zany Zoo Blue Bilby Ebony Elephant White Whale Demon Duck of Doom Dreadful Dragons Old version

Observant Otter results Zany Zoo 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 non-blank characters that can be printed by a deterministic Turing machine of a given size.

You can read in this article my take on the status of this problem, which in a nutshell is that we need to revisit the foundations of it in order to be able to document the evidence for what we know about the busy beaver problem.

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.

Observant Otter

As discussed in this paper, the observant otter heuristic seems to be a technique fundamental to solving the busy beaver problem. The detailed version of the results in the paper, together with all the code used, can be found here.

Zany Zoo

One of the key issues in solving the busy beaver and related problems is to generate the appropriate classes of machines. As the number of machines grows very quickly, it is vital to reduce the number of machine as much as possible whilst also ensuring that no potentially appropriate machines are omitted. Detailed discussion on this and other related issues can be found in this paper. The results reported in this paper, together with all the code used, can be found here.

Machine Classes

NameDescription
Blue Bilby This is my name for the class of machines of up to dimension 6, i.e. machines with 2 states and 2 symbols, 3 states and 2 symbols or 2 states and 3 symbols. The bilby is a small and cuddly animal, reflecting that this category does not contain any monster machines.
Ebony Elephant This is my name for the class of machines of dimension 8, i.e. machines with 4 states and 2 symbols, or 2 states and 4 symbols. The elephant is of course a creature larger than humans, but only poses danger under certain circumstances.
White Whale This is my name for the class of machines of dimension 9 or 10, i.e. machines with 3 states and 3 symbols, 5 states and 2 symbols or 2 states and 5 symbols. The whale is a creature which should not be approached by humans without caution and a significant level of technological sophistication.
Demon Duck of Doom This is my name for the class of machines of up to dimension 12, i.e. machines with 6 states and 2 symbols, 4 states and 3 symbols, 3 states and 4 symbols or 2 states and 6 symbols. The Demon Duck of Doom, or Thunderbird, stood over 2.5 metres tall and lived some 15 million years ago, reflecting that the machines in this category are largely unknown, are likely to contain complexities that we have never seen before and cannot really be approached at all at present.

Dreadful Dragons

This is my name for machines with very high productivities. These can be found on Heiner Marxen's website, or on the Observant Otter results page..

Old version

For backwards compatibility, an older version of this page can be found here.