Page 131

		such that fy' differs from  j p on each of xs, . . ., xs + m. Take f = fy'. Then f is an element of that M fails to Exm-identify.

		From the above two cases it follows that .

		The following corollary says that if the finite number of errors allowed in the final hypothesis is not bounded, then more collections of functions can be learned than otherwise.

		6.6 Corollary (Case and Smith [35]) .

		Proof: It is clear that . Suppose by way of contradiction that . Then there exists an m such that , hence, any subset of is also in Exm. But is a subset of , which is not in Exm. This is a contradiction.

		It is immediate from Proposition 6.5 that allowing more errors increases learning power. We note this fact in the form of an "anomaly hierarchy," one of many such hierarchies to be encountered in this and later chapters.

		6.7 Corollary .

		§6.1.2 Behaviorally Correct Function Identification

		Turning from accuracy to stability, we wish now to relax the Ex requirement that scientists converge to a single index for the target function. The simplest alternative is to require only that a scientist eventually ceases to produce incorrect indexes, leaving her the liberty of forever changing the particular index used to name the target function. This criterion was first introduced by Barzdins * [14] and later considered by Case and Smith [35] (see also Feldman[58]). It is formalized as follows.

		6.8 Definition (Barzdins* [14], Case and Smith [35])

		(a) M Bc-identifies f (written: ) just in case for all but finitely many n,  j M(f[n]) = f.

		(b) .

		Bc is read as "behaviorally correct." Thus, scientist M Bc-identifies f just in case M, fed the graph of f, produces an infinite sequence of hypotheses, p0, p1, p2, . . ., such that for all but finitely many n, pn is an index for f. It follows immediately that . We leave the proof of the following fact to Exercise 6-4.