Are the following instances of post correspondence problem solvable? Find, if possible, various non-periodic solutions or prove the insolubility.
- $\alpha = (11, 01, 001)$, $\beta = (011, 0, 110)$
- $\alpha = (101, 100, 0, 00111)$, $\beta = (1, 0, 010, 010111)$
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 sequence 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?
At the second one, the number of "0" in $\alpha$ is not the same as the number of "0" in $\beta$. Would that imply that this problem is also not solvable?
What possible values can $i_k$ and $i_{k-1}$ have?
There are several common sequences with 4 symbols. Can you find all three?