take e.g. all possible bitstrings of length n=10,000. there are 2^10,000 of them. imagine that for each of those strings we knew the length of the shortest program that could produce the string. what would the distribution of the lengths of those programs look like?

  • 6
    $\begingroup$ How precise of an answer do you want? By a counting argument, only a $2^{-c}$ fraction of strings can possibly have a KC of less than $2^{10000-c}$, or in other words, all but $o(n)$ strings have complexity $n-o(n)$. $\endgroup$
    – usul
    Sep 24, 2017 at 9:40
  • $\begingroup$ PS. That should say all but $2^{o(n)}$ strings have complexity $n - o(n)$, or equivalently all but an $o(1)$ fraction of strings. $\endgroup$
    – usul
    Sep 29, 2017 at 19:29
  • $\begingroup$ Thank you, that is interesting. I suppose I'm interested in as precise an answer as is currently possible, but would take anything more than I know right now which is near zero :) The counting argument is probably obvious to most, but I would be interested in hearing it described. $\endgroup$
    – RoboTeddy
    Sep 30, 2017 at 20:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.