The undecidable problems seen so far all talk about Turing machines: whether they halt, whether they accept, what language they recognize. The Post correspondence problem (PCP) is different: it is a combinatorial puzzle about strings that anyone can grasp in a minute, and it mentions no machine at all. Yet it is undecidable. Precisely because it looks so "innocent", it is a valuable tool for proving the undecidability of problems about grammars, languages and rewriting systems.
The puzzle
An instance of PCP is a finite set of dominoes. Each domino has one string on top and one on the bottom. Dominoes may be used as many times as you like, in any order. A solution (or match) is a non-empty sequence of dominoes such that concatenating the top strings gives exactly the same string as concatenating the bottom ones.
The problem asks: given an instance, does a solution exist?
A solvable instance
Consider four dominoes, written as top/bottom:
| Domino | Top | Bottom |
|---|---|---|
| 1 | b | ca |
| 2 | a | ab |
| 3 | ca | a |
| 4 | abc | c |
The sequence 2, 1, 3, 2, 4 is a solution. Top: a · b · ca · a · abc = abcaaabc. Bottom: ab · ca · a · ab · c = abcaaabc. The two strings coincide.
An instance with no solution
Now take the dominoes abc/ab, ca/a, acc/ba. On every domino the top string is longer than the bottom one. Any sequence therefore produces a top row strictly longer than the bottom one, and the two can never coincide. No solution.
This case is spotted at once, but in general there is no mechanical criterion that always works.
The statement
The language PCP = {⟨P⟩ : P is an instance of the Post correspondence problem that has a solution} is undecidable.
It is, however, recognizable: try every sequence of dominoes in order of increasing length and accept if one works. If a solution exists, it will eventually be found; if it does not, the search never ends.
The idea of the proof
The proof reduces A_TM to PCP. The key ingredient is the computation history: the sequence of configurations C₁, C₂, …, Cₖ that a machine M goes through on input w, written one after another and separated by a # symbol.
Given ⟨M, w⟩, we build a set of dominoes designed so that the only way to obtain a solution is to write out an accepting computation history of M on w.
- Starting domino: just # on top, #C₁# on the bottom, where C₁ is the initial configuration. The bottom row starts one configuration ahead.
- Transition dominoes: for each transition of M, a domino with a piece of configuration on top and the corresponding piece after one step on the bottom. For example, if δ(q, a) = (r, b, R), the domino has qa on top and br on the bottom.
- Copy dominoes: for each tape symbol, a domino with the same symbol above and below, to copy the parts of a configuration that do not change.
- Closing dominoes: once the accept state appears, dominoes that let the remaining symbols be "consumed" until the two rows even out.
The mechanism is this: the top row is always chasing the bottom one. To catch up, whoever solves the puzzle is forced to transcribe the current configuration on top, and the dominoes force them to write the next configuration on the bottom. The rows can only even out if the computation reaches the accept state. So the instance has a solution if and only if M accepts w.
There are technical details, such as forcing the first domino to be the starting one (via an intermediate variant, the modified PCP), but that is the whole idea.
Consequences for grammars
PCP is the starting point for many results about context-free grammars. Given an instance with dominoes t₁, …, tₙ, build two grammars:
- G_A generates strings of the form "top of tᵢ₁ … top of tᵢₖ" followed by a marker of the indices iₖ … i₁;
- G_B does the same with the bottom strings.
A string generated by both corresponds exactly to a solution. Among other results, it follows that:
- it is undecidable whether two context-free grammars generate languages with a non-empty intersection;
- it is undecidable whether a context-free grammar is ambiguous (take the grammar that is the union of G_A and G_B: a string with two derivations corresponds to a solution).
This is why no parser tool solves them in general.
Decidable variants
Not every version is undecidable. PCP over a one-symbol alphabet is decidable, because only string lengths matter and the problem becomes arithmetic. The case with just two dominoes is decidable too. Bounding the length of the sequence sought makes the problem decidable but moves it into complexity territory: the bounded version is NP-complete.
In short
- PCP asks whether a sequence of dominoes produces the same string on top and on the bottom.
- It is recognizable, because every sequence can be tried, but not decidable.
- The proof builds dominoes that force you to write an accepting computation history.
- PCP yields the undecidability of ambiguity and of intersection for context-free grammars.
- With a unary alphabet or with two dominoes the problem becomes decidable.
