A052200 Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines.

1, 64, 20736, 16777216, 25600000000, 63403380965376, 232218265089212416, 1180591620717411303424, 7958661109946400884391936, 68719476736000000000000000000, 739696442014594807059393047166976, 9711967541295580042210555933809967104, 152784834199652075368661148843397208866816

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 0's, 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)

Links

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

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

Michael Somos, The Busy Beaver Problem

OEIS Wiki, Busy Beaver numbers

Index entries for sequences related to Busy Beaver problem

Formula

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

Example

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

Mathematica

A052200[n_]:=(4(n+1))^(2n); Array[A052200, 20, 0] (* Paolo Xausa, May 21 2023 *)

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