JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

The Post Correspondence Problem

A puzzle about matching dominoes turns out to be undecidable — and because it is, a whole gallery of natural questions about grammars collapses too. This is the workhorse undecidable problem you reduce FROM when the halting problem is too clumsy to translate.

A puzzle made of dominoes

By now you have the reduction habit: to show a new problem is impossible, you find a known-impossible one and translate it into the new one, always being careful about which way the arrow points. So far the known-impossible problem has been the halting problem (or its cousin A_TM). But translating 'does this Turing machine halt?' into, say, a question about grammars is awkward — you have to encode an entire machine's behaviour into a grammar. It is much easier if we first launder the halting problem into a tidier, more combinatorial form. That tidier form is the Post correspondence problem, or PCP, and it looks nothing like a machine at all. It looks like a child's puzzle.

Here is the puzzle. You are given a finite collection of dominoes, where each domino has a string written on its top and another string on its bottom — both over some alphabet Sigma (the finite pool of symbols you are allowed to use). You have an unlimited supply of each kind of domino. Your job is to line up a sequence of them, repeats allowed, so that reading all the tops left to right spells the exact same string as reading all the bottoms left to right. Such a sequence is called a match. The question PCP asks is simply: for this particular collection of dominoes, does any match exist at all?

Dominoes:   d1 = [ b  / ca ]   d2 = [ a  / ab ]   d3 = [ ca / a  ]   d4 = [ abc / c ]
            (top / bottom)

Try the sequence  d2  d1  d3  d3  d4 :

   tops:    a   b    ca   ca   abc      ->  concatenated:  a b ca ca abc  =  abcacaabc
   bottoms: ab  ca   a    a    c        ->  concatenated:  ab ca a a c    =  abcacaabc

           MATCH:  top string == bottom string == "abcacaabc"
One concrete PCP instance with a match. Notice the tops and bottoms have different lengths per domino, so it is the cumulative running totals that must finally agree — a delicate bookkeeping game.

Why it is harder than it looks

It is tempting to think you could just try sequences in order of length: all matches of length 1, then length 2, and so on, stopping when you find one. And indeed you can — but only if a match exists. If a match does exist, this brute-force search will eventually trip over it and you can shout 'yes'. The trouble is the 'no' case. If no match exists, there is no length at which you can safely stop searching, because the very next sequence you have not yet tried might have been the one. The search runs forever without ever earning the right to answer 'no'. This is the exact signature of a problem that is recognizable but not decidable — recognizable because the 'yes' instances eventually announce themselves, undecidable because the 'no' instances never do.

Where does the undecidability come from? It is smuggled in by a mapping reduction FROM the halting problem (technically from A_TM, the acceptance problem). The construction is ingenious: given a machine M and an input w, you build a set of dominoes so cleverly designed that the ONLY way to make the tops match the bottoms is to spell out, step by step, the entire sequence of configurations of M running on w — a so-called accepting computation history. The bottom row is always forced to stay exactly one configuration ahead of the top, like a story being told twice with the bottom narrator always one sentence behind, until the very last domino can close the gap only if M reaches its accepting state.

Reading the reduction the right way

Be very deliberate about the direction, because this is exactly the trap guide 1 of this rung warned about. We are reducing the halting problem TO PCP. That arrow means: 'if I had a PCP-solver, I could solve the halting problem.' The translator turns each halting question into a domino set such that M accepts w if and only if those dominoes have a match. A PCP oracle would then settle every halting question — but we proved the halting question cannot be settled. Therefore no PCP-solver exists. The undecidability flows FROM the known-hard halting problem INTO PCP, never the reverse. If you reduced PCP to the halting problem instead, you would learn only that PCP is no harder than halting — a true but useless fact that proves nothing about PCP's difficulty.

  1. Start from a problem you already KNOW is undecidable. Here: A_TM — does machine M accept input w? (proved undecidable earlier in this ladder).
  2. Build a computable translator f. Given the pair (M, w), f outputs a set of dominoes — and f itself always halts; it is just an honest construction recipe, not a solver.
  3. Prove the equivalence both ways: those dominoes have a match IF AND ONLY IF M accepts w. Yes maps to yes, no maps to no — that two-way faithfulness is what makes it a mapping reduction.
  4. Conclude by contradiction: a decider for PCP composed with f would decide A_TM. Since A_TM is undecidable, PCP must be undecidable too. The hardness has been transferred.

Why we bother: PCP kills the grammar problems

Here is the payoff. PCP is not the destination; it is a stepping stone. Now that we own a clean, machine-free undecidable problem, it becomes the ideal thing to reduce FROM whenever the target is itself combinatorial — and grammars are exactly that. A whole family of undecidable grammar problems falls out of PCP almost mechanically, because you can encode a domino set into a context-free grammar far more naturally than you could encode a Turing machine. The trick is to build two grammars (or two halves of one) — one generating all 'top' readings of domino sequences, one generating all 'bottom' readings — so that a string belongs to both languages exactly when it witnesses a PCP match.

That single idea topples several famous questions. Whether a context-free grammar is ambiguous — does some string have two different parse trees? — is undecidable, because a PCP match gives you a string derivable in two ways. Whether the intersection of two context-free languages is empty is undecidable, since a non-empty intersection IS a match. Whether a context-free grammar generates every string over its alphabet (universality) is undecidable too. None of these were obvious from staring at grammars; they all became visible only once PCP handed us the right thing to reduce from. That is the everyday role of PCP: a reusable hardness source, the undecidability gets transferred onward each time.