Busy beaver
Encyclopedia
In computability theory
, a busy beaver (from the colloquial expression for an industrious person) is a Turing machine
that attains the maximum "operational busyness" (such as measured by the number of steps performed, or the number of nonblank symbols finally on the tape) among all the Turing machines in a certain class. The Turing machines in this class must meet certain design specifications and are required to eventually halt
after being started with a blank tape.
A busy beaver function quantifies these upper limits on a given type of "operational busyness", and is a noncomputable function. In fact, a busy beaver function can be shown to grow faster asymptotically
than does any computable function. The concept was first introduced by Tibor Radó
as the "busy beaver game" in his 1962 paper, "On Non-Computable Functions".
's 1962 paper, involves a class of Turing machines, each member of which is required to meet the following design specifications:
"Running" the machine consists of starting in the starting state, with the current tape cell being any cell of a blank (all-0) tape, and then iterating the transition function until the Halt state is entered (if ever). If, and only if, the machine eventually halts, then the number of 1s finally remaining on the tape is called the machine's score.
The n-state busy beaver (BB-n) game is a contest to find such an n-state Turing machine having the largest possible score — the largest number of 1s on its tape after halting. A machine that attains the largest possible score among all n-state Turing machines is called an n-state busy beaver, and a machine whose score is merely the highest so far attained (perhaps not the largest possible) is called a champion n-state machine.
Radó required that each machine entered in the contest be accompanied by a statement of the exact number of steps it takes to reach the Halt state, thus allowing the score of each entry to be verified (in principle) by running the machine for the stated number of steps. (If entries were to consist only of machine descriptions, then the problem of verifying every potential entry is undecidable, because it is equivalent to the well-known halting problem
— there would be no effective way to decide whether an arbitrary machine eventually halts.)
Radó showed that Σ is a well-defined function; that is, for every n, the n-state busy beaver game does indeed have a maximum attainable score. To do this, he used the basic principle that a nonempty finite set of nonnegative integers must have a largest element:
There are finitely many Turing machines with n states and 2 symbols (specifically there are [4(n+1)]2n 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 Turing Machine that will halt, for every n. Now define:
Since σ(M) is a non-negative integer for any M in En, and since En is a non-empty finite set, Σ(n) is a well-defined non-negative integer for every nonnegative integer n.
This infinite sequence Σ is the busy beaver function, and any n-state 2-symbol Turing machine M for which σ(M) = Σ(n) (i.e., which attains the maximum score) is called a busy beaver. Note that for each n, there exist at least two n-state busy beavers (because, given any n-state busy beaver, another is obtained by merely changing the shift direction in a halting transition).
→ N
is any computable function
, then Σ(n) > f(n) for all sufficiently large n, and hence that Σ is not a computable function.
Moreover, this implies that it is undecidable
by a general algorithm
whether an arbitrary Turing machine is a busy beaver. (Such an algorithm cannot exist, because its existence would allow Σ to be computed, which is a proven impossibility. In particular, such an algorithm could be used to construct another algorithm that would compute Σ as follows: for any given n, each of the finitely many n-state 2-symbol Turing machines would be tested until an n-state busy beaver is found; this busy beaver machine would then be simulated to determine its score, which is by definition Σ(n).)
A noteworthy fact is that, theoretically, every finite sequence of Σ values, such as Σ(0), Σ(1), Σ(2), ..., Σ(n) for any given n, is (trivially) computable, even though the infinite sequence Σ is not computable (see computable function examples). Furthermore, for sufficiently small n, it is also practical to compute Σ(n). Thus, it is not hard to show that Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, and with progressively more difficulty it can be shown that Σ(3) = 6 and Σ(4) = 13 . Σ(n) has not yet been determined for any instance of n > 4, although lower bounds have been established (see the Known Values section below).
is defined as follows [cf. Boolos, Burgess & Jeffrey, 2007]: The complexity of a number n is the smallest number of states needed for a BB-class Turing machine that halts with a single block of n consecutive 1s on an initially blank tape. The corresponding variant of Chaitin's incompleteness theorem states that, in the context of a given axiomatic system
for the natural numbers, there exists a number k such that no specific number can be proved to have complexity greater than k, and hence that no specific upper bound can proven for Σ(k). (The latter is because "the complexity of n is greater than k" would be proved if "n > Σ(k)" were proved.) As mentioned in the cited reference, for any axiomatic system of "ordinary mathematics" the least value k for which this is true is far less than 10↑↑10 (using Knuth up-arrow notation); consequently, in the context of ordinary mathematics, neither the value nor any upper-bound of Σ(10↑↑10) can be proven. (Gödel's first incompleteness theorem is illustrated by this result: in an axiomatic system of ordinary mathematics, there is a true-but-unprovable sentence of the form "Σ(10↑↑10) = n", and there are infinitely many true-but-unprovable sentences of the form "Σ(10↑↑10) < n".)
Because these Turing machines are required to have a shift in each and every transition or "step" (including any transition to a Halt state), the max-shifts function is at the same time a max-steps function.
Radó showed that S is noncomputable for the same reason that Σ is noncomputable — it grows faster than any computable function. He proved this simply by noting that for each n, S(n) ≥ Σ(n), because a shift is required to write a 1 on the tape; consequently, S grows at least as fast as Σ, which had already been proved to grow faster than any computable function.
The following connection between Σ and S was used by Lin & Radó [Computer Studies of Turing Machine Problems, 1965] to prove that Σ(3) = 6: For a given n, if S(n) is known then all n-state Turing machines can (in principle) be run for up to S(n) steps, at which point any machine that hasn't yet halted will never halt. At that point, by observing which machines have halted with the most 1s on the tape (i.e., the busy beavers), one obtains from their tapes the value of Σ(n). The approach used by Lin & Radó for the case of n = 3 was to conjecture that S(3) = 21, then to simulate all the essentially different 3-state machines for up to 21 steps. By analyzing the behavior of the machines that had not halted within 21 steps, they succeeded in showing that none of those machines would ever halt, thus proving the conjecture that S(3) = 21, and determining that Σ(3) = 6 by the procedure just described.
Inequalities relating Σ and S include the following (from [Ben-Amram, et al., 1996]), which are valid for all n ≥ 1:
and an asymptotically
improved bound (from [Ben-Amram, Petersen, 2002]): there exists a constant c, such that for all n ≥ 2,
Milton Green, in his 1964 paper "A Lower Bound on Rado's Sigma Function for Binary Turing Machines", constructed a set of Turing machines demonstrating that
where
is Knuth up-arrow notation and A is Ackermann's function.
Thus
(with 327 = 7,625,597,484,987 terms in the exponential tower), and
where the number g1 is the enormous starting value in the sequence that defines Graham's number
.
In contrast, the current bound on Σ(6) is 1018267, which is less than 3333 (tiny in comparison).
there exist simple analogs of the busy beaver. For example, the generalization to Turing machines with n states and m symbols defines the following generalized busy beaver functions:
For example the longest running 3-state 3-symbol machine found so far runs 119,112,334,170,342,540 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 1s after 47,339,970 steps. So SRTM(6) ≥ 47,339,970 and ΣRTM(6) ≥ 6,147.
Likewise we could define an analog to the Σ function for register machine
s as the largest number which can be present in any register on halting, for a given number of instructions.
, the busy beaver functions have a profound application. Many open problems in mathematics could be solved in a systematic way given the value of S(n) for a sufficiently large n.
Consider any conjecture
that could be disproven
via a counterexample
among a countable number of cases (e.g. Goldbach's conjecture
). 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 ≥ 4 sequentially and test whether or not it is the sum of two prime numbers. Suppose this program is simulated on an n-state Turing machine. If it finds a counterexample (an even number ≥ 4 that is 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 halts only if it finds a counterexample.)
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 two 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:
Let us create the composition Double | EvalS | Clean and let n0 be the number of states of this machine. Let Create_n0 denote a Turing machine creating n0 1s on an initially blank tape. This machine may be constructed in a trivial manner to have n0 states (the state i writes 1, moves the head right and switches to state i + 1, except the state n0, which halts). Let N denote the sum n0 + n0.
Let BadS denote the composition Create_n0 | Double | EvalS | Clean. Notice that this machine has N states. Starting with an initially blank tape it first creates a sequence of n0 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 1s 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.
These are tables of rules for the Turing machines that generate Σ(1) and S(1), Σ(2) and S(2), Σ(3) (but not S(3)), Σ(4) and S(4), and the best known lower bound for Σ(5) and S(5), and Σ(6) and S(6).
In the tables, columns represent the current state and rows represent the current symbol read from the tape. Each table entry is a string of three characters, indicating the symbol to write onto the tape, the direction to move, and the new state (in that order). The Halt state is shown as H.
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)
Result: 0 0 1 0 0 (1 step, one "1" total)
Result: 0 0 1 1 1 1 0 0 (6 steps, four "1"s total)
Result: 0 0 1 1 1 1 1 1 0 0 (14 steps, six "1"s total).
Note that unlike the previous machines, this one is a busy beaver only for Σ, but not for S. (S(3) = 21.)
Result: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 steps, thirteen "1"s total)
Result: 4098 "1"s with 8191 "0"s interspersed in 47,176,870 steps.
Result: ≈3.515 × 1018267 "1"s in ≈7.412 × 1036534 steps.
The Turing machines that achieve these values are available on both Heiner Marxen's and Pascal Michel's webpages. Each of these websites 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):
Computability theory (computer science)
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science...
, a busy beaver (from the colloquial expression for an industrious person) is a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
that attains the maximum "operational busyness" (such as measured by the number of steps performed, or the number of nonblank symbols finally on the tape) among all the Turing machines in a certain class. The Turing machines in this class must meet certain design specifications and are required to eventually halt
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
after being started with a blank tape.
A busy beaver function quantifies these upper limits on a given type of "operational busyness", and is a noncomputable function. In fact, a busy beaver function can be shown to grow faster asymptotically
Asymptotic analysis
In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...
than does any computable function. The concept was first introduced by Tibor Radó
Tibor Radó
Tibor Radó 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. In World War I, he became a First Lieutenant in the Hungarian Army and was captured on the Russian Front...
as the "busy beaver game" in his 1962 paper, "On Non-Computable Functions".
The busy beaver game
The n-state busy beaver game (or BB-n game), introduced in Tibor RadóTibor Radó
Tibor Radó 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. In World War I, he became a First Lieutenant in the Hungarian Army and was captured on the Russian Front...
's 1962 paper, involves a class of Turing machines, each member of which is required to meet the following design specifications:
- The machine has n "operational" states plus a Halt state, where n is a positive integer, and one of the n states is distinguished as the starting state.
(Typically, the states are labelled by 1, 2, ..., n, with state 1 as the starting state, or by A, B, C, ..., with state A as the starting state.) - The machine uses a single two-way infinite (or unbounded) tape.
- The tape alphabet is {0, 1}, with 0 serving as the blank symbol.
- The machine's transition function takes two inputs:
-
- the current non-Halt state,
- the symbol in the current tape cell,
- and produces three outputs:
- a symbol to write over the one in the current tape cell (it may be the same symbol as the one overwritten),
- a direction to move (left or right; that is, shift to the tape cell one place to the left or right of the current cell), and
- a state to transition into (which may be the Halt state).
- The transition function may be seen as a finite table of 5-tuples, each of the form.
"Running" the machine consists of starting in the starting state, with the current tape cell being any cell of a blank (all-0) tape, and then iterating the transition function until the Halt state is entered (if ever). If, and only if, the machine eventually halts, then the number of 1s finally remaining on the tape is called the machine's score.
The n-state busy beaver (BB-n) game is a contest to find such an n-state Turing machine having the largest possible score — the largest number of 1s on its tape after halting. A machine that attains the largest possible score among all n-state Turing machines is called an n-state busy beaver, and a machine whose score is merely the highest so far attained (perhaps not the largest possible) is called a champion n-state machine.
Radó required that each machine entered in the contest be accompanied by a statement of the exact number of steps it takes to reach the Halt state, thus allowing the score of each entry to be verified (in principle) by running the machine for the stated number of steps. (If entries were to consist only of machine descriptions, then the problem of verifying every potential entry is undecidable, because it is equivalent to the well-known halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
— there would be no effective way to decide whether an arbitrary machine eventually halts.)
The busy beaver function Σ
The busy beaver function, Σ: N → N, is defined such that Σ(n) is the maximum attainable score (the maximum number of 1s finally on the tape) among all halting 2-symbol n-state Turing machines of the above-described type, when started on a blank tape.Radó showed that Σ is a well-defined function; that is, for every n, the n-state busy beaver game does indeed have a maximum attainable score. To do this, he used the basic principle that a nonempty finite set of nonnegative integers must have a largest element:
There are finitely many Turing machines with n states and 2 symbols (specifically there are [4(n+1)]2n 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 Turing Machine that will halt, for every n. Now define:
-
is the finite, non-empty set of halting n-state 2-symbol Turing machines of the type described in the preceding section (two-way infinite tape, transition function defined by 5-tuples, etc.). -
, for each Turing machine 
in 
, is the score of machine 
— the number of 1s finally on the tape after machine 
is run to completion with an initially blank tape. -
(i.e., the maximum score among all n-state 2-symbol halting Turing machines started with a blank tape).
Since σ(M) is a non-negative integer for any M in En, and since En is a non-empty finite set, Σ(n) is a well-defined non-negative integer for every nonnegative integer n.
This infinite sequence Σ is the busy beaver function, and any n-state 2-symbol Turing machine M for which σ(M) = Σ(n) (i.e., which attains the maximum score) is called a busy beaver. Note that for each n, there exist at least two n-state busy beavers (because, given any n-state busy beaver, another is obtained by merely changing the shift direction in a halting transition).
Non-computability of Σ
Radó's 1962 paper proved that if f: NNatural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
→ N
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
is any computable function
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
, then Σ(n) > f(n) for all sufficiently large n, and hence that Σ is not a computable function.
Moreover, this implies that it is undecidable
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
by a general algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
whether an arbitrary Turing machine is a busy beaver. (Such an algorithm cannot exist, because its existence would allow Σ to be computed, which is a proven impossibility. In particular, such an algorithm could be used to construct another algorithm that would compute Σ as follows: for any given n, each of the finitely many n-state 2-symbol Turing machines would be tested until an n-state busy beaver is found; this busy beaver machine would then be simulated to determine its score, which is by definition Σ(n).)
A noteworthy fact is that, theoretically, every finite sequence of Σ values, such as Σ(0), Σ(1), Σ(2), ..., Σ(n) for any given n, is (trivially) computable, even though the infinite sequence Σ is not computable (see computable function examples). Furthermore, for sufficiently small n, it is also practical to compute Σ(n). Thus, it is not hard to show that Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, and with progressively more difficulty it can be shown that Σ(3) = 6 and Σ(4) = 13 . Σ(n) has not yet been determined for any instance of n > 4, although lower bounds have been established (see the Known Values section below).
Σ, complexity and unprovability
A variant of Kolmogorov complexityKolmogorov complexity
In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...
is defined as follows [cf. Boolos, Burgess & Jeffrey, 2007]: The complexity of a number n is the smallest number of states needed for a BB-class Turing machine that halts with a single block of n consecutive 1s on an initially blank tape. The corresponding variant of Chaitin's incompleteness theorem states that, in the context of a given axiomatic system
Axiomatic system
In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A mathematical theory consists of an axiomatic system and all its derived theorems...
for the natural numbers, there exists a number k such that no specific number can be proved to have complexity greater than k, and hence that no specific upper bound can proven for Σ(k). (The latter is because "the complexity of n is greater than k" would be proved if "n > Σ(k)" were proved.) As mentioned in the cited reference, for any axiomatic system of "ordinary mathematics" the least value k for which this is true is far less than 10↑↑10 (using Knuth up-arrow notation); consequently, in the context of ordinary mathematics, neither the value nor any upper-bound of Σ(10↑↑10) can be proven. (Gödel's first incompleteness theorem is illustrated by this result: in an axiomatic system of ordinary mathematics, there is a true-but-unprovable sentence of the form "Σ(10↑↑10) = n", and there are infinitely many true-but-unprovable sentences of the form "Σ(10↑↑10) < n".)
Max shifts function
In addition to the function Σ, Radó [1962] introduced another extreme function for the BB-class of Turing machines, the maximum shifts function, S, defined as follows:-
the number of shifts M makes before halting, for any M in En, -
the largest number of shifts made by any halting n-state 2-symbol Turing machine.
Because these Turing machines are required to have a shift in each and every transition or "step" (including any transition to a Halt state), the max-shifts function is at the same time a max-steps function.
Radó showed that S is noncomputable for the same reason that Σ is noncomputable — it grows faster than any computable function. He proved this simply by noting that for each n, S(n) ≥ Σ(n), because a shift is required to write a 1 on the tape; consequently, S grows at least as fast as Σ, which had already been proved to grow faster than any computable function.
The following connection between Σ and S was used by Lin & Radó [Computer Studies of Turing Machine Problems, 1965] to prove that Σ(3) = 6: For a given n, if S(n) is known then all n-state Turing machines can (in principle) be run for up to S(n) steps, at which point any machine that hasn't yet halted will never halt. At that point, by observing which machines have halted with the most 1s on the tape (i.e., the busy beavers), one obtains from their tapes the value of Σ(n). The approach used by Lin & Radó for the case of n = 3 was to conjecture that S(3) = 21, then to simulate all the essentially different 3-state machines for up to 21 steps. By analyzing the behavior of the machines that had not halted within 21 steps, they succeeded in showing that none of those machines would ever halt, thus proving the conjecture that S(3) = 21, and determining that Σ(3) = 6 by the procedure just described.
Inequalities relating Σ and S include the following (from [Ben-Amram, et al., 1996]), which are valid for all n ≥ 1:
and an asymptotically
Asymptotic analysis
In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...
improved bound (from [Ben-Amram, Petersen, 2002]): there exists a constant c, such that for all n ≥ 2,
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 non-regular 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 1018267 1s, using over 1036534 steps (found by Pavel Kropitz in 2010). As noted above, these busy beavers are 2-symbol Turing machines.Milton Green, in his 1964 paper "A Lower Bound on Rado's Sigma Function for Binary Turing Machines", constructed a set of Turing machines demonstrating that
where
is Knuth up-arrow notation and A is Ackermann's function.Thus
(with 327 = 7,625,597,484,987 terms in the exponential tower), and
where the number g1 is the enormous starting value in the sequence that defines Graham's number
Graham's number
Graham's number, named after Ronald Graham, is a large number that is an upper bound on the solution to a certain problem in Ramsey theory.The number gained a degree of popular attention when Martin Gardner described it in the "Mathematical Games" section of Scientific American in November 1977,...
.
In contrast, the current bound on Σ(6) is 1018267, which is less than 3333 (tiny in comparison).
Generalizations
For any model of computationModel of computation
In computability theory and computational complexity theory, a model of computation is the definition of the set of allowable operations used in computation and their respective costs...
there exist simple analogs of the busy beaver. For example, the generalization to Turing machines with n states and m symbols defines the following generalized busy beaver functions:
- Σ(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
- 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 119,112,334,170,342,540 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 1s after 47,339,970 steps. So SRTM(6) ≥ 47,339,970 and ΣRTM(6) ≥ 6,147.
Likewise we could define an analog to the Σ function for register machine
Register machine
In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine...
s as the largest number which can be present in any register on halting, for a given number of instructions.
Applications
In addition to posing a rather challenging mathematical gameMathematical game
A mathematical game is a multiplayer game whose rules, strategies, and outcomes can be studied and explained by mathematics. Examples of such games are Tic-tac-toe and Dots and Boxes, to name a couple. On the surface, a game need not seem mathematical or complicated to still be a mathematical game...
, the busy beaver functions have a profound application. Many open problems in mathematics could be solved in a systematic way given the value of S(n) for a sufficiently large n.
Consider any conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
that could be disproven
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
via a counterexample
Counterexample
In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule. For example, consider the proposition "all students are lazy"....
among a countable number of cases (e.g. Goldbach's conjecture
Goldbach's conjecture
Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:A Goldbach number is a number that can be expressed as the sum of two odd primes...
). 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 ≥ 4 sequentially and test whether or not it is the sum of two prime numbers. Suppose this program is simulated on an n-state Turing machine. If it finds a counterexample (an even number ≥ 4 that is 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 halts only if it finds a counterexample.)
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 two 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 fewer than 5 states, while one would presumably need at least 20-50 states to make a useful machine. Furthermore, every known exact value of S(n) was proven by enumerating every n-state Turing machine and proving whether or not each halts. One would have to calculate S(n) by some less direct method for it to actually be useful.
- But even if one did find a better way to calculate S(n), the values of the busy beaver function (and max shift function) get very large, very fast. S(6) > 1036534 already requires special pattern-based acceleration to be able to simulate to completion. Likewise, we know that
is a gigantic number. Thus, even if we knew, say, S(30), it is completely unreasonable to run any machine that number of steps. There is not enough computational capacity in the known universe to have performed even S(6) operations.
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 n0 be the number of states of this machine. Let Create_n0 denote a Turing machine creating n0 1s on an initially blank tape. This machine may be constructed in a trivial manner to have n0 states (the state i writes 1, moves the head right and switches to state i + 1, except the state n0, which halts). Let N denote the sum n0 + n0.
Let BadS denote the composition Create_n0 | Double | EvalS | Clean. Notice that this machine has N states. Starting with an initially blank tape it first creates a sequence of n0 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 1s 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
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
. 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.
Examples of busy beaver Turing machines
For an example of a 3-state busy beaver's state table and its "run" see Turing machine examples.These are tables of rules for the Turing machines that generate Σ(1) and S(1), Σ(2) and S(2), Σ(3) (but not S(3)), Σ(4) and S(4), and the best known lower bound for Σ(5) and S(5), and Σ(6) and S(6).
In the tables, columns represent the current state and rows represent the current symbol read from the tape. Each table entry is a string of three characters, indicating the symbol to write onto the tape, the direction to move, and the new state (in that order). The Halt state is shown as H.
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 busy beaver
| A | |
|---|---|
| 0 | 1RH |
| 1 | (not used) |
Result: 0 0 1 0 0 (1 step, one "1" total)
2-state, 2-symbol busy beaver
| A | B | |
|---|---|---|
| 0 | 1RB | 1LA |
| 1 | 1LB | 1RH |
Result: 0 0 1 1 1 1 0 0 (6 steps, four "1"s total)
3-state, 2-symbol busy beaver
| A | B | C | |
|---|---|---|---|
| 0 | 1RB | 0RC | 1LC |
| 1 | 1RH | 1RB | 1LA |
Result: 0 0 1 1 1 1 1 1 0 0 (14 steps, six "1"s total).
Note that unlike the previous machines, this one is a busy beaver only for Σ, but not for S. (S(3) = 21.)
4-state, 2-symbol busy beaver
| A | B | C | D | |
|---|---|---|---|---|
| 0 | 1RB | 1LA | 1RH | 1RD |
| 1 | 1LB | 0LC | 1LD | 0RA |
Result: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 steps, thirteen "1"s total)
current 5-state, 2-symbol best contender (possible busy beaver)
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 0 | 1RB | 1RC | 1RD | 1LA | 1RH |
| 1 | 1LC | 1RB | 0LE | 1LD | 0LA |
Result: 4098 "1"s with 8191 "0"s interspersed in 47,176,870 steps.
current 6-state, 2-symbol best contender
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| 0 | 1RB | 1RC | 1LD | 1RE | 1LA | 1LH |
| 1 | 1LE | 1RF | 0RB | 0LC | 0RD | 1RC |
Result: ≈3.515 × 1018267 "1"s in ≈7.412 × 1036534 steps.
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 from below 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 both Heiner Marxen's and Pascal Michel's webpages. Each of these websites 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 | ≥ 7.4 × 1036534 |
| 3-symbol | 38 | ≥ 119,112,334,170,342,540 | ≥ 1.0 × 1014072 | ??? | ??? |
| 4-symbol | ≥ 3,932,964 | ≥ 5.2 × 1013036 | ??? | ??? | ??? |
| 5-symbol | ≥ 1.9 × 10704 | ??? | ??? | ??? | ??? |
| 6-symbol | ≥ 2.4 × 109866 | ??? | ??? | ??? | ??? |
Values of Σ(n,m):
| 2-state | 3-state | 4-state | 5-state | 6-state | |
|---|---|---|---|---|---|
| 2-symbol | 4 | 6 | 13 | ≥ 4,098 | ≥ 3.5 × 1018267 |
| 3-symbol | 9 | ≥ 374,676,383 | ≥ 1.3 × 107036 | ??? | ??? |
| 4-symbol | ≥ 2,050 | ≥ 3.7 × 106518 | ??? | ??? | ??? |
| 5-symbol | ≥ 1.7 × 10352 | ??? | ??? | ??? | ??? |
| 6-symbol | ≥ 1.9 × 104933 | ??? | ??? | ??? | ??? |
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.
- Daniel Briggs' website and forum for solving the 5-state, 2-symbol busy beaver problem, based on Skelet (Georgi Georgiev) nonregular machines list.
- Aaronson, Scott (1999), Who can name the biggest number?
- Busy Beaver by Hector Zenil, Wolfram Demonstrations ProjectWolfram Demonstrations ProjectThe Wolfram Demonstrations Project is hosted by Wolfram Research, whose stated goal is to bring computational exploration to the widest possible audience. It consists of an organized, open-source collection of small interactive programs called Demonstrations, which are meant to visually and...
.