most recent 30 from http://mathoverflow.net 2013-05-20T04:53:15Z http://mathoverflow.net/feeds/question/42706 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42706/post-correspondence-problem-variant jim 2010-10-18T22:55:46Z 2010-10-19T02:05:32Z

<p>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.</p>

http://mathoverflow.net/questions/42706/post-correspondence-problem-variant/42721#42721 Mark Sapir 2010-10-18T23:55:11Z 2010-10-18T23:55:11Z

<p>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.</p>