|
|
|
|
|
|
10-4 The aim of this exercise is to establish a hierarchy for Bex-identification which shows that decreasing the quality of additional information results in a reduction in learning power. Towards this goal, first prove that, for all  ,  . Then, verify that this result implies that for all  ,  |
|
|
|
|
|
|
|
|
10-5 Show that, for each  ,  . |
|
|
|
|
|
|
|
|
Hint: Use the union of the following classes of functions: |
|
|
|
|
|
|
|
|
10-6 Show that  . |
|
|
|
|
|
|
|
|
Hint: Consider S, the class of functions  each of which satisfies: |
|
|
|
|
|
|
|
|
1.  |
|
|
|
|
|
|
|
|
2.  |
|
|
|
|
|
|
|
|
3.  |
|
|
|
|
|
|
|
|
10-7 Show that  . Observe that this result implies that  . This latter observation says that there is no scientist that can UniBex-identify every recursive function, even if the scientist is given the best quality additional information and is only required to output a finite variant program. |
|
|
|
|
|
|
|
|
Hint: Use the class of functions  . |
|
|
|
|
|
|
|
|
10-8 Use an argument similar to the one for Exercise 10-7 to argue  . Note: It is currently open whether this result or the one in Exercise 10-7 can be extended to  . |
|
|
|
|
|
|
|
|
10-9 Give a proof of Proposition 10.24. |
|
|
|
|
|
|
|
|
Hint: For each  , consider the class of languages  |
|
|
|
|
