Jump to content

Busy beaver

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 50.206.176.154 (talk) at 06:03, 31 January 2021 (Exact values and lower bounds). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that produces the most output possible.[1] Since an endlessly looping program producing infinite output is easily conceived, such programs are excluded from the game.

More precisely, the busy beaver game consists of designing a halting, binary-alphabet Turing machine which writes the most 1s on the tape, using only a given set of states. The rules for the 2-state game are as follows:

  1. the machine must have two states in addition to the halting state, and
  2. the tape initially contains 0s only.

A player should conceive a transition table aiming for the longest output of 1s on the tape while making sure the machine will halt eventually.

An nth busy beaver, BB-n or simply "busy beaver" is a Turing machine that wins the n-state Busy Beaver Game. That is, it attains the largest number of 1s among all other possible n-state competing Turing Machines. The BB-2 Turing machine, for instance, achieves four 1s in six steps.

Determining whether an arbitrary Turing machine is a busy beaver is undecidable. This has implications in computability theory, the halting problem, and complexity theory. The concept was first introduced by Tibor Radó in his 1962 paper, "On Non-Computable Functions".[1]

The game

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:

  • 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:
  1. the current non-Halt state,
  2. the symbol in the current tape cell,
and produces three outputs:
  1. a symbol to write over the symbol in the current tape cell (it may be the same symbol as the symbol overwritten),
  2. 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
  3. a state to transition into (which may be the Halt state).
There are thus (4n + 4)2n n-state Turing machines meeting this definition.
A more broken-down version of the same formula is (symbols * directions * (states + 1))(symbols * states).
The transition function may be seen as a finite table of 5-tuples, each of the form
(current state, current symbol, symbol to write, direction of shift, next state).

"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.)

The busy beaver function Σ

The busy beaver function quantifies the maximum score attainable by a Busy Beaver on a given measure. This is a noncomputable function. Also, a busy beaver function can be shown to have a greater growth rate[2] asymptotically than any computable function.

The busy beaver function, Σ: NN, 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.

It is clear that Σ is a well-defined function: for every n, there are at most finitely many n-state Turing machines as above, up to isomorphism, hence at most finitely many possible running times.

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 four n-state busy beavers (because, given any n-state busy beaver, another is obtained by merely changing the shift direction in a halting transition, another by shifting all direction changes to their opposite, and the final by shifting the halt direction of the all-swapped busy beaver).

Non-computability

Radó's 1962 paper proved that if f: 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).)

Even though Σ(n) is an uncomputable function, there are some small n for which it is possible to obtain its values and prove that they are correct. 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 (sequence A028444 in the OEIS). Σ(n) has not yet been determined for any instance of n > 4, although lower bounds have been established (see the Known values section below).

In 2016, Adam Yedidia and Scott Aaronson obtained the first (explicit) upper bound on the minimum n for which Σ(n) is unprovable in ZFC. To do so they constructed a 7910-state[3] 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).[4][5] This was later reduced to 1919 states, with the dependency on the stationary Ramsey property eliminated,[6][7] and later to 748 states.[8]

Complexity and unprovability of Σ

A variant of Kolmogorov complexity 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 be 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; 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".)

Maximum shifts function S

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:

  • s(M) = the number of shifts M makes before halting, for any M in En,
  • S(n) = max{ s(M) | MEn } = 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). 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.

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,

tends to be close to the square of , and in fact many machines give less than .

Known values for Σ and S

As of 2016 the function values for Σ(n) and S(n) are only known exactly for n < 5.[5]

The current (as of 2018) 5-state busy beaver champion produces 4098 1s, using 47176870 steps (discovered by Heiner Marxen and Jürgen Buntrock in 1989), but there remain 18 or 19 (possibly under 10, see below) machines with non-regular behavior which are believed to never halt, but which have not been proven to run infinitely. Skelet lists 42 or 43 unproven machines, but 24 are already proven.[9] The remaining machines have been simulated to 81.8 billion steps, but none halted. Daniel Briggs also proved some machines.[10] Another source says 98 machines remain unproven. There is an analysis of holdouts.[11] So, it is likely that Σ(5) = 4098 and S(5) = 47176870, but this remains unproven, and it is unknown if there are any holdouts left (as of 2018). At the moment the record 6-state champion produces over 3.515×1018267 1s (exactly (25*430341+23)/9), using over 7.412×1036534 steps (found by Pavel Kropitz in 2010). As noted above, these are 2-symbol Turing machines.

A simple extension of the 6-state machine leads to a 7-state machine which will write more than 1010101018705353 1s to the tape, but there are undoubtedly much busier 7-state machines. However, other busy beaver hunters have different sets of 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 333 = 7625597484987 terms in the exponential tower), and

where the number g1 is the enormous starting value in the sequence that defines Graham's number.

In 1964 Milton Green developed a lower bound for 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. When n=8 the method gives Σ(8) ≥ 3 × (7 × 392 - 1) / 2 ≈ 8.248×1044.

It can be derived from current lower bounds that:

In contrast, the best current (as of 2018) lower bound on Σ(6) is 1018267, which is greater than the lower bound given by Green's formula, 33 = 27 (which is tiny in comparison). In fact, it is much greater than the lower bound: 3 ↑↑ 3 = 333 = 7625597484987, which is Green's first lower bound for Σ(8), and also much greater than the second lower bound: 3*(7*392-1)/2.

Σ(7) is by the same way much, much greater than current common lower bound 331 (nearly 618 trillion), so the second lower bound is also very, very weak.

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.

Generalizations

For any model of computation 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:

  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 119112334170342540 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 6147 1s after 47339970 steps. So SRTM(6) ≥ 47339970 and ΣRTM(6) ≥ 6147.

It is possible to further generalize the busy beaver function by extending to more than one dimension.

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.

Exact values and lower bounds

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. 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 smaller machine.

The Turing machines that achieve these values are available on Pascal Michel's webpage. 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)
n
m
2-state 3-state 4-state 5-state 6-state 7-state
2-symbol 6 21 107 47176870 ? > 7.4×1036534 > 1010101018705353
3-symbol 38 119112334170342540 > 1.0×1014072 ? ? ?
4-symbol 3932964 > 5.2×1013036 ? ? ? ?
5-symbol > 1.9×10704 ? ? ? ? ?
6-symbol > 2.4×109866 ? ? ? ? ?
Values of Σ(n, m)
n
m
2-state 3-state 4-state 5-state 6-state 7-state
2-symbol 4 6 13 4098 ? > 3.5×1018267 > 1010101018705353
3-symbol 9 374676383 > 1.3×107036 ? ? ?
4-symbol 2050 > 3.7×106518 ? ? ? ?
5-symbol > 1.7×10352 ? ? ? ? ?
6-symbol > 1.9×104933 ? ? ? ? ?

Applications

In addition to posing a rather challenging mathematical game, the busy beaver functions 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.[12]

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 two primes in our example), it halts and indicates that. 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 five 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 S(10) > Σ(10) > 3 ↑↑↑ 3 is a gigantic number and S(17) > Σ(17) > G, where G is Graham's number - an enormous 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 part of the universe to have performed even S(6) operations directly.[13]

Notable instances

A 748-state binary Turing machine has been constructed that halts iff ZFC is inconsistent.[14] A 744-state Turing machine has been constructed that halts iff the Riemann hypothesis is false.[6][14] A 43-state Turing machine has been constructed that halts iff Goldbach's conjecture is false, and a 27-state machine for that conjecture has been proposed but not yet verified.[6][14]

Examples

Shows the first 100,000 timesteps of the current best 5-state busy beaver, generated in the Wolfram Language. Orange is "1", white is "0" (image compressed vertically).

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). For other visualizations, WolframAlpha is able to compute the game for general set-ups, e.g. 4-state 2-symbol.

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

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[15]
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).

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, see image)

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.

Note in the image to the right how this solution is similar qualitatively to the evolution of some cellular automata. For finer detail, the system can be calculated on WolframAlpha.

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.

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 vertically. The halt state is represented by a rule which maps one state to itself (head doesn't move). These graphics were created using the function TuringMachine in the Wolfram Language.

Evolution of Busy Beavers with 1-4 States
Rules for 1-state busy beaver.
Rules for 2-state busy beaver.
Rules for 3-state busy beaver.
Rules for 4-state busy beaver.
Evolution of 1-state busy beaver until halt. The initial state triggers a halt, with a single "1" being written before termination.
Evolution of 2-state busy beaver until halt.
Evolution of 3-state busy beaver until halt.
Evolution of 4-state busy beaver until halt. Bottom line in left image wraps to top line of right image.

See also

Notes

  1. ^ a b Radó, Tibor (May 1962). "On non-computable functions" (PDF). Bell System Technical Journal. 41 (3): 877–884. doi:10.1002/j.1538-7305.1962.tb00480.x.
  2. ^ Wolfram, Stephen (2002). A New Kind of Science. Champaign, IL: Wolfram Media. p. 1162. ISBN 1-57955-008-8.
  3. ^ Adam Yedidia and Scott Aaronson (May 2016). A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory (Technical Report). MIT. arXiv:1605.04343. Bibcode:2016arXiv160504343Y.
  4. ^ Aron, Jacob. "This Turing machine should run forever unless maths is wrong". Retrieved 2016-09-25.
  5. ^ a b Version from May 3rd contained 7918 states: "The 8000th Busy Beaver number eludes ZF set theory". Shtetl-Optimized blog. 2016-05-03. Retrieved 2016-09-25.
  6. ^ a b c "Three announcements". Shtetl-Optimized blog. 2016-05-03. Retrieved 2018-04-27.
  7. ^ "GitHub - sorear/metamath-turing-machines: Metamath proof enumerators and other things". 2019-02-13.
  8. ^ "The Busy Beaver Frontier" (PDF).
  9. ^ Busy Beaver nonregular machines for class TM(5)
  10. ^ Turing: A Project to Finish Busy Beaver of 5
  11. ^ The Busy Beaver Problem : A NEW MILLENNIUM ATTACK
  12. ^ Chaitin 1987
  13. ^ Lloyd 2001. Computational Capacity of the Universe.
  14. ^ a b c Pavlus, John. "How the Slowest Computer Programs Illuminate Math's Fundamental Limits". Quanta Magazine. Retrieved 2020-12-11.
  15. ^ Lin, Shen; Rado, Tibor (April 1965). "Computer studies of Turing machine problems". Journal of the ACM. 12 (2): 196–212.

References