This site is supported by donations to The OEIS Foundation.

Busy Beaver numbers

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


This article needs more work.

Please help by expanding it!


In the following, we consider a halting (on a blank tape, i.e. all 0s) Turing machine with states and elements of set of distinct states (excluding the halting state,) tape symbols and elements of set = {0, 1}, shift direction element of = {LEFT (-1,) RIGHT (+1)} (NONE (0) is not considered here,) suffix meaning next and represented by the 5-tuple .

Two definitions for busy beavers

Busy beavers are halting (on a blank tape, i.e. all 0s) Turing machines which compete in either of two ways

  • maximize the number of steps (or shifts since direction NONE is excluded,)
  • maximize the number of tape marks (non-blank symbols 0 on the tape) once halting.

Define as the number of steps (or shifts since direction NONE is excluded) taken by a halting Turing machine once halted, and by the number of tape marks (non-blank symbols 0) left on the tape by once halted.

Define as the number of steps taken by a halting Turing machine with states and symbols which took the maximum number of steps

* (on a blank tape, i.e. all 0s)

Define as the number of tape marks (non-blank symbols 0) left on the tape by a halting Turing machine with states and symbols which leaves the most tape marks (non-blank symbols) on the tape once halted

* (on a blank tape, i.e. all 0s)

Rado's sigma function

The busy beaver function, Rado's sigma function Sigma(n)[1], , (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ó [2] 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, [3]

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

Sequences

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. (Cf. A028444)

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

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. (Cf. A060843)

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

Number of -state, 2-symbol, in {LEFT, RIGHT}, 5-tuple () (halting or not) Turing machines. (Cf. A052200)

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

See also



Notes

  1. Radó [1962].
  2. Computer Studies of Turing Machine Problems, 1965.
  3. Ben-Amram, et al., [1996].
  4. Ben-Amram, Petersen [2002].

External links