Page 140

		§6.2.2 Behaviorally Correct Language Identification

		The next definition liberalizes the stability requirement for TxtEx just as we did for Ex.

		6.21 Definition (Osherson and Weinstein [143], Case and Lynes [33]) Let .

		(a) M TxtBca-identifies L (written: ) just in case, for all texts T for L, for all but finitely many n, WM(T[n]) =a L.

		(b) .

		(c) TxtBc0 is abbreviated to TxtBc.

		Thus a scientist M TxtBca-identifies language L just in case M, fed any text for L, produces an infinite sequence of hypotheses, all but finitely many of which are for a-variants of L. Successive conjectures need not be identical, nor even for the same language; and different texts may lead to different sequences.

		The definition gives rise to a strict hierarchy, as described in the following corollary. Its proof follows a modification of the proof of Proposition 6.13 and is left for the reader. A different proof for this can be obtained using Proposition 6.24 below.

		6.22 Corollary.

		In the case of functions, Propositions 6.9 and 6.10 reveal that Bc properly contains Ex*. Is the situation similar when we pass to TxtBc and TxtEx*? The following proposition shows that the latter paradigms are in fact incomparable.

		6.23 Proposition(a) .

		(b) .

		Proof: Part (a) is an immediate consequence of Proposition 6.10. Part (b) is taken up in Exercise 6-9.

		The above proposition shows that the instability allowed in TxtBc fails to compensate for the finite, but unbounded, number of errors allowed in TxtEx*. A subtler picture emerges when we consider bounded numbers of errors, as embodied in the criteria TxtExm.