Relation Between the Complexity and the Probability of Large Numbers.

Abstract

H(x), the negative logarithm of the apriori probability M(x), i s 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) < or = alpha(n) < or = s(n) + H(s(n)). We show that the second estimate is in some sense sharp.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1979
Accession Number
ADA083192

Entities

People

  • Peter Gacs

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Automata
  • Computer Science
  • Computers
  • Inequalities
  • Information Theory
  • Probability
  • Rational Functions
  • Recursive Functions
  • Schools
  • Sequences
  • Theorems
  • Universities

Readers

  • Approximation Theory.
  • Ballistic Missile Meteorology