Switch to: Citations

Add references

You must login to add references.
  1. Theory of recursive functions and effective computability.Hartley Rogers - 1987 - Cambridge: MIT Press.
    Download  
     
    Export citation  
     
    Bookmark   480 citations  
  • (2 other versions)Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
    Download  
     
    Export citation  
     
    Bookmark   43 citations  
  • (2 other versions)Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.
    Download  
     
    Export citation  
     
    Bookmark   41 citations  
  • Partial degrees and the density problem. Part 2: The enumeration degrees of the ∑2 sets are dense.S. B. Cooper - 1984 - Journal of Symbolic Logic 49 (2):503 - 513.
    Download  
     
    Export citation  
     
    Bookmark   21 citations  
  • (1 other version)Enumeration reducibility and partial degrees.John Case - 1971 - Annals of Mathematical Logic 2 (4):419-439.
    Download  
     
    Export citation  
     
    Bookmark   20 citations  
  • Then-rea enumeration degrees are dense.Alistair H. Lachlan & Richard A. Shore - 1992 - Archive for Mathematical Logic 31 (4):277-285.
    Download  
     
    Export citation  
     
    Bookmark   20 citations  
  • Jumps of quasi-minimal enumeration degrees.Kevin McEvoy - 1985 - Journal of Symbolic Logic 50 (3):839-848.
    Download  
     
    Export citation  
     
    Bookmark   18 citations  
  • On minimal pairs of enumeration degrees.Kevin McEvoy & S. Barry Cooper - 1985 - Journal of Symbolic Logic 50 (4):983-1001.
    Download  
     
    Export citation  
     
    Bookmark   15 citations  
  • Computational complexity, speedable and levelable sets.Robert I. Soare - 1977 - Journal of Symbolic Logic 42 (4):545-563.
    Download  
     
    Export citation  
     
    Bookmark   15 citations  
  • (1 other version)Enumeration Reducibility Using Bounded Information: Counting Minimal Covers.S. Barry Cooper - 1987 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 33 (6):537-560.
    Download  
     
    Export citation  
     
    Bookmark   13 citations  
  • (1 other version)Enumeration Reducibility Using Bounded Information: Counting Minimal Covers.S. Barry Cooper - 1987 - Mathematical Logic Quarterly 33 (6):537-560.
    Download  
     
    Export citation  
     
    Bookmark   13 citations  
  • Computably enumerable sets and quasi-reducibility.R. Downey, G. LaForte & A. Nies - 1998 - Annals of Pure and Applied Logic 95 (1-3):1-35.
    We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.
    Download  
     
    Export citation  
     
    Bookmark   13 citations  
  • Partial degrees and the density problem.S. B. Cooper - 1982 - Journal of Symbolic Logic 47 (4):854-859.
    Download  
     
    Export citation  
     
    Bookmark   11 citations  
  • On subcreative sets and S-reducibility.John T. Gill & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669-677.
    Subcreative sets, introduced by Blum, are known to coincide with the effectively speedable sets. Subcreative sets are shown to be the complete sets with respect to S-reducibility, a special case of Turing reducibility. Thus a set is effectively speedable exactly when it contains the solution to the halting problem in an easily decodable form. Several characterizations of subcreative sets are given, including the solution of an open problem of Blum, and are used to locate the subcreative sets with respect to (...)
    Download  
     
    Export citation  
     
    Bookmark   11 citations  
  • On Subcreative Sets and S-Reducibility.John T. Gill Iii & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669 - 677.
    Subcreative sets, introduced by Blum, are known to coincide with the effectively speedable sets. Subcreative sets are shown to be the complete sets with respect to S-reducibility, a special case of Turing reducibility. Thus a set is effectively speedable exactly when it contains the solution to the halting problem in an easily decodable form. Several characterizations of subcreative sets are given, including the solution of an open problem of Blum, and are used to locate the subcreative sets with respect to (...)
    Download  
     
    Export citation  
     
    Bookmark   11 citations  
  • Embedding the diamond in the σ2 enumeration degree.Seema Ahmad - 1991 - Journal of Symbolic Logic 56 (1):195 - 212.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • On subcreative sets and s-reducibility.I. I. I. Gill & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669-677.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • On the Degrees Less than 0'.Gerald E. Sacks - 1964 - Journal of Symbolic Logic 29 (1):60-60.
    Download  
     
    Export citation  
     
    Bookmark   18 citations  
  • On restricted forms of enumeration reducibility.Phil Watson - 1990 - Annals of Pure and Applied Logic 49 (1):75-96.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Bounding and Nonbounding Minimal Pairs in the Enumeration Degrees.S. Barry Cooper, Angsheng Li, Andrea Sorbi & Yue Yang - 2005 - Journal of Symbolic Logic 70 (3):741 - 766.
    We show that every nonzero $\Delta _{2}^{0}$ e-degree bounds a minimal pair. On the other hand, there exist $\Sigma _{2}^{0}$ e-degrees which bound no minimal pair.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Addendum to “computably enumerable sets and quasi-reducibility”.R. Downey, G. LaForte & A. Nies - 1999 - Annals of Pure and Applied Logic 98 (1-3):295.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Noncappable enumeration degrees below 0'e. [REVIEW]S. Cooper & Andrea Sorbi - 1996 - Journal of Symbolic Logic 61 (4):1347 - 1363.
    We prove that there exists a noncappable enumeration degree strictly below 0' e.
    Download  
     
    Export citation  
     
    Bookmark   3 citations