Affiliations: Ruprecht-Karls-Universität Heidelberg, Institut für Informatik, Heidelberg, Germany. merkle@math.uni-heidelberg.de, http://math.uni-heidelberg.de/logic/merkle/merkle.html | Pennsylvania State University, Department of Computer Science and Engineering, State College, Pennsylvania, USA. teutsch@cse.psu.edu, 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.
