A characterization of c.e. random reals

摘要

A real α is computably enumerable if it is the limit of a computable, increasing, converging sequence of rationals. A real α 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 Syrup. 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 3. Watson Research Center, Yorktown Heights, New York, May 1975, 215 pp.), of the following theorem: a real is C. e. and random if and only f it is a Chaitin Ω real, i.e., the halting probability of some universal self-delimiting Turing machine.