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 = w1, w2, w3, …. , wn and B = x1, x2, x3, …. xn then there exists a non empty set of integers i1, i2, i3, …. , in such that,
w1, w2, w3, …. wn = x1, x2, x3, …. xn“
To solve the post correspondence problem we try all the combinations of i1, i2, i3, …. , 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, bab3, ba) and B = (b3, ba, a). The input set is ∑ = {0, 1}. Find the solution.
Solution:
A solution is 2, 1, 1, 3. That means w2w1w1w3 = x2x1x1x3
The constructed string from both lists is bab3b3a.
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