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

Vesa Halava; Tero Harju

doi:10.14232/actacyb.284625

Vesa Halava Department of Mathematics and Statistics, University of Turku, Finland https://orcid.org/0000-0003-3633-4902
Tero Harju Department of Mathematics and Statistics, University of Turku, Finland https://orcid.org/0000-0002-9640-6309

DOI: https://doi.org/10.14232/actacyb.284625

Keywords: Normal systems, Post's correspondence problem, undecidability, assertion problem

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.

Downloads

Download data is not yet available.