The Post Correspondence Problem, and the Undecidable Problems of Grammars
Chapter Seventy-Seven
Syllabus topic Module 2, "Turing Machines: Introduction to Unsolvable Problems"
Pages 384 to 388 of 438
In one line
Given a list of pairs of strings, can some sequence of them be chosen so that the tops and the bottoms spell the same thing? No method decides it.
In the wording a student can write in an examination: an instance of the Post correspondence problem is a finite list of pairs of non empty strings over an alphabet. A solution is a non empty sequence of indices, with repetition allowed, such that concatenating the first components in that order gives the same string as concatenating the second components. The problem of determining whether an arbitrary instance has a solution is undecidable.
The problem, as Post posed it
Post's 1946 paper is "A Variant of a Recursively Unsolvable Problem", Bulletin of the American Mathematical Society volume 52 (1946), pages 264 to 268. It opens by defining strings over two letters and then poses what it calls the correspondence decision problem: whether, for an arbitrary finite set of pairs of corresponding non null strings, there is a solution matching the two concatenations. The paper then proves that in its full generality the problem is recursively unsolvable.
Why it looks like a puzzle and is not. It has the shape of a game with dominoes and it is undecidable, which is why it is worth including: undecidability is not confined to questions about machines. And once a problem is undecidable it can be used to prove others undecidable, and Post's is the one that reaches the grammars.
An instance, and a solution
An instance is a list of pairs. Write them as a table, tops in one row and bottoms in the other.
Post's own example, from his paper.
| Pair | 1 | 2 | 3 |
|---|---|---|---|
| top | bb | ab | b |
| bottom | b | ba | bb |
Is there a solution? Take the sequence of indices 1, 2, 2, 3.
| Pieces chosen | Joined | |
|---|---|---|
| tops | bb, ab, ab, b | bbababb |
| bottoms | b, ba, ba, bb | bbababb |
The two agree, both being bbababb, seven symbols. So this instance has a solution, and Post's paper gives exactly this one.
Notice the asymmetry of the evidence. Producing the sequence 1, 2, 2, 3 settles the yes case completely, in one line, and anybody can check it. Settling a no case needs an argument about every possible sequence, of which there are infinitely many. That asymmetry is the shape of undecidability, and it is the same shape chapter 44 noted for ambiguity.
Two cases where there is no solution, and both are Post's
His paper gives two sufficient conditions, and each is worth knowing because an examination may set an instance satisfying one.
If every top is longer than its bottom, there is no solution: the joined tops would be longer than the joined bottoms, so they cannot be equal.
The Post Correspondence Problem, and the Undecidable Problems of Grammars
If every top begins with a different letter from its bottom, there is no solution: the first pair chosen would make the two strings differ at their very first symbol.
| Pair | 1 | 2 |
|---|---|---|
| top | ab | b |
| bottom | b | a |
Here the first pair has a longer top than bottom, and the second begins differently from its bottom, so a sequence starting with either pair is already lost.
These conditions are sufficient and not necessary. An instance failing both tests may still have no solution, and deciding that in general is exactly what cannot be done.
The modified problem
For the reductions it is convenient to require the solution to begin with pair 1. That is the modified Post correspondence problem.
It is also undecidable, and the two are interreducible: the modified problem is a special case, and the general one reduces to it by padding the strings with a marker symbol so that only one pair can begin a solution.
The reductions below use the modified form, which is standard.
Why it is undecidable
The full proof is a reduction from the halting problem and it is long. What it does is worth knowing even though MU does not set the details.
The idea. Given a machine M and an input w, build an instance whose pairs are made from M's moves, arranged so that the only way to make the tops and the bottoms agree is to spell out an accepting computation of M on w. The bottom row runs one configuration ahead of the top row, and each pair either copies a symbol across unchanged or applies one move of M, so a matching sequence is exactly a valid run.
Then a solution exists exactly when M accepts w, and a decider for the correspondence problem would decide acceptance, which chapter 75 proved impossible.
What to take from it. It is the same trick as chapter 59's triple: encode a computation as a combinatorial object, so that a question about the object becomes a question about the computation.
What it proves about grammars
This is why the chapter is in the syllabus, and it closes chapter 51's table.
The construction. From an instance with pairs (x1, y1) to (xn, yn), and fresh symbols a1 to an not in the alphabet, build two grammars:
Gx: S -> x(i) S a(i) | x(i) a(i), one pair of productions for each i
Gy: S -> y(i) S a(i) | y(i) a(i), one pair of productions for each i
What they generate. Gx generates every string made of some tops joined, followed by the indices used, in reverse order. Gy does the same with the bottoms. So a string lies in both languages exactly when one index sequence gives the same joined string on both rows, which is exactly a solution.
The Post Correspondence Problem, and the Undecidable Problems of Grammars
L(Gx) intersect L(Gy) is non empty exactly when the instance has a solution
Four results fall out, each one line from that.
Is the intersection of two context free languages empty? Undecidable, immediately.
Is a context free grammar ambiguous? Undecidable. Combine Gx and Gy into one grammar with a new start symbol S and the two productions S to Sx and S to Sy, renaming the variables apart. A string with two derivation trees is one derivable both ways, which is one in the intersection. So the combined grammar is ambiguous exactly when the instance has a solution.
Are two context free grammars equivalent? Undecidable. The route is through complements: the complement of L(Gx) is context free, and so is the complement of L(Gy), and so is their union, and that union is everything exactly when the intersection of the two original languages is empty.
Is a context free language equal to Sigma star? Undecidable, by the same union.
And the ones that remain decidable, from chapter 51, for contrast: membership, emptiness and finiteness for a single grammar. The line is worth stating: a question about ONE grammar's strings tends to be decidable, and a question comparing TWO tends not to be.
A worked construction, small enough to read
Take the two pair instance with tops a and ab, bottoms ab and b, and fresh symbols 1 and 2.
S->a S 1 | a 1Accepts: a1, aa11, aaa111
Rejects: ε, a, 1, 1a, aa1
That is Gx for the first pair alone, written out so the shape is visible: the top string, then the rest, then the index. A full Gx has two productions per pair and generates all the sequences.
Read the shape. Every string it generates is some tops joined, then the indices of the pairs used in reverse order. The reversal is what makes the grammar context free rather than needing two counts at once: the indices come back off in the order a stack would give them, which is chapter 52's observation again.
The whole undecidability picture
| Problem | Status | Proved by |
|---|---|---|
| halting | undecidable | diagonalisation, chapter 74 |
| acceptance, blank tape, emptiness of T(M) | undecidable | reduction, chapter 75 |
| every non trivial property of T(M) | undecidable | Rice, chapter 76 |
| Post correspondence | undecidable | reduction from halting |
| emptiness of an intersection of two CFLs | undecidable | reduction from Post |
| ambiguity of a CFG | undecidable | reduction from Post |
| equivalence of two CFGs | undecidable | reduction from Post |
| membership, emptiness, finiteness for one CFG | DECIDABLE | chapter 51 |
| everything in chapter 39 about finite automata | DECIDABLE | chapter 39 |
| the Entscheidungsproblem, whether a statement of first order logic is provable | undecidable | Turing, 1936 |
The Post Correspondence Problem, and the Undecidable Problems of Grammars
The last row is where the subject began. Hilbert asked for a definite method deciding any statement of first order logic, Turing's paper of chapter 62 invented the machine in order to answer him, and the answer was no. So a first order theory can be undecidable, and the one Hilbert asked about is.
One diagonal argument at the top and everything else by reduction, which is the sentence that summarises the whole block.
Distinctions
| The general problem | The modified problem | |
|---|---|---|
| The solution | any non empty index sequence | must begin with pair 1 |
| Undecidable | yes | yes |
| Used in reductions | rarely | usually |
| A yes instance | A no instance | |
|---|---|---|
| Evidence | the index sequence, checkable in a line | an argument about infinitely many sequences |
| Semi decidable | yes, by searching sequences in order of length | no |
What it does NOT mean
It is not a puzzle with a trick. Particular instances are often easy either way; no method handles all of them.
A no answer is not always hard to see. Post's two conditions settle many instances at a glance, and they are sufficient rather than necessary.
The problem is not about machines. That is what makes it useful: it shows undecidability is not confined to self referential questions about programs, and it gives a combinatorial starting point for reductions into grammars.
The grammar results are not about Turing machines. They are about context free grammars, which chapter 51 showed are otherwise well behaved. The undecidability arrives through Post's problem rather than directly.
Undecidable does not mean useless. Parser generators decide ambiguity for restricted grammar classes and reject the rest, which is how the practical world lives with this result.
Quick revision
- An instance is a finite list of pairs of non empty strings; a solution is a non empty index sequence, repeats
allowed, making the joined tops equal the joined bottoms.
- Post 1946, Bulletin of the American Mathematical Society volume 52, pages 264 to 268.
- His own example: tops bb, ab, b and bottoms b, ba, bb, solved by 1, 2, 2, 3, both sides giving bbababb.
- Two sufficient conditions for no solution, both his: every top longer than its bottom, or every top beginning
with a different letter from its bottom.
- The modified problem requires the solution to begin with pair 1, is also undecidable, and is the one used in
reductions.
- Undecidable by a reduction from halting, in which a matching sequence is forced to spell out an accepting
computation.
- From it: emptiness of an intersection of two context free languages, ambiguity of a grammar, equivalence of two
The Post Correspondence Problem, and the Undecidable Problems of Grammars
grammars, and whether a context free language is everything.
- A question about one grammar's strings tends to be decidable; one comparing two tends not to be.
Test yourself
1. Define an instance and a solution. An instance is a finite list of pairs of non empty strings. A solution is a non empty sequence of indices, with repetition allowed, such that joining the first components in that order gives the same string as joining the second components.
2. Solve the instance with tops bb, ab, b and bottoms b, ba, bb. The sequence 1, 2, 2, 3 works: the tops give bb, ab, ab, b which is bbababb, and the bottoms give b, ba, ba, bb which is also bbababb.
3. Give two conditions under which an instance certainly has no solution. If every top is longer than its corresponding bottom, since the joined tops would then be longer; or if every top begins with a different letter from its bottom, since the very first pair chosen would make the two strings differ.
4. What are the two grammars built from an instance, and what does their intersection mean? One generating the joined tops followed by the reversed index sequence, and one doing the same with the bottoms. A string lies in both exactly when one index sequence gives the same result on both rows, so the intersection is non empty exactly when the instance has a solution.
5. Name three questions about context free grammars that this makes undecidable. Whether the intersection of two context free languages is empty; whether a grammar is ambiguous; and whether two grammars generate the same language.
6. Why is a yes instance easy to confirm and a no instance not? A yes instance has a finite witness, the index sequence, which anybody can check in a line. A no instance is a claim about infinitely many sequences and has no finite witness, so the problem is semi decidable and not decidable.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.