Institution: Stanford University, Department of Computer Science

Title: Relation between the complexity and the probability of large numbers

Author: Gacs, Peter

Date: September 1979

Abstract: H(x), the negative logarithm of the apriori probability M(x), is Levin's variant of Kolmogorov's complexity of a natural number x. Let $\alpha (n)$ be the minimum complexity of a number larger than n, s(n) the logarithm of the apriori probability of obtaining a number larger than n . It was known that $s(n) \leq\ \alpha (n) \leq\ s(n) + H(\lceil s(n) \rceil )$. We show that the second estimate is in some sense sharp.

http://i.stanford.edu/pub/cstr/reports/cs/tr/79/765/CS-TR-79-765.pdf