Recursively enumerable reals and chaitin Ω numbers

Abstract

A real α is called recursively enumerable if it is the limit of a recursive, increasing, converging sequence of rationals. Following Solovay [23] and Chaitin [10] we say that an r.e. real α dominates an r.e. real β if from a good approximation of a 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 [23] Ω-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, [9]) 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.

The first and third authors were partially supported by AURC A18/XXXXX/ 62090/F3414056, 1996. The second author was supported by the DFG Research Grant No. HE 2489/2-1, and the fourth author was supported by an AURC Post-Doctoral Fellowship.