the Post correspondence problem
/ post (as in the surname) /
Picture a box of special dominoes. Each domino has a top string and a bottom string, like a card with 'ab' written on top and 'a' on the bottom. You may use any domino as many times as you like and line up a sequence of them. You win if, reading all the tops left to right gives the very same string as reading all the bottoms. The Post correspondence problem (PCP) asks the deceptively simple question: for a given box of dominoes, does any winning sequence exist?
Formally an instance is a finite list of pairs (t1, b1), ..., (tk, bk) of strings over some alphabet. A solution is a nonempty sequence of indices i1, i2, ..., in (repeats allowed) such that the concatenation t_{i1} t_{i2} ... t_{in} equals the concatenation b_{i1} b_{i2} ... b_{in}. For instance with dominoes (a, ab), (b, ca), (ca, a), (abc, c), the sequence 1, 2, 3, 1, 4 makes top and bottom both spell abcaaabc, so it is a solution. The hard part is that there is no bound on how long a winning sequence might need to be, and chasing longer and longer attempts never lets you conclude 'no solution exists'. PCP is undecidable: no algorithm can determine, for every box of dominoes, whether a match is possible.
Why care about a domino puzzle? Because PCP is the great lever for proving GRAMMAR problems undecidable. The undecidability of PCP is established by a reduction from the acceptance/halting problem (a Turing machine's computation history can be encoded as a domino-matching task), and then PCP is reduced onward to context-free grammar questions. This chain is exactly how we learn that grammar ambiguity is undecidable, that grammar equivalence is undecidable, that whether a grammar generates every string (universality) is undecidable, and that whether two context-free languages intersect is undecidable. PCP sits in the middle as the convenient, combinatorial hinge between machine undecidability and grammar undecidability. A note of nuance: PCP over a one-symbol alphabet, and PCP limited to very few dominoes, are decidable; undecidability needs enough room.
Dominoes (top/bottom): (b, ca), (a, ab), (ca, a), (abc, c). Try sequence 2, 1, 3, 2, 4: tops give a b ca a abc = abcaaabc; bottoms give ab ca a ab c = abcaaabc. They match, so this instance has a solution. With a different box, deciding whether ANY such matching sequence exists is, in general, impossible.
Line up dominoes so the top string and bottom string spell the same word; PCP asks if that is ever possible.
PCP is undecidable in general, but not always: over a single-symbol alphabet it is decidable, and instances with very few dominoes are decidable. Undecidability is about the general problem with enough symbols and tiles.