Undecidable Problem of Turing Machine
Automata Undecidable Problem of Turing Machine
Undecidable problems areproblems which cannot be solved by any Turing machine.
Example: Post Correspondence Problem is the type of undecidable Problem.
Post Correspondence Problem
Post Correspondence problem is a type of undecidable problem also called PCP. This type of problem was firstly introduced by Emil post in 1946.The Post Correspondence Problem over an alphabet ? belongs to a class of yes/no problems, and is stated as follows:
Consider the lists F = (f1,f2,………,fn), and
S = (s1,s2,………….,sn) of non-empty strings over an alphabet ? = {0,1}.
For each i, the pair (fi, si ) is said to be a corresponding pair. We can say this instance of Post Correspondence problem has a solution, if there is a sequence of one or more integers i1,i2,i3……………ik that, when interpreted as indexes for strings in the F and S lists yields the same string, that is
fi1,fi2………………..fik = si1,si2………………..sik.
We can say the sequence i1,i2,………………..ik is a solution to this instance of Post Correspondence problem. Example of the Post Correspondence problem is:
Example 1:
Consider the following two lists:
F = (1013, 1, 10)
S = (10, 13, 0)
Is this, Post Correspondence Problem have a solution or not?
Solution:
List of F and S can be written as:
Let k =4
i1 = 1, i2 = 2, i3 = 2, i4 = 3
The solution is the list 1,2,2,3.
The solution for the given Post Correspondence Problem find by concatenating or joining the corresponding strings in order for the two lists.
1013 1 1 10 = 10 13 13 0
f1 f2 f2 f3 = s1 s2 s2 s3
10160 = 10160
f1f2f2f3 = s1s2s2s3
Hence, It is proved that Post Correspondence Problem have a solution.
Example 2:
Consider the following two lists:
F = (ba, a, a)
S = (ba2, ab, a2)
Is this, Post Correspondence Problem have a solution or not?
Solution:
List of F and S can be written as:
Each substring of list S is greater than each substring of List F i.e.
| fi | < | si | for all i.
Hence the string generating by a sequence of substring of F is always shorter than the string generated by the sequence of corresponding substring of S.
Hence, it is proved that Post Correspondence Problem has no solution.
Example 3:
Consider the following two lists:
F = (ab, a, abaaa)
S = (b, a3 ,ab,)
Is this, Post Correspondence Problem have a solution or not?
Solution:
List of F and S can be written as:
Let k =4
i1 = 3,
i2 = 2,
i3 = 2,
i4 = 1
The solution is the list 3,2,2,1.
The solution for the given Post Correspondence Problem can be found by concatenating or joining the corresponding strings in order for the two lists.
abaaa a a ab = ab a3 a3 b
f3 f2 f2 f1 = s3 s2 s2 s1
abaaaaaab = ab a3 a3b
aba6b = aba6b
f3f2f2f1 = s3s2s2s1
Hence, It is proved that Post Correspondence Problem have a solution.
Example 4:
Consider the following two lists:
F = (11, 111, 001, 010)
S = (10110, 000, 0101, 0)
Is this Post Correspondence Problem have a solution or not?
Solution:
List of F and S can be written as:
Let k =4
The solution is the list 4,1,3,4.
The solution for the given Post Correspondence Problem can be found by concatenating or joining the corresponding strings in order for the two lists.
010 11 001 010 = 0 10110 0101 0
f4 f1 f3 f4 = s4 s1 s3 s4
01011001010 = 01011001010
f4f1f3f4 = s4s1s3s4
Hence, It is proved that Post Correspondence Problem have a solution.
Example 5:
Consider the following two lists:
F = (b, a, ba, baa, ab)
S = (aba, ba, bab, a, baa)
Is this Post Correspondence Problem have a solution or not?
Solution:
List of F and S can be written as:
The solution is the list 3,1,5,2,4,4,2,4.
The solution for the given Post Correspondence Problem can be found by concatenating or joining the corresponding strings in order for the two lists.
ba b ab a baa baa a baa = bab aba baa ba a a ba a
f3 f1 f5 f2 f4 f4 f2 f4 = s3 s1 s5 s2 s4 s4 s2 s4
babababaabaaabaa = babababaabaaabaa
babababa2b a3ba2 = babababa2b a3ba2
f3f1f5f2f4f4f2f4 = s3s1s5s2s4s4s2s4
Hence, It is proved that Post Correspondence Problem have a solution.