A characterization of c.e. random reals
A real alpha is computably enumerable if it is the limit of a computable, increasing, converging sequence of rationals. A real a is random if its binary expansion is a random sequence. Our aim is to offer a self-contained proof, based on the papers (Calude et al.. in: M. Morvan, C. Meinel, D. Krob (Eds.), Proc. 15th Symp. on Theoretical Aspects of Computer Science, Paris, Springer, Berlin, 1998, pp. 596-606; Chaitin, J. Assoc. Comput. Mach. 22 (1975) 329; Slaman, manuscript, 14 December 1998, 2 pp., Solovay, unpublished manuscript, IBM Thomas J. Watson Research Center. Yorktown Heights, New York, May 1975, 215 pp,), of the following theorem: a real is ce. and random if and only, if it is a Chaitin Omega real, i.e., the halting probability of some universal self-delimiting Turing machine. (C) 2002 Elsevier Science B.V. All rights reserved.
random real chaitin omega real c.e. real