Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

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

 
 

 

The equivalence of some general combinatorial decision problems


Author: W. E. Singletary
Journal: Bull. Amer. Math. Soc. 73 (1967), 446-451
DOI: https://doi.org/10.1090/S0002-9904-1967-11780-4
Errata: Bull. Amer. Math. Soc., Volume 74, Number 4 (1968), 767--768
MathSciNet review: 0210590
Full-text PDF

References | Additional Information

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

  • 1. W. W. Boone, The word problem, Ann. of Math. 70 (1959), 207-265. MR 179237
  • 2. W. W. Boone, Word problems and recursively enumerable degrees of unsolvability. A first paper on Thue systems, Ann. of Math. 83 (1966), 520-571; Bull. Amer. Math. Soc. 68 (1962), 616-623. MR 201499
  • 3. D. F. Cudia and W. E. Singletary, The Post correspondence problem, J. Assoc. Comput. Mach. (to appear). MR 244050
  • 4. M. Davis, Computability and unsolvability, McGraw-Hill, New York, 1958. MR 124208
  • 5. M. D. Gladstone, Doctoral Dissertation, University of Bristol, England, 1963; Trans. Amer. Math. Soc. 118 (1965) 192-210.
  • 6. Hans Hermes, Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit, 3rd ed., Heidelberger Taschenbücher [Heidelberg Paperbacks], vol. 87, Springer-Verlag, Berlin-New York, 1978 (German). Einführung in die Theorie der rekursiven Funktionen. MR 519338
  • 7. A. H. Ihrig, Doctoral Dissertation, University of Illinois, Urbana, Ill., 1964; Notre Dame J. Formal Logic 6 (1965), 54-72.
  • 8. E. L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197-215. MR 7893
  • 9. E. L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284-316. MR 10514
  • 10. E. L. Post, A variant of an unsolvable problem, Bull. Amer. Math. Soc. 52 (1946), 264-268. MR 15343
  • 11. E. L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1-11. MR 20527
  • 12. J. C. Shepherdson, Machine configuration and word problems of given degree of unsolvability, Z. Math. Logik Grundlagen 11 (1965), 149-175; Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science, North-Holland, Amsterdam, 1965. MR 174480
  • 13. W. E. Singletary, Recursive unsolvability of a complex of problems proposed by Post, J. Math. Soc. Japan (to appear); Bull. Amer. Math. Soc. 70 (1964), 105-109. MR 158817
  • 14. M. K. Yntema, A detailed argument for the post-linial theorems, Notre Dame Journal of Formal Logic 5 (1964), 37-50. MR 170796


Additional Information

DOI: https://doi.org/10.1090/S0002-9904-1967-11780-4

American Mathematical Society