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 his 1962 paper, On Non-Computable Functions. In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ... An artistic representation of a Turing Machine . ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ... Tibor Radó (June 2, 1895 - December 29, 1965) was a Hungarian mathematician who moved to the USA after World War I. He was born in Budapest and between 1913 and 1915 attended the Polytechnic Institute. ...

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 labeled 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.) An artistic representation of a Turing Machine . ...

His definition of a Turing machine was as follows:

• The machine runs on a 2-way infinite (or unbounded) tape.
• At each step, two conditions --

1. the machine's current "state" (instruction); and
2. the tape symbol the machine's head is scanning

-- define each of the following:

1. a unique symbol to write (the machine can overwrite a 1 on a 0, a 0 on a 1, a 1 on a 1, and a 0 on a 0);
2. a direction to move (Left or Right but "none" is not allowed in this model); and
3. a state to transition into (may be the same as the one it was in).

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

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, specifically there are [4n+2]²ⁿ of them. In addition it is trivial that some of these are halting machines; i.e., there exists at least one n-state, 2-symbol TM that will halt, for every n.

Now define:

• E_n to be the finite, non-empty set of halting n-state, 2-symbol Turing machines.
• σ(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)

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.

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.) In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation. ... Computability theory is that part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. ...

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 and over the decades a few more small values have been proven and many lower bounds demonstrated.

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.

Known values

The function values for Σ(n) and S(n) are only known exactly for n < 5. The current 5-state 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 Busy Beaver produces over 10⁸⁶⁵ 1s, using over 10¹⁷³⁰ steps (also found by Heiner Marxen and Jürgen Buntrock in 2001). As noted above, these Busy Beavers are 2-symbol Turing machines.

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. The Minsky register machine is a type of theoretical computing device. ... In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ...

Applications

In addition to posing a rather challenging mathematical game the Busy Beaver functions have 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. Mathematical games include many topics which are a part of recreational mathematics, but can also cover topics such as the mathematics of games, and playing games with mathematics. ... This article lists some unsolved problems in mathematics. ...

Consider any open question that could be disproven via a counterexample among a countable number of cases (e.g. Goldbach's 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). In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule, i. ... In mathematics the term countable set is used to describe the size of a set, e. ... Goldbachs conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. ...

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 that there are no counterexamples to the given conjecture (i.e., no even numbers that 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 presumably need around 20-50 states to make a useful machine.
• The values of the Busy Beaver function (and max shift function) get very large, very 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).

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. In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...

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. The following are examples to supplement the article Turing machine: // The following table is Turings very first example (Turing 1936): 1. ...

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 at the position underlined, halts at the position in bold)

1-state, 2-symbol:

	A
0	1-Halt
1	Never used

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

2-state, 2-symbol:

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

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

6-state, 2-symbol:

	A	B	C	D	E	F
0	1-Right-B	0-Right-C	1-Left-D	0-Left-E	0-Right-A	1-Left-A
1	0-Left-F	0-Right-D	1-Right-E	0-Left-D	1-Right-C	1-Halt

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. An artistic representation of a Turing Machine . ...

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 as plain integers 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):

	2-state	3-state	4-state	5-state	6-state
2-symbol	6	21	107	≥ 47,176,870	≥ 3.0 x 101730
3-symbol	≥ 38	≥ 4,345,166,620,336,565	???	???	???
4-symbol	≥ 3,932,964	???	???	???	???
5-symbol	≥ 7,069,449,877,176,007,352,687	???	???	???	???

Values of Σ(n,m):

	2-state	3-state	4-state	5-state	6-state
2-symbol	4	6	13	≥ 4,098	≥ 1.2 x 10865
3-symbol	≥ 9	≥ 95,524,079	???	???	???
4-symbol	≥ 2,050	???	???	???	???
5-symbol	≥ 172,312,766,455	???	???	???	???

See also

• Kolmogorov complexity

In computer science, the Kolmogorov complexity (also known as descriptive complexity, Kolmogorov-Chaitin complexity, stochastic complexity, algorithmic entropy, or program-size complexity) of an object such as a piece of text is a measure of the computational resources needed to specify the object. ...

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

• 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, pages 19-23, 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 and Conway's 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."