Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

Increasing the gap between descriptional complexity and algorithmic probability


Author: Adam R. Day
Journal: Trans. Amer. Math. Soc. 363 (2011), 5577-5604
MSC (2000): Primary 68Q30
DOI: https://doi.org/10.1090/S0002-9947-2011-05315-8
Published electronically: May 5, 2011
MathSciNet review: 2813425
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The coding theorem is a fundamental result of algorithmic information theory. A well-known theorem of Gács shows that the analog of the coding theorem fails for continuous sample spaces. This means that descriptional monotonic complexity does not coincide within an additive constant with the negative logarithm of algorithmic probability. Gács's proof provided a lower bound on the difference between these values. He showed that for infinitely many finite binary strings, this difference was greater than a version of the inverse Ackermann function applied to string length. This paper establishes that this lower bound can be substantially improved. The inverse Ackermann function can be replaced with a function $ O(\operatorname{log}(\operatorname{log}(x)))$. This shows that in continuous sample spaces, descriptional monotonic complexity and algorithmic probability are very different. While this proof builds on the original work by Gács, it does have a number of new features; in particular, the algorithm at the heart of the proof works on sets of strings as opposed to individual strings.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 68Q30

Retrieve articles in all journals with MSC (2000): 68Q30


Additional Information

Adam R. Day
Affiliation: School of Mathematics, Statistics and Operations Research, Victoria University of Wellington, Wellington 6140, New Zealand
Email: adam.day@msor.vuw.ac.nz

DOI: https://doi.org/10.1090/S0002-9947-2011-05315-8
Received by editor(s): October 21, 2009
Received by editor(s) in revised form: February 10, 2010
Published electronically: May 5, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.