|
The equivalence of some general combinatorial decision problems
Author(s):
W. E.
Singletary
Journal:
Bull. Amer. Math. Soc.
73
(1967),
446-451.
Errata:
Bull. Amer. Math. Soc., Volume 74, Number 4 (1968), 767--768
MathSciNet review:
0210590
Retrieve article in:
PDF
References |
Additional information
References:
- 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.
- H. Hermes, Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit Einführung in die Theorie der rekursiven Funktionen, Springer-Verlag, Berlin, 1961. English transl., Enumerability, decidability, computability, Springer-Verlag, Berlin, 1965. 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:
10.1090/S0002-9904-1967-11780-4
PII:
S 0002-9904(1967)11780-4
|
