Randomness, Relativization and Turing Degrees

Journal of Symbolic Logic 70 (2):515 - 535 (2005)
Abstract
We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to θ(n−1). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ |x| − c. The 'only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove some results on lowness. Among other things, we characterize the 2-random sets as those 1-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω sets coincide with the r.e. K-trivial ones. Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
 
Download options
PhilPapers Archive


Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 9,360
External links
  •   Try with proxy.
  •   Try with proxy.
  • Through your library Configure
    References found in this work BETA

    No references found.

    Citations of this work BETA
    Similar books and articles
    Rodney G. Downey & Evan J. Griffiths (2004). Schnorr Randomness. Journal of Symbolic Logic 69 (2):533 - 554.
    George Barmpalias (2010). Relative Randomness and Cardinality. Notre Dame Journal of Formal Logic 51 (2):195-205.
    Joseph Berkovitz, Roman Frigg & Fred Kronz (2006). The Ergodic Hierarchy, Randomness and Hamiltonian Chaos. Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 37 (4):661-691.
    Roman Frigg (2006). The Ergodic Hierarchy, Randomness and Hamiltonian Chaos. Studies in History and Philosophy of Science Part B 37 (4):661-691.
    Analytics

    Monthly downloads

    Added to index

    2010-08-24

    Total downloads

    3 ( #224,136 of 1,089,055 )

    Recent downloads (6 months)

    1 ( #69,801 of 1,089,055 )

    How can I increase my downloads?

    My notes
    Sign in to use this feature


    Discussion
    Start a new thread
    Order:
    There  are no threads in this forum
    Nothing in this forum yet.