Busy beaver
In theoretical computer science, the busy beaver game aims to find a terminating program of a given size that (depending on definition) either produces the most output possible, or runs for the longest number of steps.
[3] Turing machines consist of an infinite tape, and a finite set of states which serve as the program's "source code".
Producing the most output is defined as writing the largest number of 1s on the tape, also referred to as achieving the highest score, and running for the longest time is defined as taking the longest number of steps to halt.
[4] The n-state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has n states and eventually halts.
[2] The objective of the game is to program a set of transitions between states aiming for the highest score or longest running time while making sure the machine will halt eventually.
[5] Depending on definition, it either attains the highest score, or runs for the longest time, among all other possible n-state competing Turing machines.
The functions determining the highest score or longest running time of the n-state busy beavers by each definition are Σ(n) and S(n) respectively.
[6] The concept of a busy beaver was first introduced by Tibor Radó in his 1962 paper, "On Non-Computable Functions".
[4] One of the most interesting aspects of the busy beaver game is that, if it were possible to compute the functions Σ(n) and S(n) for all n, then this would resolve all mathematical conjectures which can be encoded in the form "does
[5] The n-state busy beaver game (or BB-n game), introduced in Tibor Radó'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).
and output the maximum score attainable by a Turing machine of that number of states by some measure.
[4] Moreover, this implies that it is undecidable by a general algorithm whether an arbitrary Turing machine is a busy beaver.
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).)
Each shift may write a 0 or a 1 on the tape, while Σ counts a subset of the shifts that wrote a 1, namely the ones that hadn't been overwritten by the time the Turing machine halted; consequently, S grows at least as fast as Σ, which had already been proved to grow faster than any computable function.
[14] In 2016, Adam Yedidia and Scott Aaronson obtained the first (explicit) upper bound on the minimum n for which S(n) is unprovable in ZFC.
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).
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.
[10] Alternatively a "busy beaver function" for diverse models of computation can be defined with Kolmogorov complexity.
[citation needed] So for the Reversal Turing Machine (RTM) class,[20] SRTM(6) ≥ 47339970 and ΣRTM(6) ≥ 6147.
Many open problems in mathematics could in theory, but not in practice, be solved in a systematic way given the value of S(n) for a sufficiently large n.[5][22] Theoretically speaking, the value of S(n) encodes the answer to all mathematical conjectures that can be checked in infinite time by a Turing machine with less than or equal to n states.
[6] Thus specific values (or upper bounds) for S(n) could be, in theory, used to systematically solve many open problems in mathematics.
[6] However, current results on the busy beaver problem suggest that this will not be practical for two reasons:[citation needed] Another property of S(n) is that no arithmetically sound, computably axiomatized theory can prove all of the function's values.
[6] If the theory is inconsistent, then all false statements are provable, and the Turing machine can be given the condition to halt if and only if it finds a proof of, for example,
[6] Exploring the relationship between computational universality and the dynamic behavior of Busy Beaver Turing machines, a conjecture was proposed in 2012[26] suggesting that Busy Beaver machines were natural candidates for Turing universality as they display complex characteristics, known for (1) their maximal computational complexity within size constraints, (2) their ability to perform non-trivial calculations before halting, and (3) the difficulty in finding and proving these machines; these features suggest that Busy Beaver machines possess the necessary complexity for universality.
In 1964 Milton Green developed a lower bound for the 1s-counting variant of the Busy Beaver function that was published in the proceedings of the 1964 IEEE symposium on switching circuit theory and logical design.
Heiner Marxen and Jürgen Buntrock described it as "a non-trivial (not primitive recursive) lower bound".
, because a blank tape has 0 ones), the recursion relations are as follows:[28] a This leads to two formulas, for odd and even numbers, for calculating the lower bound given by the Nth machine,
There exists a constant c, such that for all n ≥ 2:[29] The following table lists the exact values and some known lower bounds for S(n), Σ(n), and several other busy beaver functions.
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).
In the following table, the rules for each busy beaver (maximizing Σ) are represented visually, with orange squares corresponding to a "1" on the tape, and white corresponding to "0".
The diagram is compressed so only steps which change the tape are shown. Green and yellow triangles indicate regions where the Turing machine shuttles back and forth; the time taken is proportional to the areas of these colored triangles. The bottom row is an excerpt of the tape and the read/write head upon halting.
