{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T14:18:47Z","timestamp":1773152327097,"version":"3.50.1"},"reference-count":14,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":16589,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1968,10,10]]},"abstract":"<jats:p>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 <jats:italic>a, b<\/jats:italic> 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.<\/jats:p>","DOI":"10.2307\/2270327","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T20:49:03Z","timestamp":1146948543000},"page":"418-430","source":"Crossref","is-referenced-by-count":6,"title":["The post correspondence problem"],"prefix":"10.1017","volume":"33","author":[{"given":"Dennis F.","family":"Cudia","sequence":"first","affiliation":[]},{"given":"Wilson E.","family":"Singletary","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S002248120010996X_ref014","doi-asserted-by":"publisher","DOI":"10.1145\/321371.321384"},{"key":"S002248120010996X_ref013","first-page":"1","article-title":"Recursive unsolvability of a problem of Thue","volume":"12","author":"Post","year":"1947","journal-title":"this Journal"},{"key":"S002248120010996X_ref012","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08555-9"},{"key":"S002248120010996X_ref010","doi-asserted-by":"publisher","DOI":"10.2307\/2371809"},{"key":"S002248120010996X_ref009","first-page":"194","article-title":"Negative answer to the problem of reducibility of the theory of algorithms (in Russian)","volume":"108","author":"M\u00fa\u010dnik","year":"1956","journal-title":"Dokl. Acad. Nauk SSSR"},{"key":"S002248120010996X_ref006","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.43.2.236"},{"key":"S002248120010996X_ref005","volume-title":"Computability and unsolvability","author":"Davis","year":"1958"},{"key":"S002248120010996X_ref004","first-page":"267","article-title":"Post's correspondence problem and degrees of unsolvability; Degrees of unsolvability in automata and grammars","volume":"30","author":"Cudia","year":"1965","journal-title":"this Journal"},{"key":"S002248120010996X_ref001","doi-asserted-by":"publisher","DOI":"10.2307\/1970103"},{"key":"S002248120010996X_ref002","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1962-10876-3"},{"key":"S002248120010996X_ref011","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1944-08111-1"},{"key":"S002248120010996X_ref007","unstructured":"Ihrig A. H. , (1964) Applications of recursive function theory to algebra, Doctoral dissertation, Univ. of Illinois, pp. 1\u201361 + appendix."},{"key":"S002248120010996X_ref008","volume-title":"Introduction to metamathematics","author":"Kleene","year":"1952"},{"key":"S002248120010996X_ref003","doi-asserted-by":"publisher","DOI":"10.2307\/1970478"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S002248120010996X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T20:49:51Z","timestamp":1559422191000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S002248120010996X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1968,10,10]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1968,10,10]]}},"alternative-id":["S002248120010996X"],"URL":"https:\/\/doi.org\/10.2307\/2270327","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1968,10,10]]}}}