login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A028444 Busy Beaver sequence, or Rado's sigma function: maximal number of 1's that an n-state Turing machine can print on an initially blank tape before halting. 9
0, 1, 4, 6, 13 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Expanded definition from Daniel Forgues: Busy Beaver sequence, or Rado's Sigma function: maximum number of 1s that an n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) halting Turing machine can print on an initially blank tape (all 0's) before halting.

States q and q+ in set Q_n of n distinct states (plus the Halt state,) tape symbols s and s+ in set S = {0, 1}, shift direction d+ in {LEFT, RIGHT} (NONE is excluded here,) + suffix meaning next and q+ = f(q, s), s+ = g(q, s), d+ = h(q, s).

The function Sigma(n) = Sigma(n, 2) (A028444) denotes the maximal number of tape marks (1s) which a halting Turing Machine H with n internal states, 2 symbols, and a two-way infinite tape can produce onto an initially blank tape (all 0's) and then halt. The function S(n) = S(n, 2) (A060843) denotes the maximal number of steps (thus shifts, since direction NONE is excluded) which a halting machine H can take (not necessarily the same Turing machine producing a maximum number of 1s and needs not even produce many tape marks.) For all n, S(n) >= Sigma(n).

Given that 5-state 2-symbol halting Turing machines can compute Collatz-like congruential functions (see references under A060843), it may be very hard to find the next term.

Rado's Sigma function grows faster than any computable function and is thus noncomputable.

From Daniel Forgues, Jun 05-06 2011: (Start)

H in H_(n, k) is a halting* Turing machine with n states and k symbols;

* (on a blank tape (all 0s) as input)

States q, q+ in set Q_n of n distinct states (plus the Halt state;)

Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol;)

Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here;)

sigma(H) is the number of non-blank symbols left on the tape by H;

s(H) is the number of steps (or shifts in our case) taken by H;

Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}

S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}

a(n) is Sigma(n) = Sigma(n, 2) since a 2-symbol BB-class Turing machine is assumed.

For all n, S(n, k) >= Sigma(n, k), k >= 2. (End)

REFERENCES

John Hopcroft, Turing Machines, Sci. Amer. vol. 250, #5, 86-98, May 1984, table on page 92 gives old lower bounds.

J. P. Jones, Recursive undecidability - an exposition, Amer. Math. Monthly, 81 (1974), 724-738.

H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, 1990.

Tibor Rado, On Noncomputable Functions, Bell System Technical Journal, vol. 41, # 3, 877-884, May 1963.

LINKS

Table of n, a(n) for n=0..4.

Daniel Forgues, Busy Beaver numbers

H. Marxen, Busy Beaver

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.

M. Somos, Busy Beaver Turing Machine

M. Somos, Busy Beaver

Eric Weisstein's World of Mathematics, Busy Beaver

Index entries for sequences related to Busy Beaver problem

CROSSREFS

Cf. A004147, A052200, A060843.

Sequence in context: A133454 A061072 A130435 * A003973 A034747 A168015

Adjacent sequences:  A028441 A028442 A028443 * A028445 A028446 A028447

KEYWORD

nonn,hard,nice

AUTHOR

Scott Aaronson (sja8(AT)cornell.edu)

EXTENSIONS

The next two terms are at least 4098 and 1.29*10^865.

Edited by Daniel Forgues, Mar 25 2010, Jun 05 2011

Edited by N. J. A. Sloane, Aug 30 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified August 29 18:25 EDT 2014. Contains 246200 sequences.