Busy Beaver

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

A busy beaver is a Turing machine that, when provided with a blank tape, does a lot of work. Formally, it is an -state -color Turing machine started on an initially blank tape that writes a maximum number of 1s or moves the head a maximum number before halting. This Demonstration shows most of the known values of historical and current busy beaver champions as discovered by several people over the last four decades. There are known values up to four states for two-color machines and explicit constructions give exact or lower bounds for other state and color pairs.

Contributed by: Hector Zenil (March 2011)
Open content licensed under CC BY-NC-SA


Snapshots


Details

Most of the busy beaver values for and remain unreachable since they are noncomputable functions. The number of machines to explore (as well as their sizes) grows exponentially too fast. However, some values for a fixed-input empty tape and some small number of states and colors can be calculated.

The purple cells show the head position at each step. If either or appears with a sign, the Turing machine being displayed is only a busy beaver candidate. For a fixed (, ) size, if a busy beaver is known in (, ) it will be the first rule for the (, ) selection with the rest, if any, of the previous historical busy beaver candidates. If the busy beaver is unknown for that size space selection, then even the first rule will have a sign.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send