PCP is undecidable: The PCP is a fascinating undecidable problem! Since its presentation by Emil L. Post in 1946, scores of theoretical and practical problems have been shown to be undecidable by reduction from the PCP.4 A partial list includes the following problems:
• Undecidability of the ambiguity of a given CFG (see Exercise 17.2).
• Undecidability of aliasing in programming languages [101].
• Undecidability of the validity of an arbitrary sentence of first-order logic .
The impressive diversity of these problems indicates the commonality possessed by this variety of problems that Post’s correspondence problems embody.
The main undecidability result pertaining to PCPs can be phrased as follows. Given any alphabet Σ such that |Σ| > 1, consider the tile alphabet T ⊆Σ∗ × Σ∗. Now consider the language
PCP = {S | S is a finite sequence over T that has a solution}.
Theorem . PCP is undecidable.
In, PCP is studied at a detailed level, and a software tool PCPSolver is made available to experiment with the PCP. The following terminology is first defined:
With respect to the above definitions, here are some fascinating results cited in [125], that reveal the depth of this simple problem:
Here are more unusual results that pertain to the shortest solutions that exist for two innocent looking PCP instances:
These discussions help build our intuitions towards the proof we are about to sketch: the undecidability of PCP indicates the inherent inability to bound search while solving a general PCP instance.