Geodesic
Degrees in Which the Recursive Sets are Uniformly Recursive
Canadian journal of mathematics, Tome 24 (1972) no. 6, pp. 1092-1099

Voir la notice de l'article provenant de la source Cambridge University Press

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. 
Jr., Carl G. Jockusch. Degrees in Which the Recursive Sets are Uniformly Recursive. Canadian journal of mathematics, Tome 24 (1972) no. 6, pp. 1092-1099. doi: 10.4153/CJM-1972-113-9
@article{10_4153_CJM_1972_113_9,
     author = {Jr., Carl G. Jockusch},
     title = {Degrees in {Which} the {Recursive} {Sets} are {Uniformly} {Recursive}},
     journal = {Canadian journal of mathematics},
     pages = {1092--1099},
     year = {1972},
     volume = {24},
     number = {6},
     doi = {10.4153/CJM-1972-113-9},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1972-113-9/}
}
TY  - JOUR
AU  - Jr., Carl G. Jockusch
TI  - Degrees in Which the Recursive Sets are Uniformly Recursive
JO  - Canadian journal of mathematics
PY  - 1972
SP  - 1092
EP  - 1099
VL  - 24
IS  - 6
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1972-113-9/
DO  - 10.4153/CJM-1972-113-9
ID  - 10_4153_CJM_1972_113_9
ER  - 
%0 Journal Article
%A Jr., Carl G. Jockusch
%T Degrees in Which the Recursive Sets are Uniformly Recursive
%J Canadian journal of mathematics
%D 1972
%P 1092-1099
%V 24
%N 6
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1972-113-9/
%R 10.4153/CJM-1972-113-9
%F 10_4153_CJM_1972_113_9

[1] 1. Cooper, S. B., Minimal degrees and the jump operator (to appear). Google Scholar

[2] 2. Friedberg, R. M., A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160. Google Scholar

[3] 3. Jockusch, C. G., Jr., Relationships between reducibilities, Trans. Amer. Math. Soc. 142 (1969), 229–237. Google Scholar

[4] 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] 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] 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] 7. Rogers, H., Jr., Theory of recursive functions and effective computability (McGraw-Hill, New York, 1967). Google Scholar

[8] 8. Sacks, G. E., Degrees of unsolvability, Ann. of Math. Studies, No. 55 (Princeton Univ. Press, Princeton, N.J., 1963). Google Scholar

[9] 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] 10. Shoenfield, J. R., On degrees of unsolvability, Ann. of Math. 69 (1959), 644–653. Google Scholar

[11] 11. Yates, C. E. M., Degrees of index sets II, Trans. Amer. Math. Soc. 135 (1969), 249–266. Google Scholar

Cité par Sources :