|
|
|
|
|
|
12-1 For each  , let  . Intuitively, cyl(f) denotes the cylindrification of f. |
|
|
|
|
|
|
|
|
(a) Show that  . |
|
|
|
|
|
|
|
|
(b) Show that  . |
|
|
|
|
|
|
|
|
12-2 Show  . |
|
|
|
|
|
|
|
|
12-3 Recall the convention that: 0 < 1 < 2 < . . . < *. Also recall that, for each  , Exa can be written as  , that is, there is no bound on the number of mind changes. Suppose  . Show that  . |
|
|
|
|
|
|
|
|
12-4 (Sharma [173]) Adapt the notion of mind changes to the paradigm InfTxtEx (Definition 8.31) to define the paradigm InfTxtExn. Show that  . This somewhat surprising result says that the collections of languages that can be one shot learned from both positive and negative data can also be identified in the limit from only positive data. Additionally, show that  . |
|
|
|
|
|
|
|
|
12-5 Show that the function Conv defined in Equation (12.1) on page 265 satisfies the axioms given in Definition 12.10. |
|
|
|
|
|
|
|
|
12-6 The following definition (due to Daley and Smith [54]) is intended to capture the total amount of work done by a scientist on a function before the onset of convergence. |
|
|
|
 |
|
|
|
|
12.26 Definition Let F M(f[n]) denote the time (or any other suitable Blum complexity measure [19]) used by M on the evidential state f[n]. For each M and f, define |
|
|
|
|
|
|
|
|
The above is based on the integral  F(x) dx defining work in classical mechanics; auc stands for 'area under the curve.' Note that, as was the case with identification from a bounded number of examples, the above notion also assumes that the graph of the |
|
|
|
|
