Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-22T16:01:01.475Z Has data issue: false hasContentIssue false
  • English
  • Français

The post correspondence problem1

Published online by Cambridge University Press:  12 March 2014

Dennis F. Cudia  and
Wilson E. Singletary
Dennis F. Cudia
Affiliation:
The University of Wisconsin The Pennsylvania State University
Wilson E. Singletary
Affiliation:
The University of Wisconsin The Pennsylvania State University
Get access Rights & Permissions [Opens in a new window]

Extract

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 33 , Issue 3 , 10 October 1968 , pp. 418 - 430
Copyright
Copyright © Association for Symbolic Logic 1968

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

The Main Result of the present paper was presented to the International Congress of Mathematicians, Moscow, August 1966.

References

Boone, W. W., (1959) The word problem, Annals of mathematics, vol. 70, pp. 207–265.CrossRefGoogle Scholar
Boone, W. W., (1962) Partial results regarding word problems and recursively enumerable degrees of unsolvability, Bulletin of the American Mathematical Society, vol. 68, pp. 616–623.CrossRefGoogle Scholar
Boone, W. W., (1966) Word problems and recursively enumerable degrees of unsolvability. A first paper on Thue systems, Annals of mathematics, vol. 83, pp. 520–571.CrossRefGoogle Scholar
Cudia, D. F. and Singletary, W. E., (1965) Post's correspondence problem and degrees of unsolvability; Degrees of unsolvability in automata and grammars, this Journal, vol. 30, pp. 267–268.Google Scholar
Davis, M., (1958) Computability and unsolvability, McGraw-Hill, New York.Google Scholar
Friedberg, R. M., (1957) Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944), Proceedings of the National Academy of Sciences U.S.A., vol. 43, pp. 236–238.CrossRefGoogle ScholarPubMed
Ihrig, A. H., (1964) Applications of recursive function theory to algebra, Doctoral dissertation, Univ. of Illinois, pp. 1–61 + appendix.Google Scholar
Kleene, S. C., (1952) Introduction to metamathematics, Van Nostrand, Princeton, N.J.Google Scholar
Múčnik, A. A., (1956) Negative answer to the problem of reducibility of the theory of algorithms (in Russian), Dokl. Acad. Nauk SSSR, vol. 108, pp. 194–197.Google Scholar
Post, E. L., (1943) Formal reductions of the general combinatorial decision problem, American journal of mathematics, vol. 65, pp. 197–215.CrossRefGoogle Scholar
Post, E. L., (1944) Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50, pp. 284–316.CrossRefGoogle Scholar
Post, E. L., (1946) A variant of a recursively unsolvable problem, Bulletin of the American Mathematical Society, vol. 52, pp. 264–268.CrossRefGoogle Scholar
Post, E. L., (1947) Recursive unsolvability of a problem of Thue, this Journal, vol. 12, pp. 1–11.Google Scholar
Yasuhara, A. H., (1967) A remark on Post normal systems, Journal of the Association for Computing Machinery, vol. 14, pp. 167–171.CrossRefGoogle Scholar