Busy Beaver numbers

From OeisWiki

Current revision (unreviewed)

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 $\scriptstyle H \,\in\, H_{(n, 2)} \,$ with states $\scriptstyle q \,$ and $\scriptstyle q+ \,$ elements of set $\scriptstyle Q_n \,$ of $\scriptstyle n \,$ distinct states (excluding the halting state,) tape symbols $\scriptstyle s \,$ and $\scriptstyle s+ \,$ elements of set $\scriptstyle S_2 \,$ = {0, 1}, shift direction $\scriptstyle d+ \,$ element of $\scriptstyle D_2 \,$ = {LEFT (-1,) RIGHT (+1)} (NONE (0) is not considered here,) $\scriptstyle + \,$ suffix meaning next and $\scriptstyle q+ \,=\, f(q, s),\, s+ \,=\, g(q, s),\, d+ \,=\, h(q, s), \,$ represented by the 5-tuple $\scriptstyle (q,\, s,\, q+,\, s+,\, d+) \,$ .

Two definitions for busy beavers

Busy beavers are halting (on a blank tape, i.e. all 0s) Turing machines $\scriptstyle H \,$ 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 $\scriptstyle s(H) \,$ as the number of steps (or shifts since direction NONE is excluded) taken by a halting Turing machine $\scriptstyle H \,$ once halted, and by $\scriptstyle \sigma(H) \,$ the number of tape marks (non-blank symbols 0) left on the tape by $\scriptstyle H \,$ once halted.

Define $\scriptstyle S(n, k) \,$ as the number of steps taken by a halting Turing machine $\scriptstyle H \,$ with $\scriptstyle n \,$ states and $\scriptstyle k \,$ symbols which took the maximum number of steps

$S(n, k) = \max \{s(H) : H {\rm ~is~a~halting^{*}~Turing~machine~with~} n {\rm ~states~and~} k {\rm ~symbols}\} \,$

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

Define $\scriptstyle \Sigma(n, k) \,$ as the number of tape marks (non-blank symbols 0) left on the tape by a halting Turing machine $\scriptstyle H \,$ with $\scriptstyle n \,$ states and $\scriptstyle k \,$ symbols which leaves the most tape marks (non-blank symbols) on the tape once halted

$\Sigma(n, k) = \max \{\sigma(H) : H {\rm ~is~a~halting^{*}~Turing~machine~with~} n {\rm ~states~and~} k {\rm ~symbols}\} \,$

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

Rado's sigma function

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

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

$S(n, 2) \le (2n-1) ~ \Sigma(3n+3, 2),\quad n \,\ge\, 1, \,$

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

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

$S(n, 2) \le \Sigma\Bigg(n + \Bigg\lceil \frac{8n}{\log_{2} n} \Bigg\rceil + c, 2\Bigg),\quad n \,\ge\, 2. \,$

Sequences

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. (Cf. A028444 $\scriptstyle (n),\, n \,\ge\, 0 \,$ )

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

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. (Cf. A060843 $\scriptstyle (n),\, n \,\ge\, 1 \,$ )

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

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

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

Notes

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

External links

Weisstein, Eric W., Busy Beaver, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/BusyBeaver.html]
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.

[0] Radó [1962].

[1] Computer Studies of Turing Machine Problems, 1965.

[2] Ben-Amram, et al., [1996].

[3] Ben-Amram, Petersen [2002].

[1]

[2]

[3]

[4]

Busy Beaver numbers

From OeisWiki

Contents

Two definitions for busy beavers

Rado's sigma function

Maximum shifts function

Sequences

See also

Notes

External links

Views

Personal tools

Navigation

Search

Toolbox