Page 43

		Proof: Let be given. For the left-to-right direction, suppose that scientist F identifies . By Corollary 3.25, for each choose a locking sequence  s L for F on L. Since content( s L) is a finite subset of L, it suffices to prove that for all , if , then . For a contradiction, suppose that for some L, , and . Let T be a text for L' such that . Such a text exists because . Because  s L is a locking sequence for F on L, and because , F converges on T to an index for L. But , so F fails to identify T, hence fails to identify L'. This contradicts our choice of F.

		For the right-to-left direction, suppose the hypothesis of the theorem, namely:

		3.27 For all there is finite such that for all , implies .

		To show that is identifiable, we define a scientist F' as follows. For all , F'( s ) = the least i such that for some :

		(a) i is an index for L; and

		(b)

		F'( s ) is undefined if no such i exists.

		To see that F' identifies , fix , and let T be a text for L'. Then for some , . Let i0 be the least index for L'. Hence, to prove that F' converges on T to i0 (and thus identifies T), it suffices to show that for all j < i0 and , if j is for some and , then for all sufficiently large , . So let j < i0 and m be given such that j is for some and . Then and Hence by 3.27 there is . Since T is for L', let be large enough so that . Then .

		Theorem 3.26 allows us to prove that certain collections of languages are not identifiable. We give two examples.

		3.28 Corollary (Gold [80]) Let be infinite. Then is not identifiable.

		Proof: Let . The condition expressed by 3.26 fails for the infinite language . This is because for each finite there is (namely, D itself!) such that and .