Why Is the Post Correspondence Problem Undecidable?

The Post Correspondence Problem is a foundational example of an undecidable problem in classical computing because it demonstrates that even a simple string-matching puzzle can capture the full power of a Turing machine. Introduced by Emil Post in 1946, the problem asks whether a finite set of domino-like string pairs can be arranged in a sequence so that the concatenated top strings match the concatenated bottom strings. Despite its elementary formulation, no general algorithm can decide whether a solution exists for every possible input.

What Is the Post Correspondence Problem?

Formally, an instance of the Post Correspondence Problem consists of a finite list of pairs of non-empty strings over an alphabet \(\Sigma\):

\[(t_1, b_1), (t_2, b_2), \dots, (t_k, b_k)\]

A solution is a non-empty finite sequence of indices \(i_1, i_2, \dots, i_n\) (with repetition allowed) such that:

\[t_{i_1} t_{i_2} \cdots t_{i_n} = b_{i_1} b_{i_2} \cdots b_{i_n}\]

Because there is no upper bound on the length \(n\) of the sequence, a brute-force search can confirm a solution if one exists, but it may run forever if no solution exists.

How Does It Prove Undecidability?

The undecidability of the Post Correspondence Problem is established by reducing the halting problem—or more specifically, the acceptance problem \(A_{\text{TM}}\) for Turing machines—to PCP. Given a Turing machine \(M\) and an input string \(w\), one can construct a set of PCP pairs that simulate the step-by-step computation history of \(M\) on \(w\).

In this construction:

  • The top and bottom strings represent successive configurations of the Turing machine, separated by a delimiter symbol.
  • The bottom string is designed to lag one computational step behind the top string.
  • The two strings can only catch up and become identical if the Turing machine reaches an accepting state.

If an algorithm existed to decide PCP, it could be used to decide whether \(M\) accepts \(w\), which is known to be impossible.

Why Is It Foundational in Classical Computing?

The Post Correspondence Problem is significant because it bridges the gap between abstract models of computation and concrete, non-machine-based problems. While the halting problem explicitly references Turing machines and programs, PCP is purely combinatorial and requires no concept of states, tapes, or instructions.

This simplicity makes PCP a standard starting point for proving the undecidability of other problems in computer science, including:

  • Formal language theory: Determining whether a context-free grammar is ambiguous, or whether the intersection of two context-free languages is empty.
  • Database theory: Analyzing certain query containment and equivalence problems.
  • Software verification: Establishing limits on automated reasoning about program properties.

By showing that undecidability arises naturally in basic symbolic manipulation, the Post Correspondence Problem underscores the fundamental boundaries of algorithmic computation.