This site is supported by donations to The OEIS Foundation.



Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A052200 Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines. 5
1, 64, 20736, 16777216, 25600000000, 63403380965376, 232218265089212416, 1180591620717411303424, 7958661109946400884391936, 68719476736000000000000000000, 739696442014594807059393047166976, 9711967541295580042210555933809967104, 152784834199652075368661148843397208866816 (list; graph; refs; listen; history; text; internal format)



T in T_(n, k) is a Turing machine with n states and k symbols;

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;)

+ suffix meaning next and q+ = f(q, s), s+ = g(q, s), d+ = h(q, s).

This sequence is computable. On the other hand, the busy beaver numbers are noncomputable, found only by examining each of the many n-state Turing machine programs' halting. - Michael Joseph Halm, Apr 29 2003

From Daniel Forgues, Jun 06 2011: (Start)

RE: Busy beaver halting Turing machines:

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

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

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}

Cf. A028444 for Sigma(n, 2), A060843 for S(n, 2). (End)


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


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

M. Somos, The Busy Beaver Problem

Index entries for sequences related to Busy Beaver problem

OEIS Wiki, Busy Beaver numbers


a(n) = (4*(n+1))^(2*n).


a(1) = 64 = (4*1+4)^(2*1) = 8^2.


Cf. A028444, A004147, A060843.

Sequence in context: A089208 A083282 A082502 * A146517 A009497 A145258

Adjacent sequences:  A052197 A052198 A052199 * A052201 A052202 A052203




Michael Somos, Jan 28 2000


Entry revised by N. J. A. Sloane, Feb 08 2007

Edited by Daniel Forgues, Mar 25 2010



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 11 13:08 EST 2018. Contains 318049 sequences. (Running on oeis4.)