Is there an algorithm which takes as input two lists of words $v\_1,...,v\_n$ and $w\_1,...,w\_n$ over an alphabet $X$ and decides if there is an infinite sequence $(k\_i)$ where $1 \leq k\_i \leq n$ for all $i$ such that $v\_{k\_1}v\_{k\_2}...=w\_{k\_1}w\_{k\_2}...$? It seems that undecidability of the original Post Correspondence problem should imply there is no such algorithm. Is there a reference that shows undecidability of this variation of Post? Thanks.



post correspondence problem variant
See Halava, Vesa, Harju, Tero, Karhumäki, Juhani
Decidability of the binary infinite Post correspondence problem. If the alphabet consists of $\le 2$ letters, then the problem is decidable, if the number of letters is at least 7, then the problem is undecidable. The latter result is proved in Y. Matiyasevich, G. Sénizergues, Decision problems for semi-Thue systems with a few rules, in: Proceedings, 11th Annual IEEE Symposium on Logic in Computer Science, New Brunswick, NJ, 27–30 July 1996, IEEE Computer Society, Silver Spring, MD, pp. 523–531.


