Post Correspondence Problem, $(1101, 1),(0110,11),(1,110)$

159 Views Asked by At

I'm trying to solve a Post Correspondence Problem, $$(1101, 1),(0110,11),(1,110)$$

I'm not aware of any method of telling if this has a solution aside from trying different sequences. So I tried

$$1101.1.1.0110.$$ $$110.1.110.110$$

I think that's correct or am I wrong?

1

There are 1 best solutions below

0
On BEST ANSWER

The rule is that you have arbitary many stones of the given sorts. You have to put finite many together in such a way that (not considering spaces) the created words coincide.

According to my PCP-solver, this problem has no solution within $200$ moves, so I guess it is not solveable. It might be interesting to prove this. Perhaps I will try to find a proof.

PCP is undecideable in general.