Busy beaver

From Wikipedia, the free 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 incalculable by a Turing machine. The concept was first introduced by Tibor Radó as the Busy Beaver Game in this 1962 paper, On Non-Computable Functions.

Contents 1 The Busy Beaver game 2 The Busy Beaver function 3 Non-computability of Σ 4 Max shifts function 5 Known values 6 Generalizations 7 Applications 8 Proof for uncomputability of S(n) and Σ(n) 9 Examples of Busy Beaver Turing machines 10 Exact values and lower bounds for some S(n, m) and Σ(n, m) 11 External links 12 References

[edit] The Busy Beaver game

In his 1962 paper On Non-Computable Functions, Tibor Radó introduces his Busy Beaver Game as follows:

Consider a Turing machine with the binary alphabet {0, 1} and n operational states (often labled 1, 2, ... n or A, B, C ...) and an additional Halt state. (Note: The Busy Beaver function, Σ(n), will be defined as the number of 1's that the Turing machine prints given the number n of "states" (Turing-instructions) and a blank tape at the outset.)

He used a definition of a Turing machine that coincides with Wikipedia's definition. In other words:

• The machine runs on a 2-way infinite (or unbounded) tape
• At each step two conditions -- (i) the machine's current "state" (instruction) and (ii) the tape symbol the machine's head is scanning -- define (iii) a unique symbol to write (the machine can overwrite a 1 on a 1, a 0 on a 0), (iv) a direction to move (Left or Right but "none" is not allowed in this model) and (v) a state to transition into (may be the same as the one it was in) and
• The machine halts if and when it reaches the special Halt state.

Now start with a blank tape (i.e. every cell has a 0 in it) and a TABLE of n instructions. Run the machine; if it halts, note the number of 1s it leaves on the tape.

The n-state Busy Beaver (BB-n) game is a competition to find an n-state Turing machine which leaves the largest number of 1s on its tape before halting.

In order to take part in this competition you must submit the description of an n-state Turing machine that halts along with the number of steps it takes to halt to a qualified umpire who must test its validity. It is important that you provide the number of steps taken to halt, because if you do not and your Turing machine does not halt, there is no general algorithm that the umpire can use to prove that it will not halt. Whereas if you do provide a finite number of steps along with a candidate machine, the umpire can (given enough time) decide whether or not the machine will halt in so many steps.

[edit] The Busy Beaver function

Radó went on to demonstrate that there is a well-defined champion to the n-state Busy Beaver Game:

There are a finite number of Turing machines with n states and 2 symbols ( [4(n+1)]²ⁿ in fact) and hence there are a finite number of halting Turing machines with n states and 2 symbols. In addition it is easy to show that there are halting machines (i.e. that there exists a halting n state, 2 symbol TM). Thus there exists a finite non-empty set E_n of halting n-state, 2-symbol Turing machines.

Now define:

• σ(M) = the number of 1s left on the tape after the Turing machine M is run on a blank tape for any M in E_n.
• Σ(n) = max { σ(M) | M in E_n} (The largest number of 1s written by any n-state 2-symbol Turing machine)

Now since σ(M) is a non-negative finite number for any M halting (in E_n) and since E_n is a non-empty finite set, Σ is a well-defined non-negative finite number for any n.

This (Σ) is the Busy Beaver function and any n-state, 2-symbol machine M for which σ(M) = Σ(n) (i.e. which attains the maximum) is called a Busy Beaver.

[edit] Non-computability of Σ

Radó went on to prove that Σ is a non-computable function (No Turing machine can compute it) because it grows faster than any computable function. (A proof is given below)

Thus, there will never be any mechanical way to prove Busy Beaver champions.

Although Σ is a non-computable function in general, it may be the case that its value for some fixed inputs can be determined. It is relatively easy to see that Σ(1) = 1 and not hard to show that Σ(2) = 4 (using the exact definition of an n-state Turing machine as in this article) and over the decades a few more small values have been proven and many lower bounds demonstrated.

[edit] Max shifts function

Shen Lin proved that Σ(3) = 6 in his 1965 paper with Radó, Computer Studies of Turing Machine Problems.

In order to prove this he used another extreme function of halting n-state Turing machines, the maximum shift function. Define:

• s(M) = the number of steps M takes before halting for any M in E_n
• S(n) = max { s(M) | M in E_n} (The largest number of steps taken by any n-state 2-symbol Turing machine)

Now, if you know S(n), you can run all n-state Turing machines for S(n) steps sequentially and note a machine which halted with the most 1s on the tape, then you have found a Busy Beaver and the number of 1s it writes is Σ(n) (Because all n-state TMs that halt will have halted in S(n) steps).

Thus, study of the maximum shift function has been closely linked with study of the Busy Beaver function.

[edit] Known values

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 1s, using 47,176,870 steps (Discovered by Heiner Marxen and Jürgen Buntrock in 1989), but there remain about 40 machines with nonregular behavior which are believed to never halt, but which have not yet been proven to run infinitely. At the moment the record 6-state 2-symbol Busy Beaver produces over 10⁸⁶⁵ 1s, using over 10¹⁷³⁰ steps (also found by Heiner Marxen and Jürgen Buntrock in 2001).

[edit] Generalizations

For any model of computations there exist simple analogs for Busy Beaver. For example, 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 started on an initially blank tape before halting, and
2. S(n, m): the largest number of steps taken by an n-state, m-symbol machine started on an initially blank tape before halting.

For example the longest running 3-state 3-symbol machine found so far runs 4,345,166,620,336,565 steps before halting[1]. The longest running 6-state, 2-symbol machine which has the additional property of reversing the tape value at each step produces 6,147 1s 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.

[edit] Applications

In addition to posing a rather challenging mathematical game the Busy Beaver functions has a profound application. Almost any open problem in mathematics could be solved in a systematic way given the value of S(n) for a sufficiently large n.

Consider any open question that could be disproven via a counterexample among a countable number of cases (e.g. Fermat's last theorem, Goldbach's conjecture or the twin prime conjecture). Now write a computer program that sequentially tests this conjecture for increasing values (in the case of Goldbach's conjecture, we would consider every even number sequentially and test whether or not it was the sum of 2 prime numbers). We will consider this program to be simulated by an n-state Turing machine (although we could alternatively define the Busy Beaver function for whatever well-defined language you used). If it finds a counterexample (an even number not the sum of 2 primes in our example), it halts and notifies us. However, if the conjecture is true then our program will never halt (This program can only find counterexamples, it cannot prove the conjecture true).

Now, this program is simulated by an n-state Turing machine, so if we know S(n) we can decide (in a finite amount of time) whether or not it will ever halt by simply running the machine that many steps. And if, after S(n) steps the machine does not halt, we know that it never will and thus there are no counterexamples to the given conjecture (e.g. no even numbers are not the sum of 2 primes). This would prove the conjecture to be true!

Thus specific values (or upper bounds) for S(n) could be used to systematically solve many open problems in mathematics (in theory). However, current results on the Busy Beaver problem suggest that this will not be practical for two reasons:

• It is extremely hard to prove values for the Busy Beaver function (and the max shift function). It has only been proven for extremely small machines with less than 5 states, while one would presumable need around 20-50 states to make a useful machine.
• The values of the Busy Beaver function (and max shift function) get vary large, vary fast. S(6) > 10¹⁷³⁰ already requires special pattern-based acceleration to be able to simulate to completion. Thus even if we know, say, S(30), it may be completely unreasonable to run any machine that number of steps (it is likely that even comprehending or describing the number S(30) would be non-trivial)

[edit] 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) 1s 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 denote 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 S(n) can also be trivially established by reference to the halting problem. As S(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 S(n) steps; if it has still not halted, it never will. As being able to compute S(n) would provide a solution to the provably uncomputable halting problem, it follows that S(n) must likewise be uncomputable.

[edit] Examples of Busy Beaver Turing machines

For an example of a 3-state Busy Beaver's state table and its "run" see 3-state Busy Beaver.

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 direction to move, and the new state (in that order). In this case the author has chosen to omit the direction to move for the transition which goes to the Halt state (Either direction will produce equal values for s and σ).

Each machine begins in state A with an infinite tape that contains all 0s. 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⁸⁶⁵ 1s 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.

[edit] 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.

Values of S(n,m):

Values of Σ(n,m):

[edit] 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?

[edit] References

• Radó, Tibor (1962), On non-computable functions, Bell Systems Tech. J. 41, 3 (May 1962). This is where Radó first defined the Busy Beaver problem and proved that it was uncomputable and grew faster than any computable function.

• Lin, Shen and Radó, Tibor (1965), Computer Studies of Turing Machine Problems, Journal of the Association for Computing Machinery, Vol. 12, No. 2 (April 1965), pp. 196-212. Lin was a doctoral student under Radó. This paper appeared in part of Lin's thesis. Lin proves that Σ(3) = 6 and S(3) = 21 by proving that all 3-state 2-symbol Turing Machines which don't halt after 21 steps will never halt (Most are proven automatically by a computer program, however 40 are proven by human inspection).

• Brady, Allen H. (1983), The determination of the value of Rado's noncomputable function Sigma(k) for four-state Turing machines, Mathematics of Computation, Vol. 40, No. 162 (April 1983), pp. 647-665. Brady proves that Σ(4) = 13 and S(4) = 107. Brady defines two new categories for non-halting 3-state 2-symbol Turing Machines: Christmas Trees and Counters. He uses a computer program to prove that all but 27 machines which run over 107 steps are variants of Christmas Trees and Counters which can be proven to run infinitely. The last 27 machines (referred to as holdouts) are proven by personal inspection by Brady himself not to halt.

• Machlin, Rona and Stout, Quentin F. (1990), The complex behavior of simple machines, Physica D, No. 42 (June 1990), pp. 85-98. Rona and Quentin describe the Busy Beaver problem and many techniques used for finding Busy Beavers (Which they apply to Turing Machines with 4-states and 2-symbols, thus verifying Brady's proof). They use the known values for S for all machines with ≤ 4 states and 2 symbols to estimate a variant of Chaitin's halting probability (Ω).

• Marxen, Heiner and Buntrock, Jürgen (1990), Attacking the Busy Beaver 5, Bulletin of the EATCS, No 40 (February 1990), pp. 247-251. Heiner and Jürgen demonstrate that Σ(5) ≥ 4098 and S(5) ≥ 47,176,870 and describe in detail the method they used to find these machines and prove many others will never halt.

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

• Dewdney, Alexander K. A computer trap for the Busy Beaver, the hardest working Turing machine, Scientific American, 251 (2), 10-17, 1984.

• Brady, Allen H. (1995), The Busy Beaver Game and the Meaning of Life, p 237-254, appearing in Herken, Rolf (ed)., The Universal Turing Machine: A Half-Century Survey, 2nd edition (1995), Springer-Verlag, Wien New York. Wherein Brady (of 4-state fame) describes some history of the beast and calls its pursuit "The Busy Beaver Game". He describes other games (e.g. cellular automata Game of Life). Of particular interest is the "The Busy Beaver Game in Two Dimensions" (p. 247). With 19 references.

• Taylor L. Booth, 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 Busy Beavers 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."