A New Proof for Undecidability of the Bi-Infinite Post Correspondence Problem

Issue title: Elegant Structures in Computation. To Andrzej Ehrenfeucht on His 85th Birthday

Guest editors: Gheorghe Păun, Grzegorz Rozenberg and Arto Salomaa

Article type: Research Article

Authors: Halava, Vesa^{; *} | Harju, Tero | Sahla, Esa^{; †}

Affiliations: Department of Mathematics and Statistics, University of Turku, Finland. {vesa.halava, harju, estasa}@utu.fi

Correspondence: [†] Address for correspondence: Department of Mathematics and Statistics, University of Turku, Finland

Note: [*] Also affiliated at: Department of Computer Science, University of Liverpool, UK

Abstract: We give a new simplified proof for undecidability of the Bi-Infinite Post Correspondence Problem (ℤPCP). We reduce the special case of the word problem of semi-Thue systems to ℤPCP.

DOI: 10.3233/FI-2017-1558

Journal: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 167-176, 2017