Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Consider two lists A and B of three strings on {0, 1}
X:
|
List A |
List B |
|
1 |
111 |
|
10111 |
10 |
|
10 |
0 |
Y:
|
List A |
List B |
|
10 |
101 |
|
011 |
11 |
|
101 |
011 |
Which of the following is true?
1
Only PCP in X has solution.
2
Only PCP in Y has solution.
3
PCP in both X and Y has solution.
4
PCP neither in X nor in Y has solution.