Geodesic
α-Speedable and non α-Speedable Sets
Canadian journal of mathematics, Tome 31 (1979) no. 2, pp. 282-299

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

α-Recursion theory was invented simultaneously by Kripke [15] and Platek [22] and served to generalize the theories of Takeuti [34], Machover [20], Kreisel and Sacks [14] and others. Kripke (in [16]) derived machinery to construct an analogue to Kleene's T-predicate enabling him to assert that all of unrelativized ordinary recursion theory (as found in Kleene [13]) lifted to α-recursion theory. As a result, we were able to set down in [8] α-analogues to Blum's [1] well-studied axioms, thus, introducing the study of α-computational complexity theory. 
Jacobs, Barry E. α-Speedable and non α-Speedable Sets. Canadian journal of mathematics, Tome 31 (1979) no. 2, pp. 282-299. doi: 10.4153/CJM-1979-030-8
@article{10_4153_CJM_1979_030_8,
     author = {Jacobs, Barry E.},
     title = {\ensuremath{\alpha}-Speedable and non {\ensuremath{\alpha}-Speedable} {Sets}},
     journal = {Canadian journal of mathematics},
     pages = {282--299},
     year = {1979},
     volume = {31},
     number = {2},
     doi = {10.4153/CJM-1979-030-8},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1979-030-8/}
}
TY  - JOUR
AU  - Jacobs, Barry E.
TI  - α-Speedable and non α-Speedable Sets
JO  - Canadian journal of mathematics
PY  - 1979
SP  - 282
EP  - 299
VL  - 31
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1979-030-8/
DO  - 10.4153/CJM-1979-030-8
ID  - 10_4153_CJM_1979_030_8
ER  - 
%0 Journal Article
%A Jacobs, Barry E.
%T α-Speedable and non α-Speedable Sets
%J Canadian journal of mathematics
%D 1979
%P 282-299
%V 31
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1979-030-8/
%R 10.4153/CJM-1979-030-8
%F 10_4153_CJM_1979_030_8

[1] 1. Blum, M., A machine-independent theory of the complexity of recursive functions, J. AC. 14 (1967), 322–336. Google Scholar

[2] 2. Blum, M. and Marques, I., On complexity properties of recursively enumerable sets, J. Symbol Logi. 35 (1973), 579–593. Google Scholar

[3] 3. Dekker, J. C. E., A theorem on hypersimple sets, Proc. Amer. Math. Soc. 5 (1954), 791–796. Google Scholar

[4] 4. Driscoll, G. C., Metarecursively enumerable sets and their metadegrees, J. Symb. Logi. 33 (1968), 389–411. Google Scholar

[5] 5. Gill, J. and Morris, P., On subcreative sets and S-reducibility, J. Symb. Logi. 39 (1974), 669–677. Google Scholar

[6] 6. Hay, L., The class of recursively enumerable subsets of a recursively enumerable set, Pacific J. Math. 46 (1973), 167–183. Google Scholar

[7] 7. Hay, L., The halting problem relativized to complements, Proc. AMS. 41 (1973), 583–587. Google Scholar

[8] 8. Jacobs, B., ɑ-computational complexity, Ph.D. Thesis, Technical report IMM 408, Courant Inst., (1975). Google Scholar

[9] 9. Jacobs, B., On generalized computational complexity, J. Symb. Logic, 42 (1977), 47–58. Google Scholar

[10] 10. Jacobs, B., The a-union theorem and generalized primitive recursion, Trans. A.M.S.. 237 (1978), 63–81. Google Scholar

[11] 11. Jacobs, B., The a-speedup and a-naming theorems, to appear. Google Scholar

[12] 12. Jockusch, C., Semirecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (1968), 420–436. Google Scholar

[13] 13. Kleene, S. C., Introduction to metamathematics, (North-Holland, Amsterdam, 1971). Google Scholar

[14] 14. Kreisel, G. and Sacks, G. E., Metarecursive sets, J. Symb. Logic. 30, (1965), 318–338. Google Scholar

[15] 15. Kripke, S., Transfinite recursion on admissible ordinals, I, II (abstracts), J. Symb. Logic, 29 (1964), 161–162. Google Scholar

[16] 16. Kripke, S., The theory of transfinite recursions, unpublished, class notes by A. Thomas Tymoczko. Google Scholar

[17] 17. Lerman, M., Least upper bounds for minimal pairs of a-r.e. a-degrees, J. Symb. Logic. 39 (1974), 49–56. Google Scholar

[18] 18. Lerman, M., Maximal a-r.e. sets, Trans. A.M.S. 188 (1974), 341–386. Google Scholar

[19] 19. Lerman, M. and Simpson, S. G., Maximal sets in a-recursion theory, Israel J. Math. 14 (1972), 236–247. Google Scholar

[20] 20. Machover, M., The theory of transfinite recursion, Bull. Am. Math. Soc. 67 (1961), 575–578. Google Scholar

[21] 21. Marques, I., On degrees of unsolvability and complexity properties, J. Symb. Logi. 40 (1975), 529–540. Google Scholar

[22] 22. Platek, R., Foundations of recursion theory, Ph.D. Thesis, Stanford (1966). Google Scholar

[23] 23. Rogers, H., Theory of recursive functions and effective computability, (McGraw-Hill, 1967). Google Scholar

[24] 24. Sacks, G. E., Post's problem, admissible ordinals and regularity, Trans. Amer. Math. Soc. 124 (1966), 1–24. Google Scholar

[25] 25. Sacks, G. E., Degrees of unsolvability, Ann. Math. Study 55 (Princeton, 1966). Google Scholar

[26] 26. Sacks, G. E., Higher recursion theory, Springer-Verlag (Berlin), to appear. Google Scholar

[27] 27. Shoenfield, J. R., Degrees of unsolvability, (North-Holland, Amsterdam, 1971). Google Scholar

[28] 28. Shore, R., Splitting an a-recursively enumerable set, Trans. A.M.S.. 204 (1975), 67–78. Google Scholar

[29] 29. Shore, R., The irregular and nonhyperbolic a-r.e. degree, Israel J. Math. 22 (1975), 28–41. Google Scholar

[30] 30. Shore, R., On the jump of an a-recursively enumerable set, Trans. Amer. Math. Soc. 217 (1976), 351–363. Google Scholar

[31] 31. Simpson, S. G., Admissible ordinals and recursion theory, Ph.D. Thesis, Mass. Inst. Tech., 1971. Google Scholar

[32] 32. Simpson, S. G., Degree theory on admissible ordinals, in Generalized Recursion Theory, (1972), North-Holland, 165–193. Google Scholar

[33] 33. Soare, R., Computational complexity, speedable and levelable sets, J. Symb. Logic. 42 (1977), 545–563. Google Scholar

[34] 34. Takeuti, G., On the recursive functions of ordinal numbers, J. Math. Soc. Japa. 12 (1960), 119–128. Google Scholar

Cité par Sources :