Randomness and Recursive Enumerability


One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test



    Upload a copy of this work     Papers currently archived: 94,439

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

Similar books and articles

The Kolmogorov complexity of random reals.Liang Yu, Decheng Ding & Rodney Downey - 2004 - Annals of Pure and Applied Logic 129 (1-3):163-180.
Recursive events in random sequences.George Davie - 2001 - Archive for Mathematical Logic 40 (8):629-638.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
Degrees of d. c. e. reals.Rod Downey, Guohua Wu & Xizhong Zheng - 2004 - Mathematical Logic Quarterly 50 (4-5):345-350.
An invariance notion in recursion theory.Robert E. Byerly - 1982 - Journal of Symbolic Logic 47 (1):48-66.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
Relative Randomness and Cardinality.George Barmpalias - 2010 - Notre Dame Journal of Formal Logic 51 (2):195-205.
A non-splitting theorem for d.r.e. sets.Xiaoding Yi - 1996 - Annals of Pure and Applied Logic 82 (1):17-96.


Added to PP

106 (#165,040)

6 months
6 (#735,879)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references