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

 Hints (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)
 OFFSET 0,2 COMMENTS 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) REFERENCES J. P. Jones, Recursive undecidability - an exposition, Amer. Math. Monthly, 81 (1974), 724-738. LINKS M. Somos, The Busy Beaver Problem OEIS Wiki, Busy Beaver numbers FORMULA a(n) = (4*(n+1))^(2*n). EXAMPLE a(1) = 64 = (4*1+4)^(2*1) = 8^2. CROSSREFS Cf. A028444, A004147, A060843. Sequence in context: A089208 A083282 A082502 * A146517 A009497 A145258 Adjacent sequences:  A052197 A052198 A052199 * A052201 A052202 A052203 KEYWORD nonn,easy AUTHOR Michael Somos, Jan 28 2000 EXTENSIONS Entry revised by N. J. A. Sloane, Feb 08 2007 Edited by Daniel Forgues, Mar 25 2010 STATUS approved

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.

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