The Post Correspondence Problem

A fascinating undecidable puzzle with important applications

What is the Post Correspondence Problem?

The Post Correspondence Problem (PCP) was introduced by Emil Post in 1946. It's a deceptively simple puzzle that turns out to be undecidable.

Definition:

Given two lists of strings X = (x₁, x₂, ..., xₙ) and Y = (y₁, y₂, ..., yₙ) over an alphabet Σ, determine whether there exists a sequence of indices i₁, i₂, ..., iₘ such that:

xi₁xi₂...xiₘ = yi₁yi₂...yiₘ

Notes:

  • The indices i₁, i₂, ..., iₘ need not be distinct (they can be repeated)
  • m may be greater than n (the sequence can be longer than the number of pairs)
  • If there exists a solution, there exist infinitely many solutions
🧩

The PCP can be thought of as a game of dominoes, where each domino has a string on the top half and a string on the bottom half. The goal is to arrange the dominoes (possibly using multiple copies of each) to form the same string on the top and bottom.

Undecidability of PCP

Theorem:

The Post Correspondence Problem over an alphabet Σ where |Σ| ≥ 2 is undecidable.

This means there is no algorithm that can determine, for any arbitrary instance of PCP with at least two symbols in the alphabet, whether a solution exists.

Proof Idea:

The undecidability of PCP is proven by reducing the Halting Problem to PCP. This means that if we could solve PCP, we could also solve the Halting Problem, which we know is impossible.

The reduction works by encoding the computation history of a Turing machine as strings in a PCP instance. A solution to the PCP exists if and only if the Turing machine halts.

Special Case:

Interestingly, if the alphabet has only one symbol (Σ = a), then PCP is decidable. This is because with only one symbol, the strings can be compared based solely on their lengths.

Key Takeaways

  • ✓

    The Post Correspondence Problem is undecidable for alphabets with at least two symbols

  • ✓

    PCP can be visualized as a domino game where the goal is to create matching strings on top and bottom

  • ✓

    PCP is used to prove the undecidability of many problems in formal language theory