Busy Beaver numbers

This article needs more work.

Please help by expanding it!

Busy Beavers are halting Turing machines $H\in {\mathcal {H}}_{(n,k)}$ with n active states $q$ (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.

[edit preamble (sect.0)]

Two definitions for busy beavers

Let $\,{\mathcal {H}}(n,k)\,$ be the set of all Turing machines with $n$ states and $k$ 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 $s\in \{0,1\}$, i.e., $k=2$, but more general BB's are considered in the literature.

Busy beavers are Turing machines $\,H\in {\mathcal {H}}(n,k)\,$ which compete in either of two ways:

• maximize $s(H)$, the number of steps (or shifts, since direction NONE is excluded) taken by a Turing machine $H\in {\mathcal {H}}(n,k)$ started on a blank tape, once it has halted,

• maximize $\sigma (H)$, the number of tape marks (non-blank symbols left on an initially blank tape) by the Turing machine $H\in {\mathcal {H}}(n,k)$, once halted.
  (The machine may write many more non-blank symbols, but overwrite some of them by zeros.)

Correspondingly, we define $S(n,k)$ and $\Sigma (n,k)$ as the maxima reached by these two functions:

$S(n,k)=\max \,\{\,s(H):H\in {\mathcal {H}}(n,k)\,\}~,$

$\Sigma (n,k)=\max \,\{\,\sigma (H):H\in {\mathcal {H}}(n,k)\,\}~.$

Rado's sigma function

The busy beaver function, Rado's sigma function Sigma(n), $\scriptstyle \Sigma :\,n\,\to \,n\,$, (A028444) is defined such that $\scriptstyle \Sigma (n)\,\equiv \,\Sigma (n,2)\,$ is the maximum attainable score (the maximum number of 1s finally on the tape) among all $\scriptstyle n\,$-state, 2-symbol halting Turing machines (TM) $\scriptstyle H\,\in \,H_{(n,2)}\,$ of the above-described type, when started on a blank tape (all 0s.)

Radó showed that $\scriptstyle \Sigma \,$ is a well-defined function; that is, for every $\scriptstyle n\,$, the $\scriptstyle n\,$-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 $\scriptstyle f\,$, there is an integer $\scriptstyle N\,$ such that, $\scriptstyle \forall n\,>\,N\,$, we have $\scriptstyle \Sigma (n)\,\equiv \,\Sigma (n,2)\,>\,f(n)\,$) and is therefore a noncomputable function.

There are finitely many (halting or not) Turing machines $\scriptstyle T\,\in \,T_{(n,2)}\,$ with $\scriptstyle n\,$ states and 2 symbols, specifically there are $\scriptstyle [2k(n+1)]^{nk}|_{(k\,=\,2)}\,=\,[4(n+1)]^{2n}\,$ (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 $\scriptstyle n\,$-state, 2-symbol halting Turing machine $\scriptstyle H\,\in \,H_{(n,2)}\,$, for every $\scriptstyle n\,$. Now define

• $\scriptstyle H_{n}\,\equiv \,H_{(n,2)}\,$ is the finite, nonempty set of halting $\scriptstyle n\,$-state 2-symbol Turing machines $\scriptstyle H\,$ of the type described above (two-way infinite tape, transition function defined by 5-tuples, etc.)
• $\scriptstyle \sigma (H)\,$, for each halting Turing machine $\scriptstyle H\,\in \,H_{(n,2)}\,$, is the score of machine $\scriptstyle H\,$ — the number of 1s finally on the tape after machine $\scriptstyle H\,$ is run to completion with an initially blank tape (all 0s.)
• $\scriptstyle \Sigma (n)\,\equiv \,\Sigma (n,2)\,=\,\max\{\sigma (H)\,|\,H\,\in \,H_{(n,2)}\}\,$ (i.e., the maximum score among all $\scriptstyle n\,$-state 2-symbol halting Turing machines $\scriptstyle H\,$ started with a blank tape.)

Since $\scriptstyle \sigma (H)\,$ is a nonnegative integer for any $\scriptstyle H\,\in \,H_{(n,2)}\,$, and since $\scriptstyle H_{(n,2)}\,$ is a nonempty finite set, $\scriptstyle \Sigma (n)\,$ is a well-defined nonnegative integer for every nonnegative integer $\scriptstyle n\,$.

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

Maximum shifts function

In addition to the $\scriptstyle \Sigma \,$ function, Radó [1962] introduced another extreme function for the BB-class Turing machines, the maximum shifts function, $\scriptstyle S(n)\,$, defined as

• $\scriptstyle s(H)\,=\,\,$ the number of shifts (thus steps, since direction NONE (0) is excluded) $\scriptstyle H\,$ makes before halting, for any $\scriptstyle H\,\in \,H_{(n,2)}\,$,
• $\scriptstyle S(n)\,=\,\max\{s(H)\,|\,H\,\in \,H_{(n,2)}\}\,=\,\,$ the largest number of shifts (thus steps, since direction NONE (0) is excluded) made by any halting $\scriptstyle n\,$-state 2-symbol halting Turing machine $\scriptstyle H\,$ (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 $\scriptstyle S\,$ is noncomputable for the same reason that $\scriptstyle \Sigma \,$ is noncomputable — it grows faster than any computable function. He proved this simply by noting that $\scriptstyle \forall n,\,S(n)\,\geq \,\Sigma (n)\,$, because a shift is required to write a 1 on the tape; consequently, $\scriptstyle S\,$ grows at least as fast as $\scriptstyle \Sigma \,$, which had already been proved to grow faster than any computable function.

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

Inequalities relating $\scriptstyle \Sigma \,$ and $\scriptstyle S\,$ include the following,

$S(n,k)\geq \Sigma (n,k),\quad k\,\geq \,2,\,n\,\geq \,1,\,$

$S(n,2)\leq (2n-1)~\Sigma (3n+3,2),\quad n\,\geq \,1,\,$

$S(n,2)<\Sigma (3n+6,2),\quad n\,\geq \,1,\,$

and an asymptotically improved bound: there exists a constant $\scriptstyle c\,$, such that

$S(n,2)\leq \Sigma {\Bigg (}n+{\Bigg \lceil }{\frac {8n}{\log _{2}n}}{\Bigg \rceil }+c,2{\Bigg )},\quad n\,\geq \,2.\,$

Sequences

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

{0, 1, 4, 6, 13, ≥ 4098, ≥ 1.29 · 10⁸⁶⁵, ...}

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

{1, 6, 21, 107, ≥ 47176870, ≥ 3 · 10¹⁷³⁰, ...}

A052200(n) = (4(n+1))²ⁿ = number of $\scriptstyle n\,$-state, 2-symbol, $\scriptstyle d+\,$ in {LEFT, RIGHT}, 5-tuple ($\scriptstyle q,\,s,\,q+,\,s+,\,d+\,$) (halting or not) Turing machines:

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

See also

• Index entries for sequences related to Busy Beaver problem

• BB-class Turing machine
• Turing machines
• Universal Turing machine
• Halting problem

• Computable numbers and noncomputable numbers
• Computable sequences and noncomputable sequences
• Computable functions and noncomputable functions

External links

• Weisstein, Eric W., Busy Beaver, from MathWorld—A Wolfram Web Resource.
• Busy beaver—Wikipedia.org.
• Bryan Clair, The Biggest Numbers in the Universe, Strange Horizons, 2001.
• Pascal Michel, Historical survey of Busy Beavers, 2011.
• Pascal Michel, Behavior of busy beavers, 2010.
• Pascal Michel, The Busy Beaver Competitions, 2010.
• Pascal Michel, The Busy Beaver Competition: a historical survey, arXiv, 2010.