Recursive enumerability and the jump operator
Author:
Gerald E. Sacks
Journal:
Trans. Amer. Math. Soc. 108 (1963), 223-239
MSC:
Primary 02.70
DOI:
https://doi.org/10.1090/S0002-9947-1963-0155747-3
MathSciNet review:
0155747
Full-text PDF Free Access
References | Similar Articles | Additional Information
- [1] Richard Friedberg, A criterion for completeness of degrees of unsolvability, J. Symbolic Logic 22 (1957), 159–160. MR 98025, https://doi.org/10.2307/2964177
- [2] Richard M. Friedberg, Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post’s problem, 1944), Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 236–238. MR 84474, https://doi.org/10.1073/pnas.43.2.236
- [3] Stephen Cole Kleene, Introduction to metamathematics, D. Van Nostrand Co., Inc., New York, N. Y., 1952. MR 0051790
- [4] S. C. Kleene and Emil L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. MR 61078, https://doi.org/10.2307/1969708
- [5] A. A. Muchnik, Negative answer to the problem of reducibility of algorithms, Dokl. Akad. Nauk SSSR 108 (1956), 194-197. (Russian)
- [6] Gerald E. Sacks, The universality of the recursively enumerable degrees, Abstract No. 60T-14, Notices Amer. Math. Soc. 7 (1960), 996.
- [7] J. R. Shoenfield, On degrees of unsolvability, Ann. of Math. (2) 69 (1959), 644–653. MR 105355, https://doi.org/10.2307/1970028
- [8] Clifford Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581–592. MR 82457, https://doi.org/10.2307/1969604
Retrieve articles in Transactions of the American Mathematical Society with MSC: 02.70
Retrieve articles in all journals with MSC: 02.70
Additional Information
DOI:
https://doi.org/10.1090/S0002-9947-1963-0155747-3
Article copyright:
© Copyright 1963
American Mathematical Society