A reducibility condition for recursiveness
HTML articles powered by AMS MathViewer
- by Paul H. Morris PDF
- Proc. Amer. Math. Soc. 60 (1976), 270-272 Request permission
Abstract:
A result due to Jockusch, equating recursiveness of a set to a reducibility condition on its jump, is sharpened.References
- Ju. L. Eršov, A certain hierarchy of sets. I, Algebra i Logika 7 (1968), no. 1, 47–74 (Russian). MR 0270911
- John T. Gill III and Paul H. Morris, On subcreative sets and $S$-reducibility, J. Symbolic Logic 39 (1974), 669–677. MR 363840, DOI 10.2307/2272852
- Louise Hay, A noninitial segment of index sets, J. Symbolic Logic 39 (1974), 209–224. MR 354333, DOI 10.2307/2272633
- Louise Hay, The halting problem relativized to complements, Proc. Amer. Math. Soc. 41 (1973), 583–587. MR 327495, DOI 10.1090/S0002-9939-1973-0327495-X
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462 R.I. Soare, Degrees and structure of speedable sets, Abstract, January, 1974 (preprint).
- Robert I. Soare, Automorphisms of the lattice of recursively enumerable sets, Bull. Amer. Math. Soc. 80 (1974), 53–58. MR 373858, DOI 10.1090/S0002-9904-1974-13350-1
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 60 (1976), 270-272
- MSC: Primary 02F25; Secondary 02F30
- DOI: https://doi.org/10.1090/S0002-9939-1976-0416880-6
- MathSciNet review: 0416880