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 (...)
    Direct download (9 more)  
     
    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.
    Direct download  
     
    Export citation  
     
    Bookmark   87 citations  
  • Correction to “a cohesive set which is not high”.Carl Jockusch & Frank Stephan - 1997 - Mathematical Logic Quarterly 43 (4):569-569.
  • 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  
  • 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. (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   48 citations