A1 Refereed original research article in a scientific journal
On the Steps of Emil Post: from Normal Systems to the Correspondence Decision Problem
Authors: Halava Vesa, Harju Tero
Publisher: UNIV SZEGED, FAC SCIENCE
Publication year: 2020
Journal: Acta Cybernetica
Journal name in source: ACTA CYBERNETICA
Journal acronym: ACTA CYBERN
Volume: 24
Issue: 4
First page : 613
Last page: 623
Number of pages: 11
ISSN: 0324-721X
eISSN: 2676-993X
DOI: https://doi.org/10.14232/actacyb.284625
Self-archived copy’s web address: https://research.utu.fi/converis/portal/Publication/51396818
Abstract
In 1946 Emil Leon Post (Bull. Amer. Math. Soc. 52 (1946), 264-268) introduced his famous correspondence decision problem, nowadays known as the Post Correspondence Problem (PCP). Post proved the undecidability of the PCP by a reduction from his normal systems. In the present article we follow the steps of Post, and give another, somewhat simpler and more straightforward proof 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 the approach taken by Post.
In 1946 Emil Leon Post (Bull. Amer. Math. Soc. 52 (1946), 264-268) introduced his famous correspondence decision problem, nowadays known as the Post Correspondence Problem (PCP). Post proved the undecidability of the PCP by a reduction from his normal systems. In the present article we follow the steps of Post, and give another, somewhat simpler and more straightforward proof 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 the approach taken by Post.
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal