|
|
|
|
|
|
11-3 Let  be limiting recursive. Suppose that  . Further suppose that for each  , M on input f, makes at most finitely many queries to A, that is,  . Show that  . |
|
|
|
|
|
|
|
|
11-4 (Fortnow, Gasarch, Jain, et al. [59]) Suppose A is Turing reducible to both K and some 1-generic set. Show that OAEx = Ex. |
|
|
|
|
|
|
|
|
11-5 Extend Definition 11.13 in the obvious way to allow oracle scientists to converge to finite variant grammars for the language being identified. That is, for  and  , define paradigms OATxtExa. Then establish the following stronger version of Proposition 11.15: |
|
|
|
|
|
|
|
|
Let A0, A1, A2, . . . be a sequence of sets such that  and let  . Choose C so that  . Then there is an  . |
|
|
|
|
|
|
|
|
Hint: Consider a cylindrification of the class used in the proof of Proposition 11.15. |
|
|
|
|
