A141475 Number of Turing machines with n states following the standard formalism of the busy beaver problem where the head of a Turing machine either moves to the right or to the left, but none once halted.

1, 36, 10000, 7529536, 11019960576, 26559922791424, 95428956661682176, 478296900000000000000, 3189059870763703892770816, 27296360116495644500385071104, 291733167875766667063796853374976, 3807783932766699862493193563344470016, 59604644775390625000000000000000000000000

Offset

0,2

Comments

The sequence is infinite and grows exponentially.

References

J. P. Delahaye and H. Zenil, "On the Kolmogorov-Chaitin complexity for short sequences,"Randomness and Complexity: From Leibniz to Chaitin, edited by C.S. Calude, World Scientific, 2007.

J. P. Delahaye and H. Zenil, "Towards a stable definition of Kolmogorov-Chaitin complexity", to appear in Fundamenta Informaticae, 2009.

T. Rado, On non-computable functions, Bell System Tech. J., 41 (1962), 877-884.

Links

Jason Yuen, Table of n, a(n) for n = 0..175

J. P. Delahaye and H. Zenil, Towards a stable definition of Kolmogorov-Chaitin complexity, arXiv:0804.3459 [cs.IT], 2008-2010.

Hector Zenil, The experimental AIT project

Hector Zenil, The smallest universal Turing machine implementation contest

Formula

(4n+2)^(2n)

Example

a(3) = 7529536 because the number of n-state 2-symbol Turing machines is 7529536 according to the formula (4n+2)^(2n).

Mathematica

Plus[Times[4, n], 2]^Times[2, n]

Crossrefs

Sequence in context: A233171 A058466 A277603 * A233126 A201003 A271335

Adjacent sequences: A141472 A141473 A141474 * A141476 A141477 A141478

Keyword

nonn,easy

Author

Hector Zenil (hector.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008

Extensions

a(0)=1 inserted by Jason Yuen, Jul 10 2024

Status

approved