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  
  • Classes of Recursively Enumerable Sets and Degrees of Unsolvability.Donald A. Martin - 1966 - Mathematical Logic Quarterly 12 (1):295-310.
    Download  
     
    Export citation  
     
    Bookmark   88 citations  
  • Correction to “a cohesive set which is not high”.Carl Jockusch & Frank Stephan - 1997 - Mathematical Logic Quarterly 43 (4):569-569.
    Download  
     
    Export citation  
     
    Bookmark   9 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 (...)
    Download  
     
    Export citation  
     
    Bookmark   27 citations  
  • On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
    We show that, for every partition F of the pairs of natural numbers and for every set C, if C is not recursive in F then there is an infinite set H, such that H is homogeneous for F and C is not recursive in H. We conclude that the formal statement of Ramsey's Theorem for Pairs is not strong enough to prove , the comprehension scheme for arithmetical formulas, within the base theory , the comprehension scheme for recursive formulas. (...)
    Download  
     
    Export citation  
     
    Bookmark   49 citations