Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 

 

The decision problem for recursively enumerable degrees


Author: J. R. Shoenfield
Journal: Bull. Amer. Math. Soc. 81 (1975), 973-977
MSC (1970): Primary 02F25, 02F30
MathSciNet review: 0387035
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • 1. 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 0084474
  • 2. 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 0061078
  • 3. A. H. Lachlan, The impossibility of finding relative complements for recursively enumerable degrees, J. Symbolic Logic 31 (1966), 434–454. MR 0205847
  • 4. A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537–569. MR 0204282
  • 5. A. H. Lachlan, Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlagen Math. 14 (1968), 457–472. MR 0237331
  • 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.
  • 7. 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
  • 8. Gerald E. Sacks, Degrees of unsolvability, Princeton University Press, Princeton, N.J., 1963. MR 0186554
  • 9. 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
  • 10. J. R. Shoenfield, Measurable cardinals, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969), North-Holland, Amsterdam, 1971, pp. 19–49. MR 0282830
  • 11. Clifford Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581–592. MR 0082457
  • 12. S. K. Thomason, Sublattices of the recursively enumerable degrees, Z. Math. Logik Grundlagen Math. 17 (1971), 273–280. MR 0299475
  • 13. C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 159–168. MR 0205851

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1970): 02F25, 02F30

Retrieve articles in all journals with MSC (1970): 02F25, 02F30


Additional Information

DOI: https://doi.org/10.1090/S0002-9904-1975-13876-6