A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On the Steps of Emil Post: from Normal Systems to the Correspondence Decision Problem
Tekijät: Halava Vesa, Harju Tero
Kustantaja: UNIV SZEGED, FAC SCIENCE
Julkaisuvuosi: 2020
Journal: Acta Cybernetica
Tietokannassa oleva lehden nimi: ACTA CYBERNETICA
Lehden akronyymi: ACTA CYBERN
Vuosikerta: 24
Numero: 4
Aloitussivu: 613
Lopetussivu: 623
Sivujen määrä: 11
ISSN: 0324-721X
eISSN: 2676-993X
DOI: https://doi.org/10.14232/actacyb.284625
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/Publication/51396818
Tiivistelmä
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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali