BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-79-765
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Relation between the complexity and the probability of large
               numbers
        TYPE:: Technical Report
      AUTHOR:: Gacs, Peter
        DATE:: September 1979
       PAGES:: 9
    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.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-79-765