1.  2
    Exact Pairs for the Ideal of the K-Trivial Sequences in the Turing Degrees.George Barmpalias & Rod G. Downey - 2014 - Journal of Symbolic Logic 79 (3):676-692.
    TheK-trivial sets form an ideal in the Turing degrees, which is generated by its computably enumerable members and has an exact pair below the degree of the halting problem. The question of whether it has an exact pair in the c.e. degrees was first raised in [22, Question 4.2] and later in [25, Problem 5.5.8].We give a negative answer to this question. In fact, we show the following stronger statement in the c.e. degrees. There exists aK-trivial degreedsuch that for all (...)
    Direct download (3 more)  
    Export citation  
    Bookmark   2 citations  
  2.  1
    On Supersets of Non-Low Sets.Klaus Ambos-Spies, Rod G. Downey & Martin Monath - 2021 - Journal of Symbolic Logic 86 (3):1282-1292.
    We solve a longstanding question of Soare by showing that if ${\mathbf d}$ is a non-low $_2$ computably enumerable degree then ${\mathbf d}$ contains a c.e. set with no r-maximal c.e. superset.
    Direct download (2 more)  
    Export citation  
  3.  27
    Index Sets and Parametric Reductions.Rod G. Downey & Michael R. Fellows - 2001 - Archive for Mathematical Logic 40 (5):329-348.
    We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated with a computable set A, {e : W e ≤ q u A} for q∈ {m, T} are Σ4 0 complete. We also show hat FPT(≤ q n ), that is {e : W e computable and ≡ q n ?}, is Σ4 (...)
    No categories
    Direct download (5 more)  
    Export citation