Busy beaver

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: {{unordered list and produces three outputs: "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. An '''n-th busy beaver, BB-n' or simply "busy beaver" is a Turing machine that wins the n-state busy beaver game. Depending on definition, it either attains the highest score (denoted by Σ(n)), or runs for the longest time (S(n)), among all other possible n''-state competing Turing machines. Example The rules for one 1-state Turing machine might be: • In state 1, if the current symbol is 0, write a 1, move one space to the right, and transition to state 1 • In state 1, if the current symbol is 1, write a 0, move one space to the right, and transition to HALT This Turing machine would move to the right, swapping the value of all the bits it passes. Since the starting tape is all 0s, it would make an unending string of ones. This machine would not be a busy beaver contender because it runs forever on a blank tape. == Functions ==

In his original 1962 paper, Radó defined two functions related to the busy beaver game: the score function Σ(n) and the shifts function S(n). 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 proven to have complexity greater than k, and hence that no specific upper bound can be proven for Σ(k) (the latter is because "the complexity of n is greater than k" would be proven if were proven). 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; 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 , and there are infinitely many true-but-unprovable sentences of the form .) Maximum shifts function S In addition to the function Σ, Radó [1962] introduced another extreme function for Turing machines, the maximum shifts function, S, defined as follows: Turing machine whose behavior cannot be proven based on the usual axioms of set theory (Zermelo–Fraenkel set theory with the axiom of choice), under reasonable consistency hypotheses (stationary Ramsey property, equivalent to the existence of arbitrarily large subtle cardinals). Stefan O'Rear then reduced it to 1919 states, with the dependency on the stationary Ramsey property eliminated, and later to 748 states. Further improvements are reported on the BB Challenge web site. 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 established by reference to the blank tape halting problem. The blank tape halting problem is the problem of deciding for any Turing machine whether or not it will halt when started on an empty tape. The blank tape halting problem is equivalent to the standard halting problem and so it is also uncomputable. If S(n) was computable, then we could solve the blank tape halting problem simply by running any given Turing machine with n states for S(n) steps; if it has still not halted, it never will. So, since the blank tape halting problem is not computable, it follows that S(n) must likewise be uncomputable. Uncomputability of space(n) and num(n) Both \text{space}(n) and \text{num}(n) functions are uncomputable. This can be shown for \text{space}(n) by noting that every tape square a Turing machine writes a one to, it must also visit: in other words, \Sigma(n) \leq \text{space}(n). The \text{num}(n) function can be shown to be incomputable by proving, for example, that \text{space}(n) : this can be done by designing an (3n+3)-state Turing machine which simulates the n-state space champion, and then uses it to write at least \text{space}(n) contiguous ones to the tape. == Generalizations ==

Analogs of the shift function can be simply defined in any programming language, given that the programs can be described by bit-strings, and a program's number of steps can be counted. For example, the busy beaver game can also be generalized to two dimensions using Turing machines on two-dimensional tapes, or to Turing machines that are allowed to stay in the same place as well as move to the left and right. SRTM(6) ≥ and ΣRTM(6) ≥ . Likewise we could define an analog to the Σ function for register machines as the largest number which can be present in any register on halting, for a given number of instructions. Different numbers of symbols A simple generalization is the extension to Turing machines with m symbols instead of just two (0 and 1). Nondeterministic Turing machines The problem can be extended to nondeterministic Turing machines by looking for the system with the most states across all branches or the branch with the longest number of steps. The question of whether a given NDTM will halt is still computationally irreducible, and the computation required to find an NDTM busy beaver is significantly greater than the deterministic case, since there are multiple branches that need to be considered. For a 2-state, 2-color system with p cases or rules, the table to the right gives the maximum number of steps before halting and maximum number of unique states created by the NDTM. ==Applications==

Open mathematical problems In addition to posing a rather challenging mathematical game, the busy beaver functions Σ(n) and S(n) offer an entirely new approach to solving pure mathematics problems. 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. the value of S(6) is more than ^{^{^{^{9}2}2}}2, i.e. 2 tetrated to the 2 tetrated to the 2 tetrated to the 9 which is at least 2 pentated to the 5. The value of S(25), which is the number of steps the current program for the Goldbach conjecture would need to be run to give a conclusive answer, is incomprehensibly huge, and not remotely possible to write down, much less run a machine for, in the observable universe. • A 6-state Turing machine has been discovered that halts iff repeated applications of x_{n+1}=\left\lfloor\frac{3x_{n}}{2}\right\rfloor+2 starting from 4 ever produces twice as many odd values as even values. It was later named "Antihydra". Physical Church–Turing thesis The growth properties of the Busy Beaver function have implications for the behaviour of physical systems, assuming the truth of the physical Church–Turing thesis. If the physical Church–Turing thesis holds, and all physically computable functions are Turing-computable, then no directly measurable physical quantity can grow faster than the Busy Beaver function, as no Turing-computable function can grow faster than it. Simple functions of BB(n) would also impose a lower limit on growth rates, as well as upper and lower bounds on rates of convergence. == Known results ==

Lower bounds Green machines 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". This lower bound can be calculated but is too complex to state as a single expression in terms of n. This was done with a set of Turing machines, each of which demonstrated the lower bound for a certain . Relationships between busy beaver functions Trivially, because a machine that writes ones must take at least steps to do so. \begin{align} \operatorname{num}(n) & Ben-Amram and Petersen, 2002, also give an asymptotically improved bound on . There exists a constant such that for all , List of busy beavers These are tables of rules for Turing machines that generate Σ(1) and S(1), Σ(2) and S(2), Σ(3) (but not S(3)), Σ(4) and S(4), Σ(5) and S(5), and the best known lower bound for Σ(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 , halts at the position ) Result: 0 0 0 (1 step, one "1" total) Result: 0 0 1 1 1 0 0 (6 steps, four "1"s total) Result: 0 0 1 1 1 1 0 0 (14 steps, six "1"s total). This is one of several nonequivalent machines giving six 1s. Unlike the previous machines, this one is a busy beaver for Σ, but not for S. (S(3) = 21, and the machine obtains only five 1s.) Result: 0 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. Note in the image to the right how this solution is similar qualitatively to the evolution of some cellular automata. Result: more than 2↑↑↑5 "1"s in more than 2↑↑↑5 steps, where 2↑↑↑5 = 2↑↑2↑↑2↑↑2↑↑2 and ↑↑ represents tetration. ==Visualizations==

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 position of the head is indicated by the black ovoid, with the orientation of the head representing the state. Individual tapes are laid out horizontally, with time progressing from top to bottom. The halt state is represented by a rule which maps one state to itself (head doesn't move). ==See also==