On the Relation between Descriptional Complexity and Algorithmic Probability

Several results in Algorithmic Information Theory establish upper bounds on the difference between descriptional complexity and the logarithm of "apriori probability". It was conjectured that these two quantities coincide to within an additive constant. Here, we disprove this conjecture and show that the known overall upper bound on the difference is exact. The proof uses a memory-allocation game between two players called User and Server. User sends incremental requests of memory space for certain structured items, Server allocates this space in a write-once memory. For each item, some of the allocated space is required to be in one piece, in order to live a short address. We also present some related results.

Authors

• Péter Gács

Keywords

• Information theory
• Entropy
• Computer science
• Upper bound
• Probability distribution
• Approximation algorithms
• Inference algorithms
• Writing
• Binary sequences
• Encoding
• Additive Constant
• Real Numbers
• Proof Of Theorem
• Turing Machine
• Recursive Function