Busy Beaver

The busy beaver game is a competition to find an

-state Turing machine that either leaves the largest number of 1s on its tape or makes the largest number of head movements before halting. 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 a maximum number

of head movements 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 4 states for 2-color machines and explicit constructions give exact or lower bounds for other state and color pairs.

Contributed by: Hector Zenil

Show Initialization Code

(35 lines omitted)

Most of the busy beaver values for

and

remain unreachable since they are non-computable functions and the number of machines to explore as well as their sizes grow exponentially too fast. However, some values for a fixed input empty tape and some small number of states and colors can be calculated.