The Wikipedia definition of Kolmogorov-random defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string.

Aren't nearly1 all strings shorter than a certain length2 going to be Kolmogorov-random?

  1. If a random Turing machine is chosen, then programs that output short strings will almost always be longer than the strings. If the programming language used for measurement is optimized for outputting a short string, then only the complexity of a subset of short strings can be made lower than their length. For example, if a Turing complete language defines $0$ as an operation that outputs 0 and halts, the program for outputting 1 and halting is forced to be longer than the length of its output.

  2. The exact length below which this occurs will depend on the programming language chosen. The length is 41 bits using 5 state, 2 symbol Turing machines.

  • $\begingroup$ Depends on what you mean by "nonsensical". $\endgroup$ – Ray May 12 '17 at 7:52
  • $\begingroup$ I mean that, while the definition is self-consistent, the small numbers that are Kolmogorov-random don't resemble any other reasonable definition of random. $\endgroup$ – LeBleu May 12 '17 at 16:45
  • $\begingroup$ Ah, but what is a "reasonable definition" of randomnes? There are many definitions, but kolmogorov randomness, to me, is the most useful. What do the other definitions say about the randomness of small numbers? $\endgroup$ – Ray May 13 '17 at 15:59
  • $\begingroup$ Something like "no betting strategy can make money betting on a random sequence". A sequence of all 0 is easy to bet on, yet sequences shorter than ~33 bits are all Kolmgorov-random. $\endgroup$ – LeBleu May 17 '17 at 17:46
  • $\begingroup$ Without even using alternative definitions of randomness, it seems problematic that all short substrings of non-Kolmogorov-random strings are Kolmogorov-random. $\endgroup$ – LeBleu May 17 '17 at 17:54

Is Kolmogorov-random nonsensical for small numbers?

Although one could pick a specific description language to make Kolmogorov complexity into
a function from ​ {0,1}* ​ to ​ {0,1,2,3,...} , ​ most people don't pick as described ​ ( 0 , 1 , 2 , 3 ) ,
so basically:

Kolmogorov complexity is only defined up to an additive O(1), so one
needs an infinite set of strings to make sense of Kolmogorov randomness.
In particular, yes, Kolmogorov-randomness is nonsensical for small numbers.


I think that K-complexity, at least as an indication of randomness, becomes much more meaningful above the "water line" of string size N where you start having K(x) < N/10, although I'm not sure where that water line should sit. You might look into a concept called algorithmic specified complexity, which is a kind of randomness deficiency like computational depth. For an appropriate probability measure, a short but "random" K-complexity might still be a meaningful idea but not necessarily as randomness per se.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.