Page 133

		Endfor

		End ( Stage s )

		Consider the following two cases.

		Case 1: All stages terminate. In this case, let f =  j p(0). Clearly, the range of f contains indexes only for f. Hence, . However, M on f makes infinitely many mind changes; hence, .

		Case 2: Some stage s starts but fails to terminate. In this case let fl =  j p(2s+1) and f2 =  j p(2s+2). Clearly, both fl and f2 are in and, for infinitely many x, . However, M(f1) = M(f2) = M( j p(0)[xs]). Thus M fails to Ex*-identify at least one of f1 and f2.

		From the above cases it follows that .

		6.11 Corollary .

		§6.1.3 Behaviorally Correct Function Identification with Anomalies

		The previous two subsections investigated two ways of liberalizing the Ex criterion of successful learning. These two means are combined in the following definition.

		6.12 Definition (Case and Smith [35]) Let .

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

		(b) .

		Thus, a scientist Bca-identifies function f just in case, being fed the graph of f, she produces an infinite sequence of hypotheses, p0, p1, p2, . . . such that for all but finitely many n, pn is an index for an a-variant of f. It is easy to see that . The next proposition shows that these containments are strict.

		6.13 Proposition (Case and Smith [35])

		(a) For each ,

		(b)