|
| |
|
|
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.
|
|
3
|
|
|
|
1, 36, 10000, 7529536, 11019960576, 26559922791424, 95428956661682176, 478296900000000000000, 3189059870763703892770816, 27296360116495644500385071104, 291733167875766667063796853374976, 3807783932766699862493193563344470016, 59604644775390625000000000000000000000000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
Hector Zenil (hector.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
