On the n-permutation Post Correspondence Problem
: Mari Ernvall, Vesa Halava, Tero Harju
Publisher: Elsevier BV
: 2015
: Theoretical Computer Science
: THEORETICAL COMPUTER SCIENCE
: THEOR COMPUT SCI
: 601
: 11
: 15
: 20
: 6
: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2015.07.021
We give new and simpler proof for the undecidability of the n-permutation Post Correspondence Problem that was originally proved by K. Ruohonen [10]. Our proof uses a recent result on deterministic semi-Thue systems according to which it is undecidable for a given deterministic semi-Thue system T and a word u whether or not there exists a nonempty cyclic derivation is u in u -> (+)(T) u. (C) 2015 Elsevier B.V. All rights reserved.