|
Search: id:A141475
|
|
|
| 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. |
|
+0
1
|
|
| 36, 10000, 7529536, 11019960576, 26559922791424, 95428956661682176, 478296900000000000000, 3189059870763703892770816, 27296360116495644500385071104, 291733167875766667063796853374976
(list; graph; listen)
|
|
|
OFFSET
|
0,1
|
|
|
COMMENT
|
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: A013739 A054407 A058466 this_sequence A134374 A159423 A001308
Adjacent sequences: A141472 A141473 A141474 this_sequence A141476 A141477 A141478
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Hector Zenil (hector.zenil-chavez(AT)malix.univ-paris1.fr), Aug 09 2008
|
|
|
Search completed in 0.002 seconds
|
