Questions: Post Correspondence Problem and Applications

Question 1

Why is the Post Correspondence Problem (PCP) particularly valuable as an intermediate step when proving undecidability of formal language problems?

• A. Because PCP is decidable for small domino sets, making it easier to use in reductions
• B. Because PCP can be solved in polynomial time, making reductions from it efficient
• C. Because PCP involves only string concatenation and matching — not Turing machine states or tapes — making reductions to grammar and language problems natural
• D. Because PCP is the only undecidable problem that does not involve the halting problem

Answer: (C)

PCP's power as a reduction tool comes from its surface structure. It is entirely about strings: can you arrange domino pairs so top and bottom concatenations match? This is conceptually close to formal language problems (which also concern string generation and matching), making PCP reductions to those problems natural and clean. Contrast this with reducing directly from the halting problem, which requires encoding Turing machine configurations — a more complex encoding when the target problem is about grammars. PCP is undecidable but looks nothing like a TM, which is precisely what makes it a useful bridge.

Question 2

You are given three domino pairs: (ab/a), (b/ba), (a/ab). Which of the following constitutes a valid PCP solution?

• A. Any arrangement where the total number of characters on top equals the total on the bottom
• B. The sequence domino 1, domino 2, domino 3 chosen exactly once — giving top='abba', bottom='abaab'
• C. A sequence (possibly with repetition) of dominoes where the concatenation of all top strings equals the concatenation of all bottom strings
• D. A sequence where each domino's top string is longer than its bottom string

Answer: (C)

A valid PCP solution is a sequence of domino indices (repetition allowed) such that the joined top strings equal the joined bottom strings. Using dominoes 1, 2, 3 once: top = 'ab'+'b'+'a' = 'abba', bottom = 'a'+'ba'+'ab' = 'abaab' — not a match. Crucially, there is no length requirement: the top and bottom concatenations simply must be identical strings. Dominoes may be used in any order and any number of times. The decision problem asks whether any such sequence exists — and no algorithm can answer this for arbitrary domino sets.

Question 3

The Post Correspondence Problem can be decided for any finite set of dominoes by exhaustively testing most sequences up to a sufficiently large length bound.

• T. True
• F. False

Answer: False

This is the key misconception. If a PCP solution exists, there is no computable upper bound on how long it might be. A matching sequence might require thousands of domino repetitions before the top and bottom concatenations align. Since you cannot determine when to stop searching, exhaustive bounded search does not work as a decision procedure. This unboundedness is precisely why PCP is undecidable: the acceptance problem for a Turing machine is encoded into domino matching, and the length of the matching sequence corresponds to the length of the TM's computation — which can be arbitrarily long.

Question 4

Undecidability of context-free grammar equivalence can be proved by reducing PCP to it, because the string concatenations in PCP correspond naturally to language generation by CFGs.

• T. True
• F. False

Answer: True

This is one of PCP's most important applications. To show CFG equivalence is undecidable, one constructs two context-free grammars whose generated languages encode the top and bottom concatenations of PCP domino sequences. The two grammars generate the same language if and only if some matching sequence exists — i.e., PCP has a solution. Since PCP is undecidable, CFG equivalence must be undecidable too. The reduction is clean because CFG string generation and PCP string concatenation share the same string-based structure — no TM encoding needed.

Question 5

Describe how the domino encoding in the PCP undecidability proof simulates a Turing machine computation, and what guarantees that a matching sequence exists if and only if the TM accepts.

Model answer: The construction encodes the TM's sequence of configurations (computation history) into domino pairs. Top strings lag one configuration step behind bottom strings — the bottom starts with the initial configuration while the top starts blank. The dominoes are designed so that each step of the TM's computation produces a domino that advances the top by one configuration, closing the lag. The top and bottom concatenations can only become equal if the TM reaches an accepting configuration, at which point special 'accepting' dominoes close the gap. A match exists iff the TM accepts.

The genius of this encoding is that it converts an infinite computational process (does this TM halt and accept?) into a finite combinatorial question (does this domino collection have a matching sequence?). The computation history framing — each domino corresponds to one transition step — ensures that any matching sequence must be a valid TM computation path ending in acceptance. This is why the proof works: solving PCP would solve the acceptance problem, which is undecidable.