Relation between the complexity and the probability of large numbers

[摘要] 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.

[学科分类] 计算机科学（综合）