Page 42

		Case 2: . Then by 3.23 and the fact that , choose such that and ; let .

		Observe that for all . Let . T is a text for L, since u(n) is added to T at stage n (so ) and no nonmembers of L are ever added to T (so ). Finally, F does not converge on T to an index for L, since for each either or, for some with , . Thus, there are infinitely many numbers m0, m1, m2, . . . such that either F(T[mi]) is an incorrect index or .

		Intuitively, if F identifies T, then Theorem 3.22 guarantees the existence of that "locks" F onto a conjecture for L in the following sense: no presentation from L can dislodge F from F( s ). This suggests the following definition.

		3.24 Definition (Blum and Blum [18]) Let , scientist F and be given.  s  is a locking sequence for F on L just in case:

		(a)

		(b)WF( s ) = L;

		(c) for all , if , then .

		So Theorem 3.22 can be put this way:

		3.25 Corollary (Blum and Blum [18]) If scientist F identifies , then there is a locking sequence for F on L.

		Note that Theorem 3.22 does not characterize F's behavior on elements drawn from . In particular, if is such that , then even if  s  is a locking sequence for F on L, may well differ from F( s ).

		§3.6.2 Characterization

		We now state and prove a characterization of the collections of identifiable languages.

		3.26 Theorem (Based on Angluin [6]) is identifiable if and only if for all there is finite such that for all , if then .