|
|
|
|
|
|
— namely, the one that responds to  with a canonical index for N minus the least number missing from content( s ) — is not reliable as it converges on a text for the even numbers but fails to identify them. |
|
|
|
|
|
|
|
|
Reliability is a useful property of scientists. A reliable scientist never fails to signal the inaccuracy of a previous conjecture. To explain, let M be a reliable scientist, let T be a text for some language, and suppose that for some i,  , M(T[n]) = i. If  — that is, if i is incorrect—then for some m > n we have  . (This is the case, because otherwise M converges on T to the incorrect index i, contradicting M's reliability.) The new index M(T[m]) signals the incorrectness of i. It might thus be hoped that every identifiable collection of languages is identified by a reliable scientist. However, reliability turns out to be quite a debilitating constraint on scientists, as shown by the following proposition. |
|
|
|
|
|
|
|
|
5.42 Proposition Suppose some reliable scientist M identifies  . Then L is finite. |
|
|
|
|
|
|
|
|
Proof: This is a straightforward locking sequence argument. Let s be a locking sequence for M on L. Then, if  , M converges on T to an index for L. Thus L = content(T) = content( s ), which is finite. |
|
|
|
|
|
|
|
|
5.43 Corollary  |
|
|
|
|
|
|
|
|
§5.5 Constraints on the Relation between Conjectures |
|
|
|
|
|
|
|
|
The successive conjectures emitted by an arbitrary scientist need stand in no particular relation to each other. We now deal with strategies resulting from imposition of such a relation. |
|
|
|
|
|
|
|
|
A seemingly rational constraint is captured by the following strategy. |
|
|
|
|
|
|
|
|
5.44 Definition (Angluin [6]) |
|
|
|
|
|
|
|
|
(a) M is conservative on L just in case for all s and  such that  and  , if  , then  . |
|
|
|
|
|
|
|
|
(b) M is conservative on  ; just in case M is conservative on each  . |
|
|
|
|
|
|
|
|
(c) M is conservative just in case M is conservative on each  . |
|
|
|
|
