login
This site is supported by donations to The OEIS Foundation.
Logo

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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; text; 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

Table of n, a(n) for n=0..10.

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: A223264 A223196 A159665 * A159441 A011787 A006070

Adjacent sequences:  A164275 A164276 A164277 * A164279 A164280 A164281

KEYWORD

easy,nonn,uned

AUTHOR

Jonathan Vos Post, Aug 11 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified May 23 16:56 EDT 2013. Contains 225610 sequences.