Page 262

		§12.2 Mind Change Complexity

		We refer to the abandonment of a scientific conjecture as a mind change. The definition of identification places no restriction on the number of mind changes that precede convergence. In the present section we examine the impact on identifiability of bounding this number. To proceed, it will be convenient to slight modify the definition of scientist.

		We pick a nonnumerical entity "?" and append it to the range of scientists. Thus, in the functional context, scientists become mappings from SEG to Moreover, we restrict the term "scientist" to mappings M of this kind that meet the following, additional constraint: For all , and x, , if then . In other words, scientists (in our new sense) can issue ? only on some initial segment of the incoming graph; once they respond numerically (or are undefined), they do not issue ? again. Intuitively, "M(f[n]) = ?" represents a situation in which M has not seen enough data to issue any sensible hypothesis and so instead issues a ''?", which means 'no hypothesis yet.' For scientist M on function f, we say that M on f has a mind change at m if and only if we have: m > 0, and . Thus the case in which M(f[m - 1]) = ? and does not count as a mind change.

		We are now in a position to formalize identification with a bounded number of mind changes. The following definition also handles errors in final hypothesis. Recall that "" means that x is finite.

		12.1 Definition (Barzdins * and Freivalds [15], Case and Smith [35]) Let a and b be elements of ().

		(a)

		1.

		2. .

		(b) .

		So, is simply the Exa paradigm defined in Chapter 6. The special case of is variously referred to in the literature as: the Fin paradigm, finite identification, and one shot learning. The Fin paradigm, in which a scientist's first conjecture has to be correct, first appears in the work of Gold [80] and Trakhtenbrot and Barzdins* [188].

		The following proposition says that there is a collection of functions S such that: there is some scientist that infers, with no mind changes, an (n + 1)-error program for