On n-permutation Post Correspondence Problem

: Vesa Halava, Tero Harju, Mari Huova

Publisher: TUCS Technical Report 1084

: Turku

: 2013

: http://tucs.fi/publications/view/?pub_id=tHaHaHu13a

We give new and simpler proof for the undecidability of the n-permutation Post
Correspondence Problem that was originally proved by K. Ruohonen (Acta
Informatica 19 (1983), 357 -- 367). Our proof uses a recent undecidability result on
deterministic semi-Thue systems that says that it is undecidable, for a given deterministic semi-Thue system T and a word u, whether or not there exists a nonempty cyclic
derivation u ->^+ u in T.