|
|
|
|
|
10.16 Corollary For all and all , . |
|
|
|
|
|
|
|
|
Thus, if the bound on the number of errors allowed in both the additional information and the final program are fixed, then requiring a scientist to converge to the same program for any upper bound is restrictive. |
|
|
|
|
|
|
|
|
Proof (of Proposition 10.15): Let . |
|
|
|
|
|
|
|
|
Fix an and an . Since , given f and x, one can infer in the limit a program p such that j p =c f. For each y, let wy be the unique number such that . (The uniqueness of wy follows from the definition of and the fact that j p =c f.) Let modify(p) be a program obtained from p such that, for all y and z, , where wy is as defined above. It follows immediately that modify(p) is a program for f. |
|
|
|
|
|
|
|
|
It thus follows that . |
|
|
|
|
|
|
|
|
Suppose . Then it is easy to modify M to . But as (see the remark in Exercise 10-7), this is a contradiction. Hence, . |
|
|
|
|
|
|
|
|
It is open at present whether Proposition 10.15 can be extended to show . Similar notions of additional information for the Bc paradigm are treated in the exercises. |
|
|
|
|
|
|
|
|
§10.2.2 Language Identification with an Upper Bound on Grammar Size |
|
|
|
|
|
|
|
|
Additional information for a language-learning scientist can be modeled as an upper bound on the minimal index grammar for the language to be learned. We view scientists that learn languages in the presence of such additional information as computing a mapping . Our treatment of languages is thus analogous to that of functions. For this reason we highlight only basic definitions and results that turn out differently from the functional context. |
|
|
|
|
|
|
|
|
For each and language L, MinGramc(L) denotes the minimal grammar in the j -system that accepts L with at most c errors. That is, . |
|
|
|
|
|
|
|
|
10.17 Definition (read: M on text T with additional information x converges) just in case there is an i such that for all but finitely many n, M(x, T[n]) = i, in |
|
|
|
|