A real alpha is called recusively 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 alpha dominates an r.e. real beta if from a good approximation of alpha from below one can compute a good approximatio of beta from below. We shall study this relation and characterize it in terms of rellations between r.e. sets. Solovary's [23] omega-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 maching(Chaitin's omega number, [9]) is also a random r.e. real. Solovay showed that any Chaitin omega number is omega-like. In this paper we show that the converse implication is ture as well: any omega-like real in the unit interval is the halting porbability of a universal self-delimiting Turing machine.
展开▼
