login
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.
3

%I #19 Jul 10 2024 09:37:07

%S 1,36,10000,7529536,11019960576,26559922791424,95428956661682176,

%T 478296900000000000000,3189059870763703892770816,

%U 27296360116495644500385071104,291733167875766667063796853374976,3807783932766699862493193563344470016,59604644775390625000000000000000000000000

%N 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.

%C The sequence is infinite and grows exponentially.

%D 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.

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

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

%H Jason Yuen, <a href="/A141475/b141475.txt">Table of n, a(n) for n = 0..175</a>

%H J. P. Delahaye and H. Zenil, <a href="http://arxiv.org/abs/0804.3459">Towards a stable definition of Kolmogorov-Chaitin complexity</a>, arXiv:0804.3459 [cs.IT], 2008-2010.

%H Hector Zenil, <a href="http://www.mathrix.org/experimentalAIT/">The experimental AIT project</a>

%H Hector Zenil, <a href="http://www.mathrix.org/experimentalAIT/TuringMachine.html">The smallest universal Turing machine implementation contest</a>

%F (4n+2)^(2n)

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

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

%K nonn,easy

%O 0,2

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

%E a(0)=1 inserted by _Jason Yuen_, Jul 10 2024