The post correspondence problem
- 10 October 1968
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 33 (3) , 418-430
- https://doi.org/10.2307/2270327
Abstract
The correspondence decision problem was first formulated and shown to be recursively unsolvable in Post (1946). The method of proof was to reduce the known unsolvable decision problem for the class of normal systems on a, b to the correspondence decision problem. In the present paper the concept of a standard Post normal system is used so as to obtain some equivalence reductions of combinatorial systems. In particular the following main result is obtained.Keywords
This publication has 10 references indexed in Scilit:
- A Remark on Post Normal SystemsJournal of the ACM, 1967
- Word Problems and Recursively Enumerable Degrees of Unsolvability. A First Paper on Thue SystemsAnnals of Mathematics, 1966
- Partial results regarding word problems and recursively enumerable degrees of unsolvabilityBulletin of the American Mathematical Society, 1962
- The Word ProblemAnnals of Mathematics, 1959
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)Proceedings of the National Academy of Sciences, 1957
- Introduction to Metamathematics. By S. C. Kleene. Pp. x, 550, Fl. 32.50. 1952. (Noordhoff, Groningen; North-Holland Publishing Co., Amsterdam)The Mathematical Gazette, 1954
- Recursive Unsolvability of a problem of ThueThe Journal of Symbolic Logic, 1947
- A variant of a recursively unsolvable problemBulletin of the American Mathematical Society, 1946
- Recursively enumerable sets of positive integers and their decision problemsBulletin of the American Mathematical Society, 1944
- Formal Reductions of the General Combinatorial Decision ProblemAmerican Journal of Mathematics, 1943