Randomness and Recursive Enumerability
| Abstract | 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 | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,653 |
| External links |
  Try with proxy. |
| Through your library | Only published papers are available at libraries |
Similar books and articlesStephan Wehner (1999). On Recursive Enumerability with Finite Repetitions. Journal of Symbolic Logic 64 (3):927-945.
Rodney G. Downey & Evan J. Griffiths (2004). Schnorr Randomness. Journal of Symbolic Logic 69 (2):533 - 554.
Johanna N. Y. Franklin & Frank Stephan (2010). Van Lambalgen's Theorem and High Degrees. Notre Dame Journal of Formal Logic 52 (2):173-185.
André Nies, Frank Stephan & Sebastiaan A. Terwijn (2005). Randomness, Relativization and Turing Degrees. Journal of Symbolic Logic 70 (2):515 - 535.
Dev K. Roy (1993). Recursive Versus Recursively Enumerable Binary Relations. Studia Logica 52 (4):587 - 593.
A. M. Dawes (1982). Splitting Theorems for Speed-Up Related to Order of Enumeration. Journal of Symbolic Logic 47 (1):1-7.
Wolfgang Maass (1984). On the Orbits of Hyperhypersimple Sets. Journal of Symbolic Logic 49 (1):51-62.
Steffen Lempp & Theodore A. Slaman (1989). A Limit on Relative Genericity in the Recursively Enumerable Sets. Journal of Symbolic Logic 54 (2):376-395.
Iraj Kalantari & Allen Retzlaff (1979). Recursive Constructions in Topological Spaces. Journal of Symbolic Logic 44 (4):609-625.
Alexander Raichev (2005). Relative Randomness and Real Closed Fields. Journal of Symbolic Logic 70 (1):319 - 330.
Wolfgang Maass (1982). Recursively Enumerable Generic Sets. Journal of Symbolic Logic 47 (4):809-823.
Noam Greenberg (2005). The Role of True Finiteness in the Admissible Recursively Enumerable Degrees. Bulletin of Symbolic Logic 11 (3):398-410.
Theodore A. Slaman & John R. Steel (1989). Complementation in the Turing Degrees. Journal of Symbolic Logic 54 (1):160-176.
George Barmpalias (2010). Relative Randomness and Cardinality. Notre Dame Journal of Formal Logic 51 (2):195-205.
Joseph S. Miller (2004). Every 2-Random Real is Kolmogorov Random. Journal of Symbolic Logic 69 (3):907-913.
Analytics
Monthly downloads |
Added to index2011-11-21Total downloads8 ( #122,951 of 548,984 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
