Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-26T00:38:01.500Z Has data issue: false hasContentIssue false
  • English
  • Français

Degrees in Which the Recursive Sets are Uniformly Recursive

Published online by Cambridge University Press:  20 November 2018

Carl G. Jockusch Jr.
Carl G. Jockusch Jr.*
Affiliation:
University of Illinois, Urbana, Illinois
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

One of the most fundamental and characteristic features of recursion theory is the fact that the recursive sets are not uniformly recursive. In this paper we consider the degrees a such that the recursive sets are uniformly of degree ≦a and characterize them by the condition a’ ≦ 0". A number of related results will be proved, and one of these will be combined with a theorem of Yates to show that there is no r.e. degree a < 0’ such that the r.e. sets of degree ≦a are uniformly of degree ≦a. This result and a generalization will be used to study the relationship between Turing and many-one reducibility on the r.e. sets.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 24 , Issue 6 , December 1972 , pp. 1092 - 1099
Copyright
Copyright © Canadian Mathematical Society 1972

References

1. Cooper, S. B., Minimal degrees and the jump operator (to appear).Google Scholar
2. Friedberg, R. M., A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160.Google Scholar
3. Jockusch, C. G., Jr., Relationships between reducibilities, Trans. Amer. Math. Soc. 142 (1969), 229–237.Google Scholar
4. Jockusch, C. G., Jr and Soare, R. I., II10 Classes and degrees of theories (to appear in Trans. Amer. Math. Soc).Google Scholar
5. Jockusch, C. G., Jr and Soare, R. I., Degrees of members of nV classes, Pacific J. Math. 40 (1972), 605–616.Google Scholar
6. Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295–310.Google Scholar
7. Rogers, H., Jr., Theory of recursive functions and effective computability (McGraw-Hill, New York, 1967).Google Scholar
8. Sacks, G. E., Degrees of unsolvability, Ann. of Math. Studies, No. 55 (Princeton Univ. Press, Princeton, N.J., 1963).Google Scholar
9. Scott, D. and Tennenbaum, S., On the degrees of complete extensions of arithmetic, Notices Amer. Math. Soc. 7 (1960), 242–243.Google Scholar
10. Shoenfield, J. R., On degrees of unsolvability, Ann. of Math. 69 (1959), 644–653.Google Scholar
11. Yates, C. E. M., Degrees of index sets II, Trans. Amer. Math. Soc. 135 (1969), 249–266.Google Scholar