Busy beaver

In computability theory, a busy beaver (from the colloquial expression for "industrious person") is a Turing machine that, when given an initially empty (binary) tape (a string of only 0's), does a lot of work, then halts. The functions defined below, called busy beaver functions, were introduced and their properties proved in 1952 by Tibor Rado. There are two main 'categories':

Σ(n): the largest number of 1's printable by an n-state machine before halting, and
S(n): the largest number of steps taken by an n-state machine before halting.

All machines are started on initially blank tapes and those that do not halt are not candidates.

Both of these functions are uncomputable in general. That they grow faster than any computable functions can be easily shown. Take any computable function f of x. Take a function g that writes that many 1's. We can take 22 states to make a Turing complete Turing machine, add a constant number of states to write the function g to the tape, and add log₂ x states to write x to the tape. Since a constant plus log₂ x is smaller than x, for any large enough x. The busy beaver function of a constant plus log₂ x will be at least as large as f of x, therefore the busy beaver function has grown faster.

A computer which could somehow solve the halting problem would be capable of computing the uncomputable busy beaver function.

Even with only a few states, a Busy Beaver can do very much. At the moment the record 6-state Busy Beaver is over 10⁸⁶⁵ (that is a 1 with 865 zeros) ones produced, using over 10¹⁷³⁰ steps.

The function values for Σ(n) and S(n) are known only for n<5.

In case n=5 there remain about 40 machines with nonregular[1] behavior.

There is an analog to the Σ function for Minsky machines, namely the largest number which can be present in any register on halting, for a given number of instructions. This is a consequence of the Church-Turing thesis.

Trivial proof for uncomputability of S(n) and Σ(n)

Let EvalS denotes a TM, evaluating S(n). Giving a tape with n 1's it will produce S(n) 1's on the tape and then halts. Let Clean denotes a TM, cleaning the sequence of 1's initialy writen on the tape. Let Double denotes a TM, evaluating function n+n. Giving a tape with n 1's it will produce 2n 1's on the tape and then halts.

Let we create a composition Double|EvalS|Clean and n₀ is the number of states of this machine. Let Create_n₀ denotes a TM, creating n₀ 1's on initialy blank tape. This machine may be constructed in trivial manner to have n₀ states (the state i writes 1, moves the head right and go to state i+1, except the state n₀+1, which halts). Let N denotes the summ n₀+n₀.

Let BadS denotes the composition Create_n₀|Double|EvalS|Clean. This machine has N states. Starting at initialy blank tape it first creates a sequence of n₀ 1's and then double it, producing a sequence of N 1's. Then BadS will produce S(N) 1's on tape, and at last it will clear all 1's and then halts. But the last phase of cleaning will continue at least S(N) steps, so the time of working of BadS is strictly greater than S(N), which contradicts to the definition of the function S(n).

The uncomputability of Σ(n) may be proved in a similar way. We must exchange in upper proof the machine EvalS with EvalΣ and Clean with Increment - simple TM, searching for a first 0 on the tape and replacing it with 1.

Examples of lower stage Busy Beavers

These are the first two sets of rules that generate the biggest Sigma(n)... Result Key: (starts here, goes to here):

1-state:

	A
1	N/A
0	1-Halt

Result: 0 0 1 0 0 (one "1" total)

2-state:

	A	B
1	1B-Left	1-Halt
0	1B-Right	1A-Left

Result: 0 0 1 1 1 1 0 0 (four "1"s total)

External links

The page of Heiner Marxen, who, with Jürgen Buntrock, found the above-mentioned record for a 6-state Turing machine.

The page of [2] Penousal Machado's Genetic Beaver Project - which uses Evolutionary Computation to find new candidates to the Busy Beaver Problem