|
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,1
|
|
|
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
| Hector Zenil (hector.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008, Table of n, a(n) for n = 0..30
Author?, The experimental AIT project
Author?, 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: A203052 A054407 A058466 * A201003 A134374 A159423
Adjacent sequences: A141472 A141473 A141474 * A141476 A141477 A141478
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Hector Zenil (hector.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008
|
| |
|
|
