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

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

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 | 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 September 2 22:02 EDT 2014. Contains 246369 sequences.