A new representation of Chaitin Ωnumber based on compressible strings
arXiv:1004.0658 · doi:10.1007/s11047-011-9272-y
Abstract
In 1975 Chaitin introduced his Ωnumber as a concrete example of random real. The real Ωis defined based on the set of all halting inputs for an optimal prefix-free machine U, which is a universal decoding algorithm used to define the notion of program-size complexity. Chaitin showed Ωto be random by discovering the property that the first n bits of the base-two expansion of Ωsolve the halting problem of U for all binary inputs of length at most n. In this paper, we introduce a new representation Θof Chaitin Ωnumber. The real Θis defined based on the set of all compressible strings. We investigate the properties of Θand show that Θis random. In addition, we generalize Θto two directions Θ(T) and \barΘ(T) with a real T>0. We then study their properties. In particular, we show that the computability of the real Θ(T) gives a sufficient condition for a real T in (0,1) to be a fixed point on partial randomness, i.e., to satisfy the condition that the compression rate of T equals to T.
12 pages, no figures, to appear in the Proceedings of the 9th International Conference on Unconventional Computation (UC 2010), The University of Tokyo, Japan, June 21-25, 2010