The Post Correspondence Problem (PCP) is undecidable

PCP: given a finite set of dominoes (top/bottom string pairs), is there a finite sequence (with repetition allowed) such that the concatenation of tops equals the concatenation of bottoms?

• Dominoes can be reused. A match sequence may use the same domino multiple times. This is what makes PCP unbounded — the search has no a-priori length cap.
• Top equals bottom over a finite alphabet. Not just same length; the actual strings must match. The reduction encodes TM transitions so that "tops match bottoms" means "transitions are valid."
• MPCP and PCP are equivalent. The "modified PCP" fixes the first domino. Reductions to it are easier; reduce MPCP to PCP with padding to handle the unrestricted-start version.

• Q1. Why is PCP undecidable but small instances solvable by hand?
  Searching for a match is unbounded — there's no polynomial-size witness in general. For small instances breadth-first search terminates; in general, the search depth can be enormous.
• Q2. How does the TM-to-PCP reduction work?
  For each TM transition δ, create a domino: top has C_i portion, bottom has C_i+1 portion. Each match-step picks a domino, concatenating both rows. A complete match corresponds to a valid computation history. Add starter dominoes for q₀w on top and finisher dominoes for q_accept to align.
• Q3. What about MPCP (modified PCP)?
  MPCP fixes the first domino in the sequence. It's also undecidable. The TM-to-PCP reduction naturally targets MPCP (the starter domino is "first"). Standard PCP is then reduced from MPCP via a padding gadget that simulates the start-domino constraint.
• Q4. Is PCP a useful tool for other undecidability proofs?
  Yes — many natural problems reduce from PCP. The "two strings must match by combinatorial choices" pattern shows up in CFL ambiguity, post canonical systems, and various tiling problems.

Sipser: §5.2, Theorem 5.15 (PCP undecidable). Lecture notes: Module 3 slide 4. Companion problems: P9 (computation histories), P10 (E_LBA).