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

Author

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

Keywords

• nonn
• easy

Comments

The sequence is infinite and grows exponentially.

Examples

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

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

Programs

Mathematica

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

Formula

(4n+2)^(2n)

Extensions

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