Pcp Is Undecidable

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:

• A PCP instance is a member of the language PCP.
• If any member of T is of the form w,w, then that PCP instance is trivial (has a trivial solution).
• The number of pairs in a PCP instance is its size. The length of the longest string in either position of a pair (“upper or lower string of a tile”) in a PCP instance is the width of the instance.
• An optimal solution is the shortest solution sequence. The example given on page 315 has an optimal solution of length 2.

With respect to the above definitions, here are some fascinating results cited in [125], that reveal the depth of this simple problem:

• Bounded PCP is NP-complete (finding solutions of length less than an a priori given constant K ∈ Nat). Basically, checking whether solutions below a given length is decidable, but has, in all likelihood, exponential running time (see Chapter 19 for an in-depth discussion of NP-completeness).
• PCP instances of size 2 are decidable, while PCP instances of size 7 are undecidable (note: no restriction on the width is being imposed). Currently, decidability of sizes 3 through 6 are unknown.

Here are more unusual results that pertain to the shortest solutions that exist for two innocent looking PCP instances:

• The PCP instance below has an optimal solution of length 206:

• The PCP instance below has two optimal solutions of length 75:

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.