Page 186

		(d) .

		Proof: Given k texts G1, G2, . . . , Gk, form a text G such that .It is easy to see that, if at least of the k texts are *-noisy (*-incomplete, *-imperfect, accurate) for f, then so is G. The proposition follows.

		8.45 Proposition Let j and be such that and let . Then:

		(a) .

		(b) .

		(c) .

		Proof: We first introduce a technical notion. Let P be a finite set of programs. Define program Unify(P) as follows.

		Begin (  j  Unify(P) ) On input x: Search for an such that . If and when such an i is found, output  j i(x) for the first such i found.

		End (  j  Unify(P) )

		Proof of Part (a). Let M NaEx-identify C. We show how to Ex-identify from k texts, G1, G2, . . . , Gk, at least j of which are a-noisy for f.

		So suppose , and G1, G2, . . . , Gk are k texts such that at least j of them are a-noisy for f.

		First we claim that there are distinct i1, i2, . . . , ij such that,

		(A) for , and

		(B) for each l, , there is no x such that . This is so, since if we choose i1, i2, . . . , ij to be such that , . . . , are good, then (A) and (B) above are satisfied.

		Note that, given texts G1, G2, . . . , Gk, one can find, in the limit, distinct i1, i2, . . . , ij satisfying (A) and (B) above. So let M' be a scientist that, in the limit, finds such i1, i2, . . . , ij and outputs Unify(P), where .

		Since and , there is a such that  j p = f. This, along with (B) above, implies that Unify(P) is a program for f; hence part (a) follows.

		Parts (b) and (c) can be proved similarly.