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.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 semiThue 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. 

