Post Correspondence Problem

The Post Correspondence Problem (PCP) is an undecidability result in Computation Theory, introduced by Emil Post in 1946. Given a finite collection of domino-like tiles, each bearing a string on its top and bottom, the problem asks whether any sequence of tiles (repetitions allowed) can be arranged so that the concatenation of top strings matches the concatenation of bottom strings. No Turing Machine can decide this for all inputs.

The PCP is significant not for its direct applications but for its use as a reduction target: proving that new problems are undecidable is often accomplished by showing that if you could solve the new problem, you could solve the PCP, which you cannot. This makes it a workhorse of computability theory — an anchor for the web of undecidability results that extends from the Halting Problem outward.

The problem also illustrates a general point: undecidability is not exotic. It appears everywhere formal languages and rewriting systems meet. Formal language theory is riddled with undecidable questions about what strings a grammar can generate. The boundaries of the decidable are narrow in ways that practitioners routinely ignore.