|
| |
|
|
A164278
|
|
Total number of machines with n states in "On the Running Time of the Shortest Programs"
|
|
1
| |
|
|
0, 48, 28560, 47045880, 152587890624, 819628286980800, 6582952005840035280, 73885357344138503765448, 1104427674243920646305299200, 21209401372879911350250244140624, 508858109619679129936596364708525200
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| 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: A202928 A159425 A159665 * A159441 A011787 A006070
Adjacent sequences: A164275 A164276 A164277 * A164279 A164280 A164281
|
|
|
KEYWORD
| easy,nonn,uned
|
|
|
AUTHOR
| Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 11 2009
|
| |
|
|
