Post-Correspondence Problem (PCP): A Structured “Short Note” for Learning

The Post Correspondence Problem (PCP) is a classic question in theoretical computer science used to demonstrate limits of computation. Given a finite set of “dominoes,” each with an upper string and a lower string over some alphabet, PCP asks whether there exists a nonempty sequence of domino indices such that the concatenation of upper strings equals the concatenation of lower strings.

Formally, an instance of PCP consists of pairs of strings $(u_1,v_1),(u_2,v_2),\dots,(u_n,v_n)$ over an alphabet $\Sigma$. The problem asks whether there exists a length-$k$ sequence of indices $(i_1,i_2,\dots,i_k)\quad\text{with }k\ge 1$ such that $u_{i_1}u_{i_2}\cdots u_{i_k}=v_{i_1}v_{i_2}\cdots v_{i_k}.$

This simple-looking “string matching by concatenation” problem is undecidable: there is no general algorithm that decides PCP for every possible domino set. The undecidability result is attributed to Emil Post (and PCP is widely presented as a foundational stepping stone toward later undecidability theorems).2

Key learning terms:

• instance: the domino list
• concatenation: $u_{i_1}\cdots u_{i_k}$
• solution (witness): $(i_1,\dots,i_k)$

Mermaid view of what PCP is trying to “align”:

Why PCP matters (high-level intuition)

PCP acts as a “universal template” for encoding computations. The undecidability proof shows that the question “does there exist a matching concatenation?” can simulate arbitrary computation steps. In other words, a hypothetical PCP-decider would enable solving other problems known to be undecidable (e.g., certain halting-type problems). This is why PCP is used as a standard reduction target in computability theory.2

reduction is the key idea: prove PCP undecidable by reducing from a known undecidable problem. Once you can embed computations into domino concatenations, any algorithm for PCP would indirectly solve the embedded source problem—impossible if the source is undecidable.

Example of a PCP “matching sequence” (concrete computation)

Suppose the instance includes dominoes: $(u_1,v_1)=("a","a"),\quad (u_2,v_2)=("ab","b").$ Consider the sequence $(1,2)$. Then:

• Top concatenation: $u_1u_2 = "a" \cdot "ab" = "aab"$
• Bottom concatenation: $v_1v_2 = "a" \cdot "b" = "ab"$

These are not equal, so $(1,2)$ is not a solution.

If instead there existed some sequence $(i_1,\dots,i_k)$ with equal concatenations, that sequence would be a witness for a YES answer.

This is exactly the behavior the PCP decision question asks about, for arbitrary domino sets.2

Modified variants (brief context)

A common closely related variant is the Modified Post Correspondence Problem (MPCP) (sometimes called “modified PCP”). MPCP changes boundary conditions (e.g., fixed first/last domino constraints) but remains central in reductions and undecidability arguments. While different texts define MPCP constraints slightly differently, the overall theme is the same: enforce structured matching while retaining undecidability.

boundary condition: what MPCP alters relative to PCP.