Recursively enumerable reals and Chaitin Ω numbers

AbstractA real α is called recursively enumerable if it is the limit of a recursive, increasing, converging sequence of rationals. Following Solovay (unpublished manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, May 1975, 215 pp.) and Chaitin (IBM J. Res. Develop. 21 (1977) 350–359, 496.) we say that an r.e. real α dominates an r.e. real β if from a good approximation of α from below one can compute a good approximation of β from below. We shall study this relation and characterize it in terms of relations between r.e. sets. Solovay's (unpublished manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, May 1975, 215 pp.) Ω-like numbers are the maximal r.e. real numbers with respect to this order. They are random r.e. real numbers. The halting probability of a universal self-delimiting Turing machine (Chaitin's Ω number (J. Assoc. Comput. Mach. 22 (1975) 329–340)) is also a random r.e. real. Solovay showed that any Chaitin Ω number is Ω-like. In this paper we show that the converse implication is true as well: any Ω-like real in the unit interval is the halting probability of a universal self-delimiting Turing machine