This site is supported by donations to The OEIS Foundation.

Busy Beaver numbers

From OeisWiki
(Redirected from Busy Beaver problem)
Jump to: navigation, search


This article needs more work.

Please help by expanding it!


Busy Beavers are halting Turing machines with n active states (in addition to the HALT state), operating on an infinite tape which holds any of k distinct symbols. They compete for the maximum number of steps completed, or the maximum number of nonzero symbols left on the tape once they halt, when started on an initially blank tape.

Two definitions for busy beavers

Let be the set of all Turing machines with states and symbols that halt when started on a blank (i.e., all zeros) tape. (Throughout this page, "blank", "zero" and '0' are synonyms.) In this context, usually only shifts { LEFT (-1) and RIGHT (+1) } are allowed, while d+ = NONE (0) is excluded. The original Busy Beaver problem considers , i.e., , but more general BB's are considered in the literature[1].

Busy beavers are Turing machines which compete in either of two ways:

  • maximize , the number of steps (or shifts, since direction NONE is excluded) taken by a Turing machine started on a blank tape, once it has halted,
  • maximize , the number of tape marks (non-blank symbols left on an initially blank tape) by the Turing machine , once halted.
    (The machine may write many more non-blank symbols, but overwrite some of them by zeros.)

Correspondingly, we define and as the maxima reached by these two functions:

Rado's sigma function

The busy beaver function, Rado's sigma function Sigma(n)[2], , (A028444) is defined such that is the maximum attainable score (the maximum number of 1s finally on the tape) among all -state, 2-symbol halting Turing machines (TM) of the above-described type, when started on a blank tape (all 0s.)

Radó showed that is a well-defined function; that is, for every , the -state, 2-symbol 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. Rado's sigma function grows faster than any computable function (i.e., for any computable function , there is an integer such that, , we have ) and is therefore a noncomputable function.

There are finitely many (halting or not) Turing machines with states and 2 symbols, specifically there are (halting or not) Turing machines, if we don't consider the state after halting.) In addition it is trivial to see that some of these are halting machines; i.e., there exists at least one -state, 2-symbol halting Turing machine , for every . Now define

  • is the finite, nonempty set of halting -state 2-symbol Turing machines of the type described above (two-way infinite tape, transition function defined by 5-tuples, etc.)
  • , for each halting Turing machine , is the score of machine — the number of 1s finally on the tape after machine is run to completion with an initially blank tape (all 0s.)
  • (i.e., the maximum score among all -state 2-symbol halting Turing machines started with a blank tape.)

Since is a nonnegative integer for any , and since is a nonempty finite set, is a well-defined nonnegative integer for every nonnegative integer .

This infinite sequence is the busy beaver function, and any -state 2-symbol halting Turing machine for which (i.e., which attains the maximum score) is called a busy beaver. Note that for each , there exists at least two -state busy beavers (because, given any -state busy beaver, another is obtained by merely changing the shift direction in a halting transition.)

Maximum shifts function

In addition to the function, Radó [1962] introduced another extreme function for the BB-class Turing machines, the maximum shifts function, , defined as

  • the number of shifts (thus steps, since direction NONE (0) is excluded) makes before halting, for any ,
  • the largest number of shifts (thus steps, since direction NONE (0) is excluded) made by any halting -state 2-symbol halting Turing machine (not necessarily the same Turing machine producing a maximum number of tape marks, i.e. 1s, and needs not even produce many tape marks.) (Cf. A060843)

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 is noncomputable for the same reason that is noncomputable — it grows faster than any computable function. He proved this simply by noting that , because a shift is required to write a 1 on the tape; consequently, grows at least as fast as , which had already been proved to grow faster than any computable function.

The following connection between and was used by Lin & Radó [3] to prove that . For a given , if is known then all -state Turing machines can (in principle) be run for up to 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 . The approach used by Lin & Radó for the case of was to conjecture that , 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 , and determining that by the procedure just described.

Inequalities relating and include the following, [4]

and an asymptotically improved bound[5]: there exists a constant , such that

Sequences

A028444 = Busy Beaver sequence, or Rado's sigma function: maximum number of 1s that an -state, 2-symbol, in {LEFT, RIGHT}, 5-tuple () halting Turing machine can print on an initially blank tape (all 0s) before halting ():

{0, 1, 4, 6, 13, ≥ 4098, ≥ 1.29 · 10865, ...}

A060843 = Busy Beaver problem: is the maximal number of steps that an -state, 2-symbol, in {LEFT, RIGHT}, 5-tuple () halting Turing machine can make on an initially blank tape (all 0s) before halting ():

{1, 6, 21, 107, ≥ 47176870, ≥ 3 · 101730, ...}

A052200(n) = (4(n+1))2n = number of -state, 2-symbol, in {LEFT, RIGHT}, 5-tuple () (halting or not) Turing machines:

{1, 64, 20736, 16777216, 25600000000, 63403380965376, 232218265089212416, 1180591620717411303424, 7958661109946400884391936, 68719476736000000000000000000, ...}

See also



Notes

  1. Heiner Marxen, "Busy Beaver", http://web.archive.org/web/20140717022943/http://www.drb.insel.de/~heiner/BB/macro.html (last updated in 2014)
  2. Radó [1962].
  3. Computer Studies of Turing Machine Problems, 1965.
  4. Ben-Amram, et al., [1996].
  5. Ben-Amram, Petersen [2002].

External links