The Post Correspondence Problem as a Reduction Source

Most undecidability proofs in textbooks pass through a single intermediate problem rather than returning to Turing machines each time. The Post correspondence problem is that intermediate. It has no machines in its statement, no states, no tapes, only pairs of strings and a requirement that a sequence of pairs line up. The absence of machine vocabulary is what makes it useful: a reduction into it can be described in the target problem’s own terms, and a reduction out of it carries the undecidability into contexts where machines would be out of place.

The problem statement and its immediate cases

An instance of PCP is a finite list of pairs of nonempty strings over an alphabet Σ:

$$(t_1, b_1), (t_2, b_2), \ldots, (t_k, b_k)$$

A match is a finite sequence of indices i₁, i₂, …, iₘ, with m ≥ 1, such that the concatenation of the top strings equals the concatenation of the bottom strings:

$$t_{i_1} t_{i_2} \cdots t_{i_m} = b_{i_1} b_{i_2} \cdots b_{i_m}$$

Indices may repeat. The decision problem asks whether any match exists.

Two facts make the problem’s shape clear. A match of length m has both sides of length equal to the sum of the lengths of the chosen strings, so a match is always a pair of equal-length words, and the search is over sequences rather than over alignments of a fixed pair of strings. And the empty sequence is excluded, because otherwise every instance would trivially match; the exclusion is what gives the problem its content.

Small instances show the range. With the single pair (a, aa), no match exists: every sequence produces a top string shorter than the bottom. With pairs (a, ab) and (b, a), a length count settles it: a sequence using p copies of the first pair and q of the second has top length p + q and bottom length 2p + q, so equality forces p = 0, and any sequence of the second pair alone gives top b^q against bottom a^q. With pairs (ab, a) and (b, ba), both pairs have equal top and bottom lengths, so no counting argument applies, and the nonempty match 1, 2 gives “abb” on both sides. Length arguments decide easy instances and nothing else, which is a first indication of where the difficulty lies.

Why a match is a computation

The reduction from acceptance builds an instance whose matches correspond exactly to accepting computations, and the encoding is worth following because it shows where the freedom in the problem statement is spent.

The construction represents a configuration of the machine as a word: the tape contents with the state symbol inserted immediately to the left of the scanned cell. A computation is then a sequence of such words, each derived from the previous by one step of the transition function. A match must produce the same sequence on both sides, offset so that the bottom side lags the top by one configuration. The dominoes are designed so that:

• One pair starts the sequence with the initial configuration on the top and a prefix of it on the bottom.
• For each transition of the machine, pairs that append the new configuration on the top while the bottom catches up to the previous one.
• Padding pairs that let either side extend past the other’s end with a neutral symbol, so that the offset can be maintained across configurations of different lengths.
• A final pair that closes the match by making the two sides equal once the accepting state appears.

The critical detail is the last one. Without a closing mechanism, a match could run forever through non-accepting configurations and never complete; the closing pair forces the accepting state to appear, and it can only be applied when that state is present on both sides. So a match exists exactly when the machine reaches an accepting configuration in finitely many steps.

The instance’s size is proportional to the machine’s description plus the input length, with a constant factor for the padding pairs. The reduction is computable, and the correspondence is exact in both directions: a match yields an accepting computation by reading off the configurations, and an accepting computation yields a match by following the same sequence of pairs.

This is the same encoding strategy used in Encoding Turing Machines and the Undecidability of Acceptance, but with the equality constraint replaced by a concatenation constraint. The replacement is what removes the machine from the statement while keeping the computational content.

Why no algorithm decides it

PCP is Σ₁-complete. Membership is recognizable: enumerate sequences of indices in order of increasing length, test each for equality of the two concatenations, and halt when one matches. The enumeration is infinite and the test is a linear comparison of words whose length grows with the sequence length, so the procedure is a semi-decision, not a decision.

Completeness follows from the reduction above: acceptance reduces to PCP, so a decider for PCP would decide acceptance. The reduction’s direction deserves emphasis. It maps an instance of acceptance to an instance of PCP, so it shows PCP at least as hard as acceptance. A reduction in the other direction would show only that PCP is no harder than acceptance, which is true of every recognizable problem and therefore uninformative.

The problem’s own diagonal proof is not available, because PCP instances are not machines and cannot be applied to themselves. This is exactly why the problem is a useful reduction source rather than a replacement for the diagonal argument: it is a fixed, machine-free target that can be reached from many starting points, and the hardness is imported from acceptance rather than proved from scratch.

The bounded variant and its use

The bounded PCP asks whether a match exists using at most n pairs, with n given in binary as part of the input. This version is decidable, by enumerating sequences of length at most n, and the enumeration has kⁿ candidates for an instance with k pairs, so the procedure is exponential in n. The problem is NP-complete: a match itself is a certificate that can be verified in time linear in its length, and the unbounded problem reduces to it by pairing each instance with a bound. That places the unbounded problem’s difficulty precisely: the unbounded quantifier over match length is the entire source of undecidability, and bounding it collapses the problem into a familiar complexity class.

That collapse is a useful diagnostic. When a problem reduces from PCP, the reduction typically preserves the unbounded search, so the target is undecidable. When a problem reduces from bounded PCP, the target is NP-hard and possibly decidable. Confusing the two produces the common error of claiming undecidability for a problem whose instances are all bounded by construction.

A second variant, modified PCP, requires the match to begin with a designated pair. The variant is also undecidable, and it is often easier to reduce into, because the requirement that a computation start at the initial configuration can be expressed as a constraint on the first index rather than encoded into the pairs.

from itertools import product

def bounded_match(pairs, limit):
    """Search sequences of at most `limit` indices. Decidable for each limit,
    exponential in it: k**limit candidates for k pairs."""
    for m in range(1, limit + 1):
        for seq in product(range(len(pairs)), repeat=m):
            top = ''.join(pairs[i][0] for i in seq)
            bottom = ''.join(pairs[i][1] for i in seq)
            if top == bottom:
                return seq
    return None

The loop is a direct transcription of the definition, and its cost is the reason bounded PCP is not solved this way in practice. The comparison top == bottom should be incremental — extend both partial concatenations and abandon a prefix as soon as one side exceeds the other in a way no extension can repair — but the naive version makes the search space visible.

Reducing out of PCP

The standard destinations are problems about grammars and about rewriting, and the reductions share a pattern: encode each domino pair as a production, and let the grammar’s derivation generate the two concatenations in parallel.

Ambiguity of context-free grammars. A grammar is ambiguous when some string has two distinct derivation trees. Given a PCP instance, build a grammar with two nonterminals S₁ and S₂. S₁ generates every string of the form t_{i₁}…t_{iₘ} # i₁…iₘ, and S₂ generates b_{i₁}…b_{iₘ} # i₁…iₘ for exactly the same index sequences: each nonterminal derives left to right, appending one string block and one index per step, so the index suffix records the sequence that produced the prefix. A string is generated by both nonterminals exactly when some index sequence makes the two concatenations equal, that is, exactly when a match exists. Taking a fresh start symbol with productions to S₁ and to S₂ then gives a grammar that is ambiguous exactly when the instance matches. Since PCP is undecidable, grammar ambiguity is undecidable.

Intersection of context-free languages. Using the same two nonterminals as start symbols, one grammar generates the top strings with their index suffix and the other generates the bottom strings with the same suffix scheme. Their intersection is nonempty exactly when a match exists. Emptiness of the intersection is therefore undecidable, and this is a clean example of a property that is decidable for each grammar separately and undecidable for pairs.

Term rewriting and string rewriting. A finite string rewriting system is a set of rules u → v. Asking whether two given words are equivalent under the rewrite relation is the word problem for a finite semigroup presentation, and it is undecidable; the reduction encodes dominoes as rules that must be applied in a matched order. The word problem for groups, posed by Dehn in 1911, is undecidable for finitely presented groups, a result established through a chain of constructions in which PCP-like encodings play a central role.

Matrix mortality. Whether a finite set of integer matrices has a product equal to the zero matrix is undecidable, and it is known to be undecidable for 3×3 matrices over the integers while the 2×2 case is open. The dimension boundary is therefore partly an open question rather than a settled sharp line.

Each of these destinations is a problem where the natural question has no machine in it. That is the practical value of PCP: it provides a canonical undecidable problem whose instances are combinatorial objects, so the encoding work in a reduction is about the target’s structure rather than about tape simulation.

What the problem does not establish

PCP’s undecidability is a statement about the general problem, and it says nothing about instances with a fixed number of pairs or a fixed alphabet. Instances with one pair are decidable by inspection. Instances over a unary alphabet are decidable, because each string is determined entirely by its length, so a match is a question about a sequence of nonnegative integers turning two running sums into equal totals, and that question can be answered by reasoning about the pairs as integer vectors rather than by comparing words. Instances whose strings all have the same length are decidable, because a match cannot tolerate any offset between the two sides, so each pair must contribute equal-length strings and the index sequence can never be extended past a disagreement.

These restrictions are the practical route to usable algorithms, and they are why string-solving tools bound the number of variables, the alphabet size, or the word length rather than attempting the general problem. The general problem’s undecidability is a constraint on what any tool can promise, not a description of what the tool does.

A further limitation concerns the relationship to other undecidable problems. PCP is Σ₁-complete, so it is Turing-equivalent to the halting problem and to acceptance. It cannot distinguish problems at higher levels of the hierarchy, which is why the classification in The Arithmetical Hierarchy and the Turing Jump needs a different source: a problem that is Π₂-complete cannot be reduced to PCP, and proving it harder requires reducing from totality or from a jump.