This site is supported by donations to The OEIS Foundation.



Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

(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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 3 07:27 EST 2016. Contains 278698 sequences.