|
|
|
|
|
|
(a)  |
|
|
|
|
|
|
|
|
(b) Let L be recursive. Then,  . Compare this result to Exercise 8-4. |
|
|
|
|
|
|
|
|
8-10 Prove: N*Lang = Im*Lang. |
|
|
|
|
|
|
|
|
8-11 Prove:  . |
|
|
|
|
|
|
|
|
8-12 Prove:  . |
|
|
|
|
|
|
|
|
Hint: Note that  from the proof of Proposition 8.12 can be used to show that  . A similar argument works here. |
|
|
|
|
|
|
|
|
8-13 Prove, for all  , that  . This is an extension of Proposition 8.13. |
|
|
|
|
|
|
|
|
8-14 In the context of identification from inaccurate texts with a finite number of inaccuracies, this exercise compares situations in which a bound on the number of inaccuracies is available to situations in which there is no such bound. Show that  is nonempty. Hint: The positive part of this has to be non-constructive in i. |
|
|
|
|
|
|
|
|
8-15 Prove Proposition 8.15. |
|
|
|
|
|
|
|
|
8-16 Obtain the following hierarchies as corollaries to Proposition 8.15. |
|
|
|
|
|
|
|
|
(a)  |
|
|
|
|
|
|
|
|
(b)  |
|
|
|
|
|
|
|
|
(c)  |
|
|
|
|
|
|
|
|
8-17 Prove Proposition 8.19. |
|
|
|
|
|
|
|
|
8-18 Since  , there is scope for further fine-tuning of Corollary 8.20. As an example of such a refinement, show that for each  ,  . |
|
|
|
|
|
|
|
|
Open Question:  ? |
|
|
|
|
|
|
|
|
8-19 Prove:  . |
|
|
|
|
