Switch to: References

Add citations

You must login to add citations.
  1. Calibrating Randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
    We report on some recent work centered on attempts to understand when one set is more random than another. We look at various methods of calibration by initial segment complexity, such as those introduced by Solovay [125], Downey, Hirschfeldt, and Nies [39], Downey, Hirschfeldt, and LaForte [36], and Downey [31]; as well as other methods such as lowness notions of Kučera and Terwijn [71], Terwijn and Zambella [133], Nies [101, 100], and Downey, Griffiths, and Reid [34]; higher level randomness notions (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   25 citations  
  • Maximal Pairs of C.E. Reals in the Computably Lipschitz Degrees.Yun Fan & Liang Yu - 2011 - Annals of Pure and Applied Logic 162 (5):357-366.
    Computably Lipschitz reducibility , was suggested as a measure of relative randomness. We say α≤clβ if α is Turing reducible to β with oracle use on x bounded by x+c. In this paper, we prove that for any non-computable real, there exists a c.e. real so that no c.e. real can cl-compute both of them. So every non-computable c.e. real is the half of a cl-maximal pair of c.e. reals.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Algorithmic Randomness and Measures of Complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
  • Randomness and the Linear Degrees of Computability.Andrew Em Lewis & George Barmpalias - 2007 - Annals of Pure and Applied Logic 145 (3):252-257.
    We show that there exists a real α such that, for all reals β, if α is linear reducible to β then β≤Tα. In fact, every random real satisfies this quasi-maximality property. As a corollary we may conclude that there exists no ℓ-complete Δ2 real. Upon realizing that quasi-maximality does not characterize the random reals–there exist reals which are not random but which are of quasi-maximal ℓ-degree–it is then natural to ask whether maximality could provide such a characterization. Such hopes, (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Algorithmic Randomness and Measures of Complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • The ibT Degrees of Computably Enumerable Sets Are Not Dense.George Barmpalias & Andrew E. M. Lewis - 2006 - Annals of Pure and Applied Logic 141 (1-2):51-60.
    We show that the identity bounded Turing degrees of computably enumerable sets are not dense.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  • A Uniform Version of Non-Low2-Ness.Yun Fan - 2017 - Annals of Pure and Applied Logic 168 (3):738-748.
  • The Computable Lipschitz Degrees of Computably Enumerable Sets Are Not Dense.Adam R. Day - 2010 - Annals of Pure and Applied Logic 161 (12):1588-1602.
    The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations