Busy beaver - WikiHQ

thumb|upright=1.6|This "space–time diagram" shows the state of the memory tape on a row for the first 100,000 timesteps of the 5-state busy beaver from top to bottom. Orange is "1", white is "0" (image compressed vertically).

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. Since an endlessly looping program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game.

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. The n-state busy beaver game consists of finding the longest-running or highest-scoring Turing machine which has n states and eventually halts. The concept of a busy beaver was first introduced by Tibor Radó in his 1962 paper, "On Non-Computable Functions". Many other problems, including the Riemann hypothesis (744 states) and the consistency of ZF set theory (745 states), can be expressed in a similar form, where at most a countably infinite number of cases need to be checked. Depending on definition, it either attains the highest score (denoted by Σ(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. 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

{| class="wikitable" align="right"

|+ Maximal halting times and states from p-case, 2-state, 2-color NDTM

! p

! steps

! states

! 1

| 2 || 2

! 2

| 4 || 4

! 3

| 6 || 7

! 4

| 7 || 11

! 5

| 8 || 15

! 6

| 7 || 18

! 7

| 6 || 18

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 value of S(6) is more than <math>^{^{^{^{9}2}22</math>, 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 <math display="inline">x_{n+1}=\left\lfloor\frac{3x_{n{2}\right\rfloor+2</math> 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 <math>BB(n)</math> would also impose a lower limit on growth rates, as well as upper and lower bounds on rates of convergence. 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.

<math display="block">\begin{align}

\operatorname{num}(n) &< \Sigma(n)\\

S(n) &< \operatorname{num}(n + o(n))\\

S(n) &< \operatorname{num}(3n+6)

\end{align}</math>

Ben-Amram and Petersen, 2002, also give an asymptotically improved bound on . There exists a constant such that for all ,

|> 2<math>\uparrow\uparrow\uparrow</math>5

List of busy beavers

thumb|upright=1.8|A zoomed-out space-time diagram of the 5-state busy beaver machine. The diagram is modified so only steps which change the tape are shown, leading to triangular shapes appearing in the diagram. 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.

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 )

{| class="wikitable"

|+ 1-state, 2-symbol busy beaver

! width="20px" |

! A

! 0

| 1RH

! 1

| (not used)

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

{| class="wikitable"

|+ 2-state, 2-symbol busy beaver

! width="20px" |

! A

! B

! 0

| 1RB

| 1LA

! 1

| 1LB

| 1RH

Result: 0 0 1 1 1 0 0 (6 steps, four "1"s total)

thumb|Animation of a 3-state, 2-symbol busy beaver

{| class="wikitable"

|+ 3-state, 2-symbol busy beaver

! width="20px" |

! A

! B

! C

! 0

| 1RB

| 0RC

| 1LC

! 1

| 1RH

| 1RB

| 1LA

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.