Is PCP(3) decidable? The Post correspondence problem for lists of k words, called PCP(k), asks for a given set {(u₁ , v₁ ), . . . , (u_k , v_k )} of k pairs of words over an alphabet A, if there exists a sequence i₁ , . . . , i_m of indices such that u_i1 ... u_im = v_i1 ... v_im .

It is known that PCP(2) is decidable and PCP(7) is undecidable. What about PCP(3)?

-- JeffreyShallit - 13 Jul 2011