Post Correspondence Problem (PCP): Short Notes for Computation Theory

The Post Correspondence Problem (PCP) is a classic problem in theoretical computer science used to show the existence of undecidable problems. In PCP, we are given a finite set of “tiles,” each tile containing two strings over some alphabet. The task is to decide whether there exists a finite sequence of tile indices such that the concatenation of the top strings equals the concatenation of the bottom strings. The key result is that PCP is undecidable (more precisely, semi-decidable/recursively enumerable but not decidable).

1) Formal definition (instance, solution, decision question)

Let $\Sigma$ be an alphabet. An instance of PCP consists of $k$ pairs of strings: $\{(u_1,v_1),(u_2,v_2),\dots,(u_k,v_k)\}$ where each $u_i,v_i \in \Sigma^*$.

A solution is a finite sequence of indices $i_1,i_2,\dots,i_n \in \{1,2,\dots,k\}, \; n\ge 1$ such that $u_{i_1}u_{i_2}\cdots u_{i_n} \;=\; v_{i_1}v_{i_2}\cdots v_{i_n}.$

The decision problem asks:

Does there exist such a sequence?

Key keywords: alphabet, string concatenation, decision problem.

2) A small illustrative example (how matching works)

Suppose we use tiles over alphabet $\Sigma=\{a,b\}$:

• Tile 1: $(u_1,v_1) = (a, ab)$
• Tile 2: $(u_2,v_2) = (aba, a)$

We try to form the same final string on top and bottom by choosing a sequence of tile indices.

If we choose sequence $[1,2]$, then:

• Top: $u_1u_2 = a\cdot aba = aaba$
• Bottom: $v_1v_2 = ab\cdot a = aba$

They are not equal, so $[1,2]$ is not a solution. The idea is to search over all finite sequences and check equality.

Key keywords: tile, index sequence, equality constraint.

3) Semi-decidability (recognizing solutions)

Even though PCP is undecidable, it is recursively enumerable: we can enumerate all finite index sequences of length $1,2,3,\dots$ and check whether the resulting top and bottom strings match.

This gives a “search” algorithm:

• generate $i_1,\dots,i_n$ for increasing $n$
• compute the concatenated top string and bottom string
• accept if they match

If a solution exists, the algorithm eventually finds it; if not, it may run forever.

Key keywords: enumeration algorithm, semi-decision, nontermination.

4) Why PCP is undecidable (high-level reduction idea)

The standard proof strategy for PCP undecidability is to reduce an already-undecidable problem (commonly, the halting problem). The reduction encodes computation history into string concatenation so that:

• a valid sequence of tiles corresponds to a correct “computation trace,” and
• the equality of top and bottom strings forces consistency between successive configurations.

At a high level, PCP acts like a constraint satisfaction engine: the constructed equality forces the simulated machine steps to “line up” correctly.

Key keywords: reduction, computation encoding, undecidability.

5) Related variants and interpretations (short notes)

• PCP can be generalized or restricted (e.g., constraints on the form of tiles or special starting/ending rules).
• A common way to connect PCP to automata theory is via formal languages: PCP can be shown to generate languages/relations that are recursively enumerable but not decidable.

Key keywords: variant, formal language, recursively enumerable relation.