Questions: Post Correspondence Problem

Question 1

An engineer builds a program to solve the Post Correspondence Problem: it searches all domino sequences of length 1, 2, 3, … in order and reports 'no solution exists' if no match is found after 10¹⁰⁰ steps. Why is this not a correct decision procedure for PCP?

• A. The algorithm is too slow for practical use — a correct algorithm would need to run in polynomial time
• B. A valid matching sequence might have length 10¹⁰⁰ + 1 or longer — there is no finite bound N such that the absence of a solution of length at most N certifies that no solution exists at all
• C. The algorithm does not check all permutations of each length, only sequences in a fixed order
• D. PCP is only undecidable for instances with more than 7 string pairs; the algorithm works correctly on small instances

Answer: (B)

Undecidability is not about speed — it is about the impossibility of a correct algorithm for all instances. The algorithm above is correct whenever a solution exists (it will eventually find it), but it fails on instances with no solution: it reports 'no solution' after 10¹⁰⁰ steps, but the real answer might still be 'a solution exists' at a greater length. Since there is no bound on the minimum solution length (it can be arbitrarily large even when a solution exists), no finite cutoff can serve as a reliable certificate of non-existence. This 'no finite witness of failure' is the structural reason PCP is undecidable.

Question 2

Why is the Post Correspondence Problem especially useful as an intermediate step for proving undecidability results in formal language theory, rather than always reducing directly from the halting problem?

• A. Because the halting problem is decidable in special cases where PCP is not, making PCP a stronger reduction source
• B. Because PCP's clean combinatorial structure — matching string sequences — is much easier to embed into formal language problems such as CFG ambiguity than full Turing machine computation histories
• C. Because PCP is more computationally complex than the halting problem, making reductions from it yield stronger undecidability results
• D. Because formal language proofs require reductions that operate only on context-free grammars, not Turing machines

Answer: (B)

Reducing from the halting problem to a new problem requires encoding TM computations into the new domain, which is complex and TM-specific. PCP is already proved undecidable via the halting problem (done once), and its structure — does any sequence of dominoes produce a matching top-bottom string? — maps naturally into questions about formal languages. Proving CFG ambiguity or CFG equivalence undecidable via PCP only requires showing how to encode a PCP instance as a grammar construction, which is shorter and cleaner. PCP acts as a laundered form of undecidability: the messiness of TM encodings is hidden in the PCP construction once, and all downstream reductions start from that clean domino-matching formulation.

Question 3

The Post Correspondence Problem is undecidable in general, but restricted to instances over a unary alphabet (strings built from a single symbol), it becomes decidable.

• T. True
• F. False

Answer: True

This illustrates that undecidability is a property of the general problem, not every restricted variant. Over a unary alphabet, the matching condition reduces to an integer equation: do there exist positive integers n₁, …, n_k (the domino indices) such that the sum of top-string lengths equals the sum of bottom-string lengths? This is a system of linear Diophantine equations, which is decidable. Undecidability of general PCP relies on the ability to encode arbitrary computations in string structure — something a unary alphabet cannot do.

Question 4

The undecidability of PCP means that PCP instances are simply too computationally hard for current computers — a sufficiently powerful future computer could solve most instances.

• T. True
• F. False

Answer: False

Undecidability is not a statement about computational resources. An undecidable problem cannot be solved by any algorithm regardless of speed or memory, because no algorithm can produce a correct yes/no answer on all instances. For PCP, the issue is that no algorithm can correctly distinguish all solvable instances from all unsolvable ones in principle — not because the computation takes too long, but because the problem has no algorithmic decision procedure. A computer running for the lifetime of the universe still could not decide all PCP instances correctly.

Question 5

Why does the 'no finite witness of failure' property explain why no algorithm can decide PCP, and what makes this property characteristic of undecidable problems more generally?

Model answer: For a 'yes' instance of PCP, there is a finite witness of success: the matching sequence itself, which can be verified in polynomial time by checking that top strings concatenate to the same string as bottom strings. But for a 'no' instance, there is no finite object that certifies the absence of any solution. If no sequence of length 1 through N matches, a solution could still exist at length N+1, N+2, or arbitrarily longer — there is no structural property of PCP instances that bounds the minimum solution length or rules out longer solutions. Any algorithm that stops at a finite bound will sometimes classify a solvable instance as unsolvable. This is characteristic of undecidable problems: the negative direction lacks a verifiable certificate. By contrast, decidable problems like graph connectivity have short certificates for both yes (a connected spanning tree) and no (a separating cut), allowing exhaustive search to terminate.

This 'no certificate of failure' structure separates undecidable problems from NP-hard ones: NP-hard problems have efficiently verifiable yes-certificates (solutions), so even if finding them is hard, verification works. Undecidable problems lack even this guarantee for one direction.