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.
  • Algorithmic Randomness and Measures of Complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • 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   3 citations  
  • 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   8 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   3 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 (5 more)  
     
    Export citation  
     
    Bookmark   1 citation