The decision problem for recursively enumerable degrees
HTML articles powered by AMS MathViewer
- by J. R. Shoenfield PDF
- Bull. Amer. Math. Soc. 81 (1975), 973-977
References
- 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, DOI 10.1073/pnas.43.2.236
- 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, DOI 10.2307/1969708
- A. H. Lachlan, The impossibility of finding relative complements for recursively enumerable degrees, J. Symbolic Logic 31 (1966), 434–454. MR 205847, DOI 10.2307/2270459
- A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537–569. MR 204282, DOI 10.1112/plms/s3-16.1.537
- A. H. Lachlan, Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlagen Math. 14 (1968), 457–472. MR 237331, DOI 10.1002/malq.19680143002 6. A. H. Lachlan, Embedding nondistributive lattices in the recursively enumerable degrees, Conference in Mathematical Logic—London ’70, Lecture Notes in Math., vol. 255, Springer-Verlag, New York, 1972, pp. 149-177.
- A. A. Mučnik, On the unsolvability of the problem of reducibility in the theory of algorithms, Dokl. Akad. Nauk SSSR (N.S.) 108 (1956), 194–197 (Russian). MR 0081859
- Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
- J. R. Shoenfield, Applications of model theory to degrees of unsolvability, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 359–363. MR 0200154
- J. R. Shoenfield, Measurable cardinals, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969) North-Holland, Amsterdam, 1971, pp. 19–49. MR 0282830
- Clifford Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581–592. MR 82457, DOI 10.2307/1969604
- S. K. Thomason, Sublattices of the recursively enumerable degrees, Z. Math. Logik Grundlagen Math. 17 (1971), 273–280. MR 299475, DOI 10.1002/malq.19710170131
- C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159–168. MR 205851, DOI 10.2307/2269807
Additional Information
- Journal: Bull. Amer. Math. Soc. 81 (1975), 973-977
- MSC (1970): Primary 02F25, 02F30
- DOI: https://doi.org/10.1090/S0002-9904-1975-13876-6
- MathSciNet review: 0387035