|
|
|
|
|
within some fixed, finite set of indexes where each index is for a function sufficiently close to the target. We adapt this notion to the case of languages. |
|
|
|
|
|
|
|
|
6.25 Definition (Case [25], Osherson and Weinstein [143]) Let and . |
|
|
|
|
|
|
|
|
(a) We say that M on T finitely converges to a finite set D just in case, for all but finitely many n, . |
|
|
|
|
|
|
|
|
(b) (written: ) just in case for all texts T for L there is a finite, nonempty set D of cardinality at most b such that M finitely converges to D and, for each , Wi = a L. |
|
|
|
|
|
|
|
|
(c) . |
|
|
|
|
|
|
|
|
Thus, just in case for every text T for L there is a nonempty, finite set DT of no more than b indexes for a-variants of L such that all but finitely many of M's conjectures are drawn from DT. |
|
|
|
|
|
|
|
|
For the function case, Proposition 6.17 showed that there is nothing to be gained from allowing scientists to vacillate. The situation is different for languages. Indeed, we now prove that there are collections of languages for which 0-error indexes can be learned if the scientist may vacillate among n + 1 conjectures, but for which even *-error indexes cannot be learned if vacillation is limited to sets of size n. |
|
|
|
|
|
|
|
|
6.26 Proposition (Case [25]) |
|
|
|
|
|
|
|
|
(a) For , . |
|
|
|
|
|
|
|
|
(b) For , . |
|
|
|
|
|
|
|
|
As an immediate corollary we obtain: |
|
|
|
|
|
|
|
|
6.27 Corollary Let . Then . |
|
|
|
|
|
|
|
|
Proof (of Proposition 6.26): We prove only part (a). The argument for part (b) can be worked out using the proof of part (a) in a way similar to the proof of Corollary 6.6. |
|
|
|
|
|
|
|
|
Notation: Define , where m is the least number such that . Intuitively, Lastn(M, s ) denotes the set of the last n distinct indexes output by M when it is fed evidential state |
|
|
|
|