Page 239

		10.36 Proposition Suppose . Then .

		We next show that allowing an extra error in the final inferred program cannot, in general, be compensated by the best Uap-type additional information.

		10.37 Proposition

		(a) For all , .

		(b) .

		Proof: For each , define

		Also, for each , define . Observe that for all ,

		We leave it as exercise to show that the proposition follows from the above observation together with results from Section 6.1.1.

		The previous three results imply the following corollary, which reveals the complete relationship between UapdExa and ApdExa for various values of a and d. The proof of the corollary is left to the reader.

		10.38 Corollary Let a, and d1, .

		(a) .

		(b) .

		(c) For all , .

		In the paradigms considered above, partial explanations do not contradict the function being learned. There is no reason to believe, however, that the state-of-the-art explanation available to a scientist is necessarily free of errors of commission. A natural, and currently open, line of further investigation is to consider approximations that are correct on a set of certain density and either undefined or incorrect off that set.