On the Steps of Emil Post: from Normal Systems to the Correspondence Decision Problem




Halava Vesa, Harju Tero

PublisherUNIV SZEGED, FAC SCIENCE

2020

Acta Cybernetica

ACTA CYBERNETICA

ACTA CYBERN

24

4

613

623

11

0324-721X

2676-993X

DOIhttps://doi.org/10.14232/actacyb.284625(external)

https://research.utu.fi/converis/portal/Publication/51396818(external)



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.

Last updated on 2024-26-11 at 10:49