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
DOI: https://doi.org/10.1090/S0002-9904-1975-13876-6
MathSciNet review: 0387035
Full-text PDF

References | Similar Articles | Additional Information

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

  • 1. R. 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 18, 867. MR 84474
  • 2. S. C. Kleene and E. L. Post, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379-407. MR 15, 772. MR 61078
  • 3. A. H. Lachlan, The impossibility of finding relative complements for recursively enumerable degrees, J. Symbolic Logic 31 (1966), 434-454. MR 34 #5673. MR 205847
  • 4. A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3) 16 (1966), 537-569. MR 34 #4126. MR 204282
  • 5. A. H. Lachlan, Distributive initial segments of the degrees of unsolvability, Z. Math. Logik Grundlagen Math. 14 (1968), 457-472. MR 38 #5620. MR 237331
  • 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, Negative answer to the problem of reducibility of the theory of algorithms, Dokl. Akad. Nauk SSSR 108 (1956), 194-197. (Russian). MR 81859
  • 8. G. E. Sacks, Degrees of unsolvability, Ann. of Math. Studies, no. 55, Princeton Univ. Press, Princeton, N.J., 1963. MR 32 #4013. MR 186554
  • 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 34 #53. MR 200154
  • 10. J. R. Shoenfield, Degrees of unsolvability, North-Holland, Amsterdam, 1971. MR 282830
  • 11. C. Spector, On degrees of recursive unsolvability, Ann. of Math. (2) 64 (1956), 581-592. MR 18, 552, 1118. MR 82457
  • 12. S. K. Thomason, Sublattices of the recursively enumerable degrees, Z. Math. Logik Grundlagen Math. 17 (1971), 273-280. MR 45 #8523. MR 299475
  • 13. C. E. M. Yates, A minimal pair of recursively enumerable degrees, J. Symbolic Logic 31 (1966), 158-168. MR 34 #5677. MR 205851

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

American Mathematical Society