9 found
Sort by:
  1. George Barmpalias, Andrew E. M. Lewis & Keng Meng Ng (2010). The Importance of Π⁰₁ Classes in Effective Randomness. Journal of Symbolic Logic 75 (1):387-400.
    We prove a number of results in effective randomness, using methods in which $\Pi _{1}^{0}$ classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  2. George Barmpalias, Andrew E. M. Lewis & Mariya Soskova (2008). Randomness, Lowness and Degrees. Journal of Symbolic Logic 73 (2):559 - 577.
    We say that A ≤LR B if every B-random number is A-random. Intuitively this means that if oracle A can identify some patterns on some real γ. In other words. B is at least as good as A for this purpose. We study the structure of the LR degrees globally and locally (i.e., restricted to the computably enumberable degrees) and their relationship with the Turing degrees. Among other results we show that whenever α in not GL₂ the LR degree of (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  3. George Barmpalias, Andrew E. M. Lewis & Frank Stephan (2008). Classes, Degrees and Turing Degrees. Annals of Pure and Applied Logic 156 (1):21-38.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  4. George Barmpalias & Andrew E. M. Lewis (2006). The Degrees of Computably Enumerable Sets Are Not Dense. Annals of Pure and Applied Logic 141 (1-2):51-60.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  5. George Barmpalias & Andrew E. M. Lewis (2006). A C.E. Real That Cannot Be SW-Computed by Any Ω Number. Notre Dame Journal of Formal Logic 47 (2):197-209.
    The strong weak truth table (sw) reducibility was suggested by Downey, Hirschfeldt, and LaForte as a measure of relative randomness, alternative to the Solovay reducibility. It also occurs naturally in proofs in classical computability theory as well as in the recent work of Soare, Nabutovsky, and Weinberger on applications of computability to differential geometry. We study the sw-degrees of c.e. reals and construct a c.e. real which has no random c.e. real (i.e., Ω number) sw-above it.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. George Barmpalias & Andrew E. M. Lewis (2006). The Hypersimple-Free C.E. WTT Degrees Are Dense in the C.E. WTT Degrees. Notre Dame Journal of Formal Logic 47 (3):361-370.
    We show that in the c.e. weak truth table degrees if b < c then there is an a which contains no hypersimple set and b < a < c. We also show that for every w < c in the c.e. wtt degrees such that w is hypersimple, there is a hypersimple a such that w < a < c. On the other hand, we know that there are intervals which contain no hypersimple set.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  7. S. Barry Cooper, Andrew E. M. Lewis & Yue Yang (2005). Properly Σ2 Minimal Degrees and 0″ Complementation. Mathematical Logic Quarterly 51 (3):274-276.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  8. S. B. Cooper & Andrew E. M. Lewis (2005). Properly Sigma~2 Minimal Degrees and 0" Complementation. Mathematical Logic Quarterly 51 (3):274.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  9. Andrew E. M. Lewis (2005). The Minimal Complementation Property Above 0′. Mathematical Logic Quarterly 51 (5):470-492.
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation