Switch to: Citations

Add references

You must login to add references.
  1. Computability and recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
    We consider the informal concept of "computability" or "effective calculability" and two of the formalisms commonly used to define it, "(Turing) computability" and "(general) recursiveness". We consider their origin, exact technical definition, concepts, history, general English meanings, how they became fixed in their present roles, how they were first and are now used, their impact on nonspecialists, how their use will affect the future content of the subject of computability theory, and its connection to other related areas. After a careful (...)
    Download  
     
    Export citation  
     
    Bookmark   51 citations  
  • Complementation in the Turing degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
    Posner [6] has shown, by a nonuniform proof, that every ▵ 0 2 degree has a complement below 0'. We show that a 1-generic complement for each ▵ 0 2 set of degree between 0 and 0' can be found uniformly. Moreover, the methods just as easily can be used to produce a complement whose jump has the degree of any real recursively enumerable in and above $\varnothing'$ . In the second half of the paper, we show that the complementation (...)
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • A Refinement of Low n and High n for the R.E. Degrees.Jeanleah Mohrherr - 1986 - Mathematical Logic Quarterly 32 (1‐5):5-12.
    Download  
     
    Export citation  
     
    Bookmark   9 citations  
  • A Refinement of Low n_ and High _n for the R.E. Degrees.Jeanleah Mohrherr - 1986 - Mathematical Logic Quarterly 32 (1-5):5-12.
    Download  
     
    Export citation  
     
    Bookmark   10 citations  
  • Recursively enumerable generic sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
    We show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0'. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice E of recursively enumerable sets with inclusion. (...)
    Download  
     
    Export citation  
     
    Bookmark   15 citations  
  • A 1-generic degree which Bounds a minimal degree.Masahiro Kumabe - 1990 - Journal of Symbolic Logic 55 (2):733-743.
    Download  
     
    Export citation  
     
    Bookmark   6 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.
    Download  
     
    Export citation  
     
    Bookmark   9 citations  
  • The strong anticupping property for recursively enumerable degrees.S. B. Cooper - 1989 - Journal of Symbolic Logic 54 (2):527-539.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Minimal degrees recursive in 1-generic degrees.C. T. Chong & R. G. Downey - 1990 - Annals of Pure and Applied Logic 48 (3):215-225.
    Download  
     
    Export citation  
     
    Bookmark   9 citations