Constant Compression and Random Weights

Article type: Research Article

Authors: Merkle, Wolfgang^; | Teutsch, Jason

Affiliations: Ruprecht-Karls-Universität Heidelberg, Institut für Informatik, Heidelberg, Germany. [email protected], http://math.uni-heidelberg.de/logic/merkle/merkle.html | Pennsylvania State University, Department of Computer Science and Engineering, State College, Pennsylvania, USA. [email protected], http://people.cs.uchicago.edu/~teutsch/

Note: [] A preliminary version [13] of this article has been presented to the 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012).

Abstract: A real number which equals the probability that a universal prefix-free machine halts when its input bits are determined by tosses of a fair coin is known as an Omega number. We present a new characterization of Omega numbers: a real in the unit interval is an Omega number if and only if it is the weight of the strings that some universal prefix-free machine compresses by at least a certain constant number of bits. For any universal prefix-free machine U, any a, and any sufficiently large b, the weight of the strings that U compresses by at least a bits but not by b bits is again an Omega number. In fact, we can characterize the Omega numbers by finite intervals of compressibility as well.

Keywords: Kolmogorov complexity, algorithmic randomness, compressible strings, Omega numbers

DOI: 10.3233/COM-12011

Journal: Computability, vol. 1, no. 2, pp. 153-169, 2012