Chapter 10: Decidability and Recursively Enumerable Languages g 321
10.18 Prove that PCP is solvable if Il: I = l.
10.19 Let x =(Xl' .. X,,) and Y =(YI ... y,,) be two lists of nonempty strings
over l: and Il: I 2: 2. (i) Is PCP solvable for n = I? (ii) Is PCP solvable
for n = 2?
10.20 Prove that the PCP with {(01, 011), (1, 10), (I,ll)} has no solution.
(Here, Xl = 01, X2 = 1, X3 = 1, YI = 011, 1'2 = 10, Y3 = 11.)
10.21 Show that the PCP with S = {(O, 10), (1
2
0, 0
3
), (0
2 1, IOn has no
solution. [Hint: No pair has common nonempty initial substring.]
10.22 Does the PCP with X =(b
3
, ab
2
) and Y =(b
3
, bab
3
) have a solution?
10.23 Find at least three solutions to PCP defined by the dominoes:
1
10m
I
10
10.24 (a) Can you simulate a Turing machine on a general-purpose
computer? Explain.
(b) Can you simulate a general-purpose computer on a Turing
machine'? Explain.