Page 128

		(a) We say that  x  =n f (read:  x  is an n-variant of f) just in case .

		(b) We say that  x  =* f just in case is finite; we refer to  x  as a finite variant of f.

		In the definition it is helpful to think of an index i for  x  as a "possibly anomalous explanation" for f, that is, an explanation whose prediction may include a finite number of anomalies. In this case, i is called an n-error (or *-error) index for f. We distinguish two kinds of errors that i may embody in explaining f. If  x (x) is undefined, then i commits an error of omission at x. If , then i commits an error of commission at x.

		Definition 6.1 suggests the following criterion of learning, in which it suffices to converge to an index for a function that is proximate to the target. (The * case of the new paradigm was introduced by Blum and Blum [18], the other cases by Case and Smith [35].)

		6.2 Definition (Blum and Blum [18], Case and Smith [35]) Let .

		(a) M Exa-identifies f (written: ) just in case and  j M(f) =a f.

		(b) M Exa-identifies just in case .

		(c)

		Ex0, of course, is the same as Ex. Note that in Exa, for , the parameter 'a' is an upper bound on the number of errors allowed in the final hypothesis, not an exact number of required errors. Indeed, were a interpreted in the latter sense, Exa would collapse to the original paradigm Ex (see Exercise 6-2).

		The success criterion for Ex* can be formulated this way: M Ex*-identifies just in case for every there is such that M Exm-identifies f. Thus, M's errors must be bounded on each function in . The bound itself, however, might grow without limit across different members of .

		A simple modification of the proof of Proposition 4.15 yields:

		6.3 Proposition For every collection of functions, and any , is Exa identifiable just in case some total scientist Exa-identifies .

		It also follows that there is a recursively enumerable sequence of total computable scientists M0,M1, . . ., such that for all , there is an i such that .