Post Correspondence Problem

In this section, we will discuss the undecidability of string and not of Turing machines. The undecidability of the string is determined with the help of Post's Correspondence Problem (PCP). Let us define the PCP.

"The Post's correspondence problem consists of two lists of string that are of equal length over the input. The two lists are A = w₁, w₂, w₃, .... , w_n and B = x₁, x₂, x₃, .... x_n then there exists a non empty set of integers i₁, i₂, i₃, .... , in such that,
w₁, w₂, w₃, .... w_n = x₁, x₂, x₃, .... x_n"

To solve the post correspondence problem we try all the combinations of i₁, i₂, i₃, .... , in to find the w1 = x1 then we say that PCP has a solution.

Example 1:

Consider the correspondence system as given below

A = (b, bab³, ba) and B = (b³, ba, a). The input set is ∑ = {0, 1}. Find the solution.

Solution:

A solution is 2, 1, 1, 3. That means w₂w₁w₁w₃ = x₂x₁x₁x₃

The constructed string from both lists is bab³b³a.

Example 2:

Does PCP with two lists x = (b, a, aba, bb) and y = (ba, ba, ab, b) have a solution?

Solution: Now we have to find out such a sequence that strings formed by x and y are identical. Such a sequence is 1, 2, 1, 3, 3, 4. Hence from x and y list

Example 3:

Obtain the solution for the following system of posts correspondence problem. A = {100, 0, 1}, B = {1, 100, 00}

Solution: Consider the sequence 1, 3, 2. The string obtained from A = babababb. The string obtained from B = bababbbb. These two strings are not equal. Thus if we try various combination from both the sets to find the unique sequence, we could not get such a sequence. Hence there is no solution for this system.

Example 4:

Obtain the solution for the following system of posts correspondence problem, X = {100, 0, 1}, Y = {1, 100, 00}.

Solution: The solution is 1, 3, 1, 1, 3, 2, 2. The string is

X1X3X1X1X3X2X2 = 100 + 1 + 100 + 100 + 1 + 0 + 0 = 1001100100100
Y1Y3Y1Y1Y3Y2Y2 = 1 + 00 + 1 + 1 + 00 + 100 + 100 = 1001100100100