Recursively enumerable reals and Chaitin Omega numbers

A real alpha is called recursively enumerable if it is the limit of a recur sive, increasing, converging sequence of rationals. Following Solovay (unpu blished manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, May 1975, 215 pp.) and Chaitin (IBM J. Res. Develop. 21 (1977) 3 50-359, 496.) we say that an r.e. real alpha dominates an r.e. real beta if from a good approximation of alpha from below one can compute a good appro ximation of beta from below. We shall study this relation and characterize it in terms of relations between r.e. sets. Solovay's (unpublished manuscri pt, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, May 1 975, 215 pp.) SZ-like numbers are the maximal r.e. real numbers with respec t to this order. They are random r.e. real numbers. The halting probability of a universal self-delimiting Turing machine (Chaitin's Omega number (J. Assoc. Comput. Mach. 22 (1975) 329-340)) is also a random r.e. real. Solova y showed that any Chaitin Omega number is Omega -like. In this paper we sho w that the converse implication is true as well: any Omega -like real in th e unit interval is the halting probability of a universal self-delimiting T uring machine. (C) 2001 Elsevier Science B.V. All rights reserved.