On the n-permutation Post Correspondence Problem

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 u→T+u in T.