Switch to: Citations

Add references

You must login to add references.
  1. Relativized Schnorr tests with universal behavior.Nicholas Rupprecht - 2010 - Archive for Mathematical Logic 49 (5):555-570.
    A Schnorr test relative to some oracle A may informally be called “universal” if it covers all Schnorr tests. Since no true universal Schnorr test exists, such an A cannot be computable. We prove that the sets with this property are exactly those with high Turing degree. Our method is closely related to the proof of Terwijn and Zambella’s characterization of the oracles which are low for Schnorr tests. We also consider the oracles which compute relativized Schnorr tests with the (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • On the filter of computably enumerable supersets of an r-maximal set.Steffen Lempp, André Nies & D. Reed Solomon - 2001 - Archive for Mathematical Logic 40 (6):415-423.
    We study the filter ℒ*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ*(A) is still Σ0 3-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ*(A).
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Low upper bounds of ideals.Antonín Kučera & Theodore A. Slaman - 2009 - Journal of Symbolic Logic 74 (2):517-534.
    We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ T-degrees for which there is a low T-upper bound.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • A cohesive set which is not high.Carl Jockusch & Frank Stephan - 1993 - Mathematical Logic Quarterly 39 (1):515-530.
    We study the degrees of unsolvability of sets which are cohesive . We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets (...)
    Direct download  
     
    Export citation  
     
    Bookmark   27 citations  
  • The degrees below a 1-generic degree $.Christine Ann Haught - 1986 - Journal of Symbolic Logic 51 (3):770 - 777.
    It is shown that the nonrecursive predecessors of a 1-generic degree $ are all 1-generic. As a corollary, it is shown that the 1-generic degrees are not densely ordered.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   9 citations