The equivalence of some general combinatorial decision problems
HTML articles powered by AMS MathViewer
- by W. E. Singletary PDF
- Bull. Amer. Math. Soc. 73 (1967), 446-451
References
- William W. Boone, The word problem, Ann. of Math. (2) 70 (1959), 207–265. MR 179237, DOI 10.2307/1970103
- William W. Boone, Word problems and recursively enumerable degrees of unsolvability. A first paper on Thue systems, Ann. of Math. (2) 83 (1966), 520–571. MR 201499, DOI 10.2307/1970478
- Dennis F. Cudia and Wilson E. Singletary, The Post correspondence problem, J. Symbolic Logic 33 (1968), 418–430. MR 244050, DOI 10.2307/2270327
- Martin Davis, Computability and unsolvability, McGraw-Hill Series in Information Processing and Computers, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1958. MR 0124208 5. M. D. Gladstone, Doctoral Dissertation, University of Bristol, England, 1963; Trans. Amer. Math. Soc. 118 (1965) 192-210.
- 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, DOI 10.1007/978-3-642-95327-9 7. A. H. Ihrig, Doctoral Dissertation, University of Illinois, Urbana, Ill., 1964; Notre Dame J. Formal Logic 6 (1965), 54-72.
- Emil L. Post, Formal reductions of the general combinatorial decision problem, Amer. J. Math. 65 (1943), 197–215. MR 7893, DOI 10.2307/2371809
- Emil L. Post, Recursively enumerable sets of positive integers and their decision problems, Bull. Amer. Math. Soc. 50 (1944), 284–316. MR 10514, DOI 10.1090/S0002-9904-1944-08111-1
- Emil L. Post, A variant of a recursively unsolvable problem, Bull. Amer. Math. Soc. 52 (1946), 264–268. MR 15343, DOI 10.1090/S0002-9904-1946-08555-9
- Emil L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic Logic 12 (1947), 1–11. MR 20527, DOI 10.2307/2267170
- J. C. Shepherdson, Machine configuration and word problems of given degree of unsolvability, Z. Math. Logik Grundlagen Math. 11 (1965), 149–175. MR 174480, DOI 10.1002/malq.19650110210
- Wilson E. Singletary, A complex of problems proposed by Post, Bull. Amer. Math. Soc. 70 (1964), 105–109. MR 158817, DOI 10.1090/S0002-9904-1964-11038-7
- Mary Katherine Yntema, A detailed argument for the Post-Linial theorems, Notre Dame J. Formal Logic 5 (1964), 37–50. MR 170796
Additional Information
- Journal: Bull. Amer. Math. Soc. 73 (1967), 446-451
- DOI: https://doi.org/10.1090/S0002-9904-1967-11780-4
- MathSciNet review: 0210590