On the steps of Emil Post : from normal systems to the correspondence decision problem

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)

[thumbnail of cybernetica_024_numb_004_613-623.pdf]
Cikk, tanulmány, mű

Download (209kB) | Preview


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 View Item