7
$\begingroup$

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it such that the height at one point is constant, and let the bin-size go to 0, what can be said about the resulting distribution as $n\rightarrow\infty$? I'd expect it to approach something (very roughly) like the normal distribution.

Is there any nontrivial $L$ for which we know of a distribution that becomes apparent for large $n$?

$\endgroup$
1
  • 9
    $\begingroup$ Certainly not like the normal distribution. For instance, consider the Ackermann function. $A(n,n)$ takes constant+log n bits to express in any reasonable language, so the probability of a number at least as big as $A(n,n)$ will be much higher than $e^{- A(n,n)^2}$, which is a reasonable estimate for the normal distribution. Therefore, the distribution has longer tails than the normal distribution. My guess is that for most reasonable languages, a sufficient portion of the probability mass will go off to infinity, and that most facts about the distribution will not be computable. $\endgroup$
    – Will Sawin
    Nov 24, 2011 at 12:24

2 Answers 2

1
$\begingroup$

For any Turing-complete language, the class of descriptions of the form "$r$ is an integer with these digits:" followed by the digits, will have a constant positive probability. But this is exactly a uniform distribution on the first $2^n$ integers, which "goes to infinity". Hence, the limit object will not be a distribution (will not have total mass 1).

$\endgroup$
0
0
$\begingroup$

As Will says, this distribution will be different from any computable distribution in the sense that e.g. its distribution function will not be recursive. However, you can find any distribution in it in the sense that e.g. there is a c such that c times the distribution function of the normal distribution is a lower bound on this distribution function. You should check the Coding theorem and Levin's theorem about lower semi-computable semi-measures. I could find only this link: http://www.scholarpedia.org/article/Algorithmic_probability I can also recommend the Lovasz-(Gacs) book: Complexity of Algorithms.

$\endgroup$
2
  • 1
    $\begingroup$ any computable distribution in it. $\endgroup$
    – Will Sawin
    Nov 29, 2011 at 1:49
  • $\begingroup$ yes, you are right, I forgot to add that. $\endgroup$
    – domotorp
    Dec 1, 2011 at 11:44

Your Answer

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

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