The uncomputable problems that we have seen so far have all been questions about computer programs. But what about more mundane problems that do not involve any programs or machines?
Post's Correspondence Problem (PCP) is based on a puzzle that involves a collection of oriented dominoes. Each domino has a top and a bottom. Each side contains a string. For example, the dominoes might look as follows.
| b | a | ca | abc | |||
| ca | ab | a | c |
You are not allowed to rotate the dominoes, but you can have as many copies of each as you like.
The puzzle is to find a sequence of dominoes that, placed side by side, has the same sequence of letters across the top as across the bottom. (Ignore the boundaries between dominoes.)
For example, using the dominoes above, here is a solution to the puzzle.
| a | b | ca | a | abc | ||||
| ab | ca | a | ab | c |
Reading off either the top or the bottom gives abcaaabc
It should be easy for you to find a set of dominoes for which there is no solution.
Input. A collection C of oriented dominoes.
Question. Is it possible to solve the above puzzle with only the dominoes in collection C?
Sipser shows a reduction from ACCEPTTM to PCP. The reduction is long, and is done in two stages.
First, a modified version of PCP called MPCP is defined. (In MPCP, you are required to start with the first domino.) Then Sipser shows
ACCEPTTM ≤m MPCP,
MPCP ≤m PCP.
Since relation ≤m is transitive, conclude that ACCEPTTM ≤m PCP.
Because of the length of the proof, I will not reproduce it here. But it is interesting to note that the proof relies on using Turing machines. It uses MPCP to simulate a Turing machine computation. With a more complicated model of computation, this proof would really be unwieldy.
At first glance, PCP does not seem all that difficult to solve. You just start trying sequences of dominoes.
Part of what makes PCP so difficult is that there are collections of dominoes that let you chain together arbitrarily long sequences without reaching a solution. Look at the following dominoes
| a | bab | |
| aba | bba |
A solution clearly cannot start with the second domino. So let's start with the first one.
| a |
| aba |
Now we have no choice but to use the second domino.
| a | bab | |
| aba | bba |
The top reads abab and the bottom reads ababba. The bottom has an extra ba. Again, we have no choice but to use the second domino.
| a | bab | bab | ||
| aba | bba | bba |
The bottom still has an extra ba. You can keep adding copies of the second domino as long as you want, but you will never finish the puzzle.
But it is not just the existence of puzzles like that that makes PCP so difficult. The proof (by reduction) that PCP is uncomputable implies that there is no way to look at a collection of dominoes and compute an upper bound on the number of dominoes needed in a solution. Sometimes, a small number of dominoes has a very long solution.