Page 230

		Fix an and an . Clearly, condition (i) in definition of M0 will succeed for sufficiently large initial segments of f. Thus, , which by definition of , is a program for f.

		Fix an and an . Then, for any initial segment of f and this x, condition (i) will fail. Thus, for any sufficiently large n, M0(x, f[n]) will stabilize to , a program for f.

		Therefore, .

		The proof of is a diagonalization employing the operator recursion theorem (Theorem 2.6). We refer the reader to Jain and Sharma [86] for the proof.

		The next proposition illustrates the power of even a small amount of additional information. The proposition says that there are collections of functions that can be UniBex-identified in the presence of an upper bound on the minimal size *-error program, but which cannot be Bc-identified even if the scientist is allowed to output programs that commit no more than a predetermined number of errors.

		10.13 Proposition For each , .

		The proof of this result is the subject of Exercise 10-3. Propositions 10.12 and 10.13 have the following corollary on UniBex-identification.

		10.14 Corollary Suppose . Then:

		(a) .

		(b) .

		Part (a) of the corollary says that even the worst quality of additional information (an upper bound on a minimal *-error program) yields extra learning power over Exa-identification. Part (b) says that if the bound on the number of errors allowed in the final inferred program is fixed in advance, then decreasing the quality of the additional information results in a reduction in learning power with respect to UniBex-identification. The proof of the above corollary is left to the reader. A related result about Bex-identification is the subject of Exercise 10-4.

		We end this section by presenting a result that implies the advantages of Bex-identification over UniBex-identification.

		10.15 Proposition Suppose . Then, .