Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
9  
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. –  Will Sawin Nov 24 '11 at 12:24

2 Answers 2

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).

share|improve this answer

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.

share|improve this answer
1  
any computable distribution in it. –  Will Sawin Nov 29 '11 at 1:49
    
yes, you are right, I forgot to add that. –  domotorp Dec 1 '11 at 11:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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