Busy beaver

In computability theory, a busy beaver (from the colloquial expression for "industrious person") is a Turing machine (TM) that, when given an empty tape (a string of only 0's), does a lot of work, then halts. Originally the only TMs considered were those using only 2 symbols (0 and 1).

The two functions defined below, called busy beaver functions, were introduced in 1962 by Tibor Rado as simple examples of noncomputable functions:

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

Both of these functions are noncomputable, because they grow faster than any computable function.

Even with only a few states, a Busy Beaver can do very much.

The current 5-state Busy Beaver champion produces 4,098 ones, using 47,176,870 steps.

At the moment the record 6-state Busy Beaver produces over 10⁸⁶⁵ ones, 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 (http://skelet.ludost.net/bb/nreg.html) behavior.

Contents

1 Generalizations 2 Trivial proof for uncomputability of S(n) and Σ(n) 3 Examples of busy beaver Turing machines 4 Exact values and lower bounds for some S(n,m) and Σ(n,m) 5 External links

Generalizations

For any model of computations there exist simple analogs for Busy Beaver.

The generalization to Turing machines with n states and m symbols defines the following generalized busy beaver functions:

1. Σ(n,m): the largest number of non-zeros printable by an n-state, m-symbol machine before halting, and
2. S(n,m): the largest number of steps taken by an n-state, m-symbol machine before halting.

The longest running 3-state 3-symbol machine found so far (found by Allen Brady) runs 92,649,163 steps before halting.

The longest running 6-state, 2-symbol machine which has the additional property of reversing the tape value at each step produces 6,147 ones after 47,339,970 steps. So S_RTM(6) ≥ 47,339,970 and Σ_RTM(6) ≥ 6,147.

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)

Suppose that S(n) is a computable function and let EvalS denote a TM, evaluating S(n). Given a tape with n 1s it will produce S(n) 1's on the tape and then halt. Let Clean denote a TM, cleaning the sequence of 1s initially written on the tape. Let Double denote a TM, evaluating function n + n. Given a tape with n 1s it will produce 2n 1s on the tape and then halt.

Let us create the composition Double|EvalS|Clean and let n₀ be the number of states of this machine. Let Create_n₀ denote a TM, creating n₀ 1s on an initially blank tape. This machine may be constructed in a trivial manner to have n₀ states (the state i writes 1, moves the head right and switches to state i + 1, except the state n₀, which halts). Let N denotes the sum n₀ + n₀.

Let BadS denote the composition Create_n₀|Double|EvalS|Clean. Notice that this machine has N states. Starting with an initially blank tape it first creates a sequence of n₀ 1s and then doubles it, producing a sequence of N 1s. Then BadS will produce S(N) 1s on tape, and at last it will clear all 1's and then halt. But the 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. In the above proof, one must exchange the machine EvalS with EvalΣ and Clean with Increment - a simple TM, searching for a first 0 on the tape and replacing it with 1.

Examples of busy beaver Turing machines

These are tables of rules for Turing machines that generate Σ(1), Σ(2), and the best known lower bound for Σ(6) and S(6). The latter entry is listed because it is truly remarkable.

In the tables, the columns represent the current state and the rows represent the current symbol read from the tape. The table entries indicate the symbol to write onto the tape, the new state, and the direction to move over the tape.

Each machine begins in state A with an infinite tape that contains all 0's. Thus, the initial symbol read from the tape is a 0.

Result Key: (starts here, goes to here)

1-state, 2-symbol:

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

2-state, 2-symbol:

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

6-state, 2-symbol:

Result: ~1.291 x 10⁸⁶⁵ ones in ~3.002 x 10¹⁷³⁰ steps. See Heiner Marxen's (http://drb9.drb.insel.de/~heiner/) list of 6 state, 2 symbol Turing machines (http://www.drb.insel.de/~heiner/BB/bb-6list) for the exact values of these lower bounds.

Exact values and lower bounds for some S(n,m) and Σ(n,m)

The following table lists the exact values and some known lower bounds for S(n,m) and Σ(n,m) for the generalized busy beaver problems. Known exact values are shown in bold face type and known lower bounds are preceded by a greater than or equal to (≥) symbol. Note: entries listed as "???" are bounded by the maximum of all entries to left and above but have not been explicitly investigated by anyone to date.

The Turing machines that achieve these values are available on either Heiner Marxen's (http://www.drb.insel.de/~heiner/BB/) and Pascal Michel's (http://www.logique.jussieu.fr/~michel/ha.html) WWW pages. Each of these WWW sites also contains some analysis of the Turing machines and references to the proofs of the exact values.

Values of S(n,m):

Values of Σ(n,m):

External links

• The page of Heiner Marxen (http://www.drb.insel.de/~heiner/BB/), who, with Jürgen Buntrock, found the above-mentioned records for a 5 and 6-state Turing machine.
• Pascal Michel's Historical survey (http://www.logique.jussieu.fr/~michel/ha.html) of Busy Beaver results which also contains best results and some analysis.
• The page of Penousal Machado's Genetic Beaver Project (http://eden.dei.uc.pt/~machado/research/bb/BB.html) uses Evolutionary Computation to find new candidates to the Busy Beaver Problem
• Definition of the class RTM (http://skelet.ludost.net/bb/RTM.htm) - Reversal Turing Machines, simple and strong subclass of the TMs.
• The "Millennium Attack (http://www.cs.rpi.edu/~kelleo/busybeaver/)" at the Rensselaer RAIR Lab on the Busy Beaver Problem.
• Aaronson, Scott (1999), Who can name the biggest number? (http://www.scottaaronson.com/writings/bignumbers.html)de:Fleißiger Biber

pl:Busy Beaver