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 ‘a priori 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 two-person memory-allocation game between 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 give a short address. We also present some related results.

Authors

• Péter Gács

Keywords

No keywords are indexed for this paper.