The Post Correspondence Problem

Introduction

Time for one of the most famous undecidable problems: the Post Correspondence Problem (PCP). Invented by Emil Post in 1946, PCP asks if you can match tiles to make top and bottom strings equal. Simple to state, but there’s no algorithm to solve it in full generality.

Problem Statement

Given two lists of non-empty strings (tiles) over some alphabet Σ:

• Top row: $x_1, x_2, \dots, x_k$
• Bottom row: $y_1, y_2, \dots, y_k$

the question is: does there exist a finite sequence of indices $i_1, i_2, \dots, i_n$ such that:

$$ x_{i_1} x_{i_2} \cdots x_{i_n} = y_{i_1} y_{i_2} \cdots y_{i_n}? $$

Example Instance

Consider tiles:

• Question: Is there a match? Try sequence (1,2,1):

  • Top: a + aba + a = aaba a = aabaa.
  • Bottom: ab + a + ab = abaab.

  Not equal. You can search, but no finite sequence works.

Proof Sketch of Undecidability

PCP is typically proved undecidable by reduction from the Halting Problem:

1. Start with a Turing machine $M$ and input $w$.
2. Build tile sets encoding configurations of $M$ on $w$.
3. Show there’s a matching sequence of tiles iff $M$ halts on $w$.

The construction is intricate and uses marker symbols to align successive configurations.

Why It Matters

• Language Theory: PCP is a canonical example of an undecidable problem about strings.
• Reductions: Many other problems reduce from PCP, especially in formal language and combinatorics.
• Boundary of Decidability: Highlights that even simple combinatorial puzzles can encode Turing computations.

Wrap-Up

PCP is our first major string-based undecidable problem. Next up: Rice’s Theorem, a powerful generalization that shows why almost any nontrivial property of program behavior is undecidable.