On the steps of Emil Post from normal systems to the correspondence decision problem /
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...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
University of Szeged, Institute of Informatics
Szeged
2020
|
| Sorozat: | Acta cybernetica
24 No. 4 |
| Kulcsszavak: | Kibernetika |
| Tárgyszavak: | |
| doi: | 10.14232/actacyb.284625 |
| Online Access: | http://acta.bibl.u-szeged.hu/71765 |
| LEADER | 01468nab a2200241 i 4500 | ||
|---|---|---|---|
| 001 | acta71765 | ||
| 005 | 20220621092219.0 | ||
| 008 | 210205s2020 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 024 | 7 | |a 10.14232/actacyb.284625 |2 doi | |
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Halava Vesa | |
| 245 | 1 | 3 | |a On the steps of Emil Post |h [elektronikus dokumentum] : |b from normal systems to the correspondence decision problem / |c Halava Vesa |
| 260 | |a University of Szeged, Institute of Informatics |b Szeged |c 2020 | ||
| 300 | |a 613-623 | ||
| 490 | 0 | |a Acta cybernetica |v 24 No. 4 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Kibernetika | ||
| 700 | 0 | 1 | |a Harju Tero |e aut |
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/71765/1/cybernetica_024_numb_004_613-623.pdf |z Dokumentum-elérés |