Chapter 33 of 34

Post Correspondence Problem

Imagine a box of dominoes. Each domino has a string written on its top half and another string on its bottom half. You may pick dominoes in any order, use each one as many times as you like, and lay them in a row. You win if the string you read along the top is exactly the same as the string along the bottom. Sounds like a puzzle for children, and for some sets of dominoes it is. But there is no algorithm that can tell, for every set of dominoes, whether a winning row exists.

This puzzle is the Post Correspondence Problem (PCP), introduced by Emil Post in 1946. It matters because it has nothing to do with Turing machines on the surface: it is about plain strings. That makes it the perfect starting point for proving that questions about grammars (ambiguity, equivalence, intersection) are undecidable.

An instance of PCP is two lists of non-empty strings over an alphabet Σ, of the same length k: A = (w1, …, wk) and B = (x1, …, xk). A solution is a non-empty sequence of indices i1, i2, …, im (each between 1 and k, repeats allowed) such that wi1wi2…wim = xi1xi2…xim. PCP asks whether a given instance has a solution. PCP is undecidable.

In domino language, pair i is the domino with wi on top and xi on the bottom, written [wi / xi]. This chapter builds on Halting Problem & Undecidability and Reductions & Rice's Theorem. Every instance, solution and "no solution" claim below was checked with a small brute-force search program.


Solving an Instance by Hand

Take this instance over Σ = {a, b}:

Domino i

Top wi

Bottom xi

1

a

aba

2

aa

ba

3

ab

a

The key idea for searching by hand: at every moment, one of the two strings is a prefix of the other (otherwise they already disagree somewhere, and adding more dominoes cannot fix that). The extra part of the longer string is called the overhang, and the next domino must "pay it off".

Step 1: which domino can start?

  • Domino 1: top "a", bottom "aba". "a" is a prefix of "aba". Possible; the bottom is ahead by "ba".

  • Domino 2: top "aa", bottom "ba". They differ in the first letter. Impossible.

  • Domino 3: top "ab", bottom "a". Possible; the top is ahead by "b".

Step 2: follow each branch

Branch starting with 1: the bottom is ahead by "ba", so the next top must begin with b. All tops (a, aa, ab) begin with a. Dead end. So every solution starts with domino 3.

Branch starting with 3: the top is ahead by "b", so the next bottom must start with b. Only domino 2 (bottom "ba") works. Continuing like this:

Sequence

Top string

Bottom string

Overhang

Comment

3

ab

a

top ahead by b

next bottom must start with b → only 2

3, 2

abaa

aba

top ahead by a

next bottom must start with a → 1 or 3

3, 2, 1

abaaa

abaaba

mismatch at position 5 (a vs b)

dead end

3, 2, 3

abaaab

abaa

top ahead by ab

next bottom must start with a → 1 or 3

3, 2, 3, 1

abaaaba

abaaaba

none

Match: a solution!

Check it by laying out the dominoes:

Domino :   3      2      3      1
Top    :   ab  |  aa  |  ab  |  a       = abaaaba
Bottom :   a   |  ba  |  a   |  aba     = abaaaba

So 3, 2, 3, 1 is a solution, and a search of all sequences up to length 9 confirms it is the shortest one. Once you have one solution you have infinitely many: repeating it (3, 2, 3, 1, 3, 2, 3, 1) is also a solution, because both rows simply double.

Why we can't just keep searching

The hand method is a search that keeps the overhang. When a solution exists, a breadth-first search through sequences of length 1, 2, 3, … will find it. When none exists, the search may go on forever, because overhangs can keep growing without the branches dying. This is exactly the RE-but-not-recursive behaviour from the halting problem:

  • PCP is recursively enumerable: try all index sequences in order of length and accept when one matches.

  • PCP is not recursive (proved below), so its complement ("no solution exists") is not RE.


Proving That an Instance Has No Solution

Undecidability says no single method works for all instances, but many particular instances can be settled with a simple argument. These are the arguments exam questions expect.

Argument

Example instance

Why no solution

Length: every top is longer than its bottom (or every top shorter)

[aab / aa], [ba / b]

Each domino adds more letters on top than on the bottom, so after any non-empty sequence the top is strictly longer.

Counting a letter: every domino has fewer b's on top than on the bottom

[ab / abb], [ba / bba]

Each domino adds 1 b on top and 2 on the bottom. Any solution would need equal b-counts. Impossible.

First domino: no domino has top and bottom where one is a prefix of the other

[ab / ba], [b / a]

The first domino already creates a mismatch in the first letter.

Last domino: no domino where one string is a suffix of the other

[ab / a], [b / ba]

The two rows must end with the same letters, so the last domino must have one string as a suffix of the other. Here "ab" ends in b but "a" ends in a, and "b" ends in b but "ba" ends in a. A start is possible (ab / a), but no row can ever be closed.

Dead-end search: every branch dies

Domino 1 of our example as a forced start (see MPCP below)

The search tree is finite and every leaf is a mismatch.


Modified PCP (MPCP)

The undecidability proof goes through a variant where the solution must start with the first domino.

Modified PCP (MPCP): given lists A and B as before, is there a solution i1, …, im with i1 = 1?

The two problems really are different. In our example, if domino 1 = [a / aba] is the forced first domino, the bottom is ahead by "ba" and no top begins with b, so the MPCP instance has no solution, although the PCP instance does (3, 2, 3, 1). If we reorder the list so that [ab / a] is first, the MPCP instance has the solution starting with it.

MPCP reduces to PCP

To turn an MPCP instance into a PCP instance with the same answer, use a new symbol * and an end marker $ that are not in Σ. For a string u = u1u2…un, write

*u   =  * u1 * u2 * ... * un        (star BEFORE each symbol)
u*   =  u1 * u2 * ... * un *        (star AFTER each symbol)
*u*  =  * u1 * u2 * ... * un *      (both)

The new PCP instance has:

  • for every domino [t / b] of the MPCP instance, a domino [*t / b*];

  • one special domino [*t1 / *b1*] built from the first domino;

  • an end domino [*$ / $].

Now every ordinary domino's bottom starts with a real symbol while its top starts with *, so the only domino that can start a solution is the special one (both its strings begin with *). The stars interleave so that the rows can only match if the original dominoes matched, and the end domino absorbs the one extra star at the end. Applied to our instance with [ab / a] forced first, the program found the PCP solution:

special [*a*b / *a*], then [*a*a / b*a*], [*a*b / a*], [*a / a*b*a*], end [*$ / $]
Top    : *a*b *a*a *a*b *a *$  = *a*b*a*a*a*b*a*$
Bottom : *a*  b*a* a*   a*b*a* $ = *a*b*a*a*a*b*a*$

Removing the stars and the end marker gives back the MPCP solution 3, 2, 3, 1. With [a / aba] forced first instead, the converted instance has no solution, as it should.


Why PCP Is Undecidable (Proof Sketch)

The proof shows ATM ≤m MPCP ≤m PCP. Since ATM is undecidable, so is PCP. The idea of the first step is beautiful: the dominoes are designed so that the only way to make the rows match is to write out an accepting computation history of M on w.

A configuration of M (tape contents with the state written just before the scanned symbol, e.g. 1q301) is a string, and a computation is a sequence of configurations separated by #:

#  q0 w1 w2 ... wn  #  C1  #  C2  #  ...  #  (accepting configuration)  #

Given ⟨M, w⟩ we build these kinds of dominoes (following Sipser's construction):

Kind

Domino(es)

Purpose

Start (forced first)

[# / #q0w1…wn#]

Puts the start configuration on the bottom; the bottom is now one configuration ahead.

Right move δ(q, a) = (r, b, R)

[qa / br]

Copying the head region of the current configuration (top) forces the next configuration (bottom).

Left move δ(q, a) = (r, b, L)

[cqa / rcb] for every tape symbol c

Same, for a left move.

Copy

[a / a] for every tape symbol a

Copies the unchanged parts of the tape.

Separators

[# / #] and [# / ␣#]

End a configuration; the second adds a blank when the head reaches the right end.

Accept clean-up

[a qacc / qacc] and [qacc a / qacc]

Once accepting, "eat" tape symbols one at a time so the top can catch up.

Finish

[qacc## / #]

Closes the match when only the state is left.

How it works: the top always lags one configuration behind the bottom. To pay off the overhang (configuration Ci on the bottom), we must place dominoes whose tops spell Ci; their bottoms then spell exactly Ci+1, the next configuration of M. So the bottom keeps running ahead, step by step, simulating M. The rows can only become equal after the accepting state appears and the clean-up dominoes shrink the configuration away. Hence the MPCP instance has a match if and only if M accepts w. The star construction above then gives a PCP instance. (Some technical details, like the head trying to move off the left end, are handled with small modifications.)

Since the alphabet can be encoded in binary (replace each symbol by a fixed-length binary code), PCP is undecidable even over the alphabet {0, 1}.


Decidable Special Cases

Restriction

Decidable?

Reason / source

One-letter alphabet Σ = {a}

Yes

Only lengths matter. Let di = |wi| − |xi|. A solution exists iff some di = 0, or some di > 0 and some dj < 0 (use domino i |dj| times and domino j di times). We tested this rule against brute-force search on thousands of random unary instances.

Only k = 1 domino

Yes

A solution exists iff w1 = x1.

k = 2 dominoes

Yes

Ehrenfeucht, Karhumäki and Rozenberg (1982).

k = 3 or 4 dominoes

Open

Not known.

k ≥ 5 dominoes

No

Neary (2015), improving the earlier bound of 7.

Solution length at most a given m

Yes

Finitely many sequences to try (this bounded version is NP-complete).

General PCP (any k, any alphabet with ≥ 2 symbols)

No

Post (1946).


Using PCP: Undecidable Problems About Grammars

PCP is the bridge from Turing machines to context-free grammars. Given an instance with dominoes [w1 / x1], …, [wk / xk], pick k new terminal symbols 1, 2, …, k (index symbols) and build two grammars:

G_A :  A -> w1 A 1 | w2 A 2 | ... | wk A k | w1 1 | w2 2 | ... | wk k
G_B :  B -> x1 B 1 | x2 B 2 | ... | xk B k | x1 1 | x2 2 | ... | xk k

GA generates exactly the strings wi1…wim im…i1: a top row followed by the reversed index sequence that produced it. The index tail records which dominoes were used, so each string of L(GA) has exactly one derivation. The same holds for GB with bottom rows. Therefore:

L(GA) ∩ L(GB) ≠ ∅ if and only if the PCP instance has a solution.

With our instance, the solution 3, 2, 3, 1 gives the string abaaaba1323 in both languages:

G_A:  A => ab A 3 => ab aa A 23 => ab aa ab A 323 => ab aa ab a 1323  = abaaaba1323
G_B:  B => a  B 3 => a  ba B 23 => a  ba a  B 323 => a  ba a  aba 1323 = abaaaba1323

From this one construction several classic results follow:

  1. Ambiguity of CFGs is undecidable. Combine the two grammars: S → A | B. A string has two parse trees exactly when it is in both L(GA) and L(GB) (each part on its own is unambiguous). So G is ambiguous ⟺ the PCP instance has a solution. Our program confirmed that, among all strings from up to 5 dominoes, abaaaba1323 is the only one derivable from both A and B.

  2. Is L(G1) ∩ L(G2) = ∅? is undecidable for CFGs, by the boxed statement. In fact L(GA) and L(GB) are deterministic CFLs, so it is undecidable even for DCFLs.

  3. Is L(G) = Σ*? is undecidable. The complement of L(GA) is context-free (it is a DCFL), and so is the complement of L(GB); their union is a CFL that equals Σ* exactly when L(GA) ∩ L(GB) = ∅.

  4. Equivalence and containment of CFGs are undecidable: universality is the special case "is L(G) = L(Gall)?" where Gall generates Σ*.

These are the "U" entries for CFLs in the decidability table of Reductions & Rice's Theorem.


Common Mistakes

  • Thinking each domino may be used only once. Repeats are allowed, and the order is free. Only the sequence must be non-empty.

  • Matching the rows domino by domino. The individual tops and bottoms need not be equal; only the full concatenated strings must be.

  • Reading the indices in the grammar forward. In GA, the index symbols come out in reverse order (the last domino's index is next to the strings).

  • "PCP is undecidable, so no instance can be solved." Many instances are easy. Undecidability means no single algorithm settles every instance.

  • "PCP is not RE." PCP is RE (search all sequences); its complement is not RE.

  • Confusing PCP and MPCP. They differ on individual instances (our example), but both are undecidable.

  • Forgetting the alphabet condition. Over a one-letter alphabet PCP is decidable; two letters already make it undecidable.


GATE and Interview Questions

Q1. Find a solution to the PCP instance [a / aa], [bb / b], [aa / abb].

1, 3, 2, 2. Top: a + aa + bb + bb = aaabbbb. Bottom: aa + abb + b + b = aaabbbb. (How to find it: domino 3 cannot start, since aa and abb differ in the second letter. Starting with domino 2 leaves the top ahead by "b"; only domino 2 has a bottom starting with b, and using it again just makes the top further ahead, so that branch never closes. Starting with domino 1 leaves the bottom ahead by "a"; domino 3 then gives top aaa, bottom aaabb, and two copies of domino 2 pay off the "bb".)

Q2. Does the instance [ab / abb], [ba / bba] have a solution?

No. Every domino has one b on top and two on the bottom, so after n dominoes the top has n b's and the bottom 2n. They can never be equal for n ≥ 1.

Q3. PCP is (a) decidable, (b) RE but not recursive, (c) not RE?

(b). A search over all sequences finds a solution when one exists; the reduction from ATM shows no algorithm decides it.

Q4. Is PCP over the one-letter alphabet {a} decidable? Decide the instance [aaa / a], [a / aaa].

Yes, it is decidable: only lengths matter. Here d1 = +2 and d2 = −2, so using each domino once works: top aaaa, bottom aaaa. The solution is 1, 2.

Q5. Which of these are undecidable for CFGs: (i) membership, (ii) emptiness, (iii) ambiguity, (iv) L(G1) ∩ L(G2) = ∅?

(iii) and (iv), both by reduction from PCP. Membership (CYK) and emptiness (check whether the start symbol generates a terminal string) are decidable.

Q6. In the reduction from ATM to MPCP, why is the bottom row always "one configuration ahead"?

The forced first domino [# / #q0w#] puts the start configuration only on the bottom. To match it, the top must spell that configuration, and the transition and copy dominoes then write the next configuration on the bottom. The only way to close the gap is to reach the accepting state and use the clean-up dominoes, so a match exists exactly when M accepts w.

Q7. If an instance has a solution, how many solutions does it have?

Infinitely many. Any solution can be repeated any number of times (s, s, s, …) and still match.


Summary

  • A PCP instance is a list of dominoes [wi / xi]; a solution is a non-empty sequence (repeats allowed) whose top and bottom rows are equal.

  • Search by hand by tracking the overhang; length, counting, first-domino and last-domino arguments prove particular instances have no solution.

  • PCP is RE but undecidable; its complement is not RE.

  • MPCP forces the first domino; ATM ≤m MPCP (dominoes spell an accepting computation history) and MPCP ≤m PCP (the star trick).

  • Decidable cases: unary alphabet, k ≤ 2 dominoes, bounded solution length. Undecidable already for k ≥ 5 and for a binary alphabet.

  • Via the grammars GA, GB: ambiguity, intersection emptiness, universality and equivalence of CFGs are undecidable.

PCP turns "does this machine accept?" into "can these dominoes match?", a question about plain strings. That is why it is the standard tool for proving grammar problems undecidable.