Halava Vesa and Harju Tero: On the steps of Emil Post : from normal systems to the correspondence decision problem. In: Acta cybernetica, (24) 4. pp. 613-623. (2020)
Preview |
Cikk, tanulmány, mű
cybernetica_024_numb_004_613-623.pdf Download (209kB) | Preview |
Abstract
In 1946, Emil Leon Post (Bulletin of Amer. Math. Soc. 52 (1946), 264-268) introduced his famouscorrespondence decision problem, nowadays known as the Post Correspondence Problem (PCP).Post proved the undecidability of the PCP by areduction from his normal systems. In the presentarticle we follow the steps of Post, and give another, somewhat simpler and more straightforwardproof of the undecidability of the problem by using the same source of reductions as Post did.We investigate these, very different, techniques, and point out out some peculiarities in theapproach used by Post.
| Item Type: | Article |
|---|---|
| Journal or Publication Title: | Acta cybernetica |
| Date: | 2020 |
| Volume: | 24 |
| Number: | 4 |
| ISSN: | 0324-721X |
| Page Range: | pp. 613-623 |
| Language: | English |
| Publisher: | University of Szeged, Institute of Informatics |
| Place of Publication: | Szeged |
| Related URLs: | http://acta.bibl.u-szeged.hu/71734/ |
| DOI: | 10.14232/actacyb.284625 |
| Uncontrolled Keywords: | Kibernetika |
| Additional Information: | Bibliogr.: 623. p. ; összefoglalás angol nyelven |
| Subjects: | 01. Natural sciences 01. Natural sciences > 01.02. Computer and information sciences |
| Date Deposited: | 2021. Feb. 05. 11:52 |
| Last Modified: | 2022. Jun. 21. 09:22 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/71765 |
Actions (login required)
 |
View Item |
