Page 172

		additional errors in the output theory, in the sense discussed in Section 6.1.1. To what extent does such leniency compensate for additional noisy or missing points in the input data? The proposition stated below shows that the tradeoff is not straightforward. To see this, consider ImnExn. just in case there is some scientist M that behaves as follows. Given an n-imperfect text G for any , M converges on G to an index for a (partial) function  h  that differs from f on no more than n arguments. It might be thought that ImnExn defines the same family of collections as ImmExm for distinct n and m. However, this is not true. Indeed, Part (a) of the next proposition shows that allowing one additional error in the output theory, in some cases, more than compensates for additional imperfection in the input data. Specifically, there are classes of functions for which an (i + 1)-error program can be identified from texts with an arbitrarily large finite number of imperfections, but for which an i-error program cannot be synthesized, even from completely accurate texts. Part (c) of the proposition is a similar result about Bc-identification. It is also interesting to note that by part (e) there is a scientist that can Bc*-identify every computable function, even from texts with an unbounded, finite number of imperfections.

		8.10 Proposition For all :

		(a) .

		(b) .

		(c) .

		(d) .

		(e) .

		Proof: Part (a). Let . It is easy to see that . An easy extension of the proof of Proposition 6.5 shows that .

		Parts (b), (c), and (d) can be shown by similar extensions of the proofs of Corollary 6.6 and Propositions 6.10 and 6.13 in Chapter 6. The proof of part (e) is left to the reader.

		Proposition 8.10 yields a hierarchy of paradigms that may be summarized as follows.

		8.11 Corollary Let . Then:

		(a) .