Post Correspondence Problem

The Post Correspondence Problem (PCP), introduced by Emil Post in 1946, is an undecidable decision problem. The PCP problem over an alphabet ∑ is stated as follows −

Given the following two psts, M and N of non-empty strings over ∑ −

M = (x₁, x₂, x₃,………, x_n)

N = (y₁, y₂, y₃,………, y_n)

We can say that there is a Post Correspondence Solution, if for some i₁,i₂,………… i_k, where 1 ≤ i_j ≤ n, the condition x_i1 …….x_ik = y_i1 …….y_ik satisfies.

Example 1

Find whether the psts

M = (abb, aa, aaa) and N = (bba, aaa, aa)

have a Post Correspondence Solution?

Solution

Here,

x₂x₁x₃ = ‘aaabbaaa’

and y₂y₁y₃ = ‘aaabbaaa’

We can see that

x₂x₁x₃ = y₂y₁y₃

Hence, the solution is i = 2, j = 1, and k = 3.

Example 2

Find whether the psts M = (ab, bab, bbaaa) and N = (a, ba, bab) have a Post Correspondence Solution?

Solution

In this case, there is no solution because −

| x₂x₁x₃ | ≠ | y₂y₁y₃ | (Lengths are not same)

Hence, it can be said that this Post Correspondence Problem is undecidable.