Auto comment: topic has been updated by MOOONI (previous revision, new revision, compare).

Auto comment: topic has been updated by MOOONI (previous revision, new revision, compare).

If you try all possible permutations, you would still have no guarantee of finding a solution because it is possible for the PCP to have no solution

My understanding is that the main issue is that the length of the answer can be arbitrarily large. This is because you're not just permuting the two lists of dominos -- you are actually allowed to repeat dominos as much as you like.

As the other commenter said, there can be no solution. So the naive algorithm of iterating over the length of the answer and trying all solutions of that length might never halt, because you never know if the solution is just really long or if none exist.

What makes the PCP problem undecidable is precisely the unlimited number of times a given tile can be used. If the number of tiles that could be used was bounded, your solution would indeed decide the problem. However, since you have an unlimited supply of tiles, you would have to find and check “all permutations of an infinite set of tiles”, which doesn’t quite work.