The Post Correspondence Problem is an undecidable problem that turns out to be a very helpful tool for proving problems in logic or in formal language theory to be undecidable

Let Σ be an alphabet with at least two letters. An instance of the Post Correspondence problem (for short, PCP) is given by two sequences U = (u1,...,um) and V =(v1,...,vm), of strings ui,vi∈ Σ*.

The problem is to find whether there is a finite sequence (i1,...,ip), withij∈ {1,...,m} for j = 1,...,p, so that ui1ui2 ···uip = vi1vi2 ···vip.

Example:

Let U= {0,2,4,6,8} and V={1,3,5,7,9}

As per the theorem we have to find a finite sequence I such that

$u_i1, u_i1,…,u_ip= v_i1, v_i1,…, v_ip$

Let us assume we have a sequence I={1,2,3,4,5}

So, as p=5 in this case,

$u_i1, u_i1,…,u_ip= u1, u2,…, u5 = 0,2,4,6,8$

$v_i1, v_i1,…,v_ip= v1, v2,…, v5 = 1,3,5,7,9$

But as we see in this example,

$u_i1, u_i1,…,u_i ≠ v_i1, v_i1,…, v_{ip}$

So we need to find another finite sequence I such that

$u_i1, u_i1,…,u_ip= v_i1, v_i1,…, v_ip$

Finding such a sequence I would hence be undecidable as it would also depend on the two sequences U and V

The Post correspondence problem is undecidable, provided that the alphabet Σ has at least two symbols.

We shall reduce the halting problem to the PCP, by encoding sequences of ID‟s as partial solutions of the PCP.

For instance, this can be done for RAM programs. The first step is to show that every RAM program can be simulated by a single register RAM program.

Then, the halting problem for RAM programs with one register is reduced to the PCP (using the fact that only four kinds of instructions are needed). As an application, we prove the following result:

It is undecidable whether a context-free grammar is ambiguous.

Proof . We reduce the PCP to the ambiguity problem for CFG‟s. Given any instance U= (u1,...,um) and V = (v1,...,vm) of the PCP, let c1,...,cm be m new symbols, and consider the following languages:

LU = {ui1 ···uipcip ···ci1 | 1 ≤ ij ≤ m, 1 ≤ j ≤ p, p ≥ 1},

LV = {vi1 ···vipcip ···ci1 | 1 ≤ ij ≤ m, 1 ≤ j ≤ p, p ≥ 1}, and LU,V = LU ∪ LV .

We can easily construct a CFG, GU,V , generating LU,V . The productions are:

S −→ SU S −→ SV SU −→ uiSUci SU −→ uici SV −→ viSV ci SV −→ vici.

It is easily seen that the PCP for (U,V ) has a solution iffLU ∩ LV 6= ∅iff G is ambiguous.

Remark: As a corollary, we also obtain the following result: It is undecidable for arbitrary context-free grammars G1 and G2 whether L(G1) ∩ L(G2) = ∅.