|
Search: id:A164278
|
|
|
| A164278 |
|
Total number of machines with n states in "On the Running Time of the Shortest Programs" |
|
+0
1
|
|
| 0, 48, 28560, 47045880, 152587890624, 819628286980800, 6582952005840035280, 73885357344138503765448, 1104427674243920646305299200, 21209401372879911350250244140624, 508858109619679129936596364708525200
(list; graph; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
The Kolmogorov complexity of the word w is equal to the length of the shortest concatenation of program Z and its input x with which the word w is computed by the universal Turing machine U. The question introduced in this paper is the following: How long do the shortest programs run for?
|
|
LINKS
|
Norbert Batfai, On the Running Time of the Shortest Programs, Aug 10, 2009.
|
|
FORMULA
|
a(n) = ((6*n + 1)^(2*n)) - 1.
|
|
CROSSREFS
|
Cf. A028444.
Sequence in context: A123478 A159425 A159665 this_sequence A159441 A011787 A006070
Adjacent sequences: A164275 A164276 A164277 this_sequence A164279 A164280 A164281
|
|
KEYWORD
|
easy,nonn,uned
|
|
AUTHOR
|
Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 11 2009
|
|
|
Search completed in 0.002 seconds
|
