Busy beaver

From Free net encyclopedia

In computability theory, a Busy Beaver (from the colloquial expression for "industrious person") is a Turing machine that, when given an empty tape, does a lot of work, then halts. The machine meets limits on the amount of resources that a halting machine of a particular size can consume, in terms of either time or space. Related is the concept of a Busy Beaver function, which quantifies those resource limits and which, therefore, is uncalculable by Turing machine.

Contents 1 Definition and known values 2 Generalizations 3 Trivial proof for uncomputability of S(n) and Σ(n) 4 Examples of Busy Beaver Turing machines 5 Exact values and lower bounds for some S(n, m) and Σ(n, m) 6 External links 7 References

Definition and known values

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.

Originally the only Turing machines considered were those using only 2 tape symbols (0 and 1). With more symbols, the machine can store more state on its tape and so do more work.

The function values for Σ(n) and S(n) are only known exactly for 2 symbols and n < 5. The current 5-state 2-symbol Busy Beaver champion produces 4,098 ones, using 47,176,870 steps, but there remain about 40 machines with nonregular behavior. At the moment the record 6-state 2-symbol Busy Beaver produces over 10⁸⁶⁵ ones, using over 10¹⁷³⁰ steps.

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 Gregory Lafitte and Christophe Papazian[1] in 2005) runs 987,522,842,126 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 Turing machine cleaning the sequence of 1s initially written on the tape. Let Double denote a Turing machine 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 Turing machine 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.

The uncomputability of Σ(n) can also be trivially established by reference to the halting problem. As Σ(n) is the maximum number of steps that can be performed by a halting Turing machine, any machine which runs for more steps must be non-halting. One could then determine whether a given Turing machine with n states halts by running it for Σ(n) steps; if it has still not halted, it never will. As being able to compute Σ(n) would provide a solution to the provably uncomputable halting problem, it follows that Σ(n) must likewise be uncomputable.

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).

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 list of 6 state, 2 symbol Turing machines 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. These machines either haven't been investigated or were subsequently surpassed by a machine preceding them.

The Turing machines that achieve these values are available on either Heiner Marxen's and Pascal Michel's WWW pages. Each of these WWW sites also contains some analysis of the Turing machines and references to the proofs of the exact values.

In the second half of 2005, discoveries made by Gregory Lafitte and Christophe Papazian entailed changes in the following S and Σ tables for (n,m) belonging to {(3,3),(2,5),(3,4),(4,3),(5,3),(4,4),(3,5),(2,6)}, changing altogether 16 entries.

Values of S(n,m):

Values of Σ(n,m):

External links

• The page of Heiner Marxen, who, with Jürgen Buntrock, found the above-mentioned records for a 5 and 6-state Turing machine.
• Pascal Michel's Historical survey of Busy Beaver results which also contains best results and some analysis.
• The page of Penousal Machado's Genetic Beaver Project uses Evolutionary Computation to find new candidates to the Busy Beaver Problem
• Definition of the class RTM - Reversal Turing Machines, simple and strong subclass of the TMs.
• The "Millennium Attack" at the Rensselaer RAIR Lab on the Busy Beaver Problem.
• Aaronson, Scott (1999), Who can name the biggest number?

References

• Booth, Taylor L, Sequential Machines and Automata Theory, Wiley, New York, 1967. Cf Chapter 9, Turing Machines. A difficult book, meant for electrical engineers and technical specialists. Discusses recursion, partial-recursion with reference to Turing Machines, halting problem. A reference in Booth attributes them to Rado. Booth also defines Rado's Busy Beaver Problem in "home problems" 3, 4, 5, 6 of Chapter 9, p. 396. Problem 3 is to "show that the busy beaver problem is unsolvable... for all values of n."
• Rado,T. (1962), On non-computable functions, Bell Systems Tech. J. 41.
• Busy Beaver Programs are described by Alexander Dewdney in Scientific American, August 1984, page unknown, also March 1985 p. 23 and April 1985 p. 30.de:Fleißiger Biber

pl:Busy Beaver