Welcome to our community

Be a part of something great, join today!

Are the instances of PCP solvable?


Well-known member
MHB Site Helper
Apr 14, 2013
Hey!! :eek:

Are the following instances of post correspondence problem solvable? Find, if possible, various non-periodic solutions or prove the insolubility.

1. $\alpha = (bb, ab, aab)$, $\beta = (abb, a, bba)$
2. $\alpha = (bab, baa, a, aabbb)$, $\beta = (b, a, aba, ababbb)$

For the first one I tried various sequences but I didnt find a common sequence so I suppose that this one is not solvable. Is that correct?

To prove that, we suppose that the problem is solvable.

There exists a $k\in \mathbb{N}$ and a seuquence of indices $i_1, \ldots , i_k\in \{1, 2, 3\}$ with $\alpha_{i_1}\dots \alpha_{i_k}=\beta_{i_1}\dots \beta_{i_k}$.

How can we continue to get a contradiction? Or is the problem solvable? (Wondering)

At the second one, the number of "a" in $\alpha$ is not the same as the number of "a" in $\beta$. Would that imply that this problem is also not solvable? (Wondering)