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$?

Improve this question
$\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
    Commented Nov 24, 2011 at 12:24

2 Answers 2

Reset to default
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).

Improve this answer
$\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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .