Let the Post Correspondence problem with input

$$K = ((x_1, y_1), . . . ,(x_n, y_n)), x_i, y_i ∈ \Sigma^*$$

for $$ i = 1, . . . , n $$

Find a concrete solution for the input

$$K = ((001,0), (01, 011),(01, 101),(10, 001))$$

The Post Correspondence problem is undecidable so it's really hard to find a concrete solution. I've tried brute forcing it but it gets frustrating after a few tries.

Is there a logical way to deduce that K is a solution, rather than finding a pattern that works?

  • $\begingroup$ Interesting example. Where does it originate? (I googled PCP 66, see the solution by Yuval, and found several lectures where the example was given.) $\endgroup$ – Hendrik Jan Nov 23 '17 at 23:32

The smallest solution is


generated by the string


where $a = (001,0)$, $b=(01,011)$, $c=(01,101)$, $d=(10,001)$.

This solution can be found by a simple pruning procedure:

  1. Start with the list $L$ which contains a pair of empty strings.
  2. At each iteration, attempt to add each of the four "pieces" to each of the pairs in $L$, and remove any pair for which no string is a prefix of the other.

Eventually $L$ will contain a pair of equal strings, in this case after 66 iterations.

As an example, here is the contents of $L$ in the first few iterations:

  1. Iteration 1: (001,0), (01,011)
  2. Iteration 2: (001001,00), (0110,011001)
  3. Iteration 3: (011001,011001011), (011001,011001101)
  4. Iteration 4: (01100101,011001011011), (01100101,011001011101), (01100110,011001101001)

The number of pairs of strings at every iteration fluctuates but generally increases, and after 66 iterations reaches 12081, one of which is the solution given above.

  • $\begingroup$ That's a great answer! I guess the only way to tackle the undecidable problems is to either try out everything or to figure out some kind of logic that will lower the number of possibilities. In all cases, the undecidable problems are a real pain. $\endgroup$ – Billy Joel Nov 23 '17 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.