Report Number: CS-TR-79-765
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.