Constant Compression and Random Weights

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.