Page 137

		index pi for which . (Recall that is the finite function with graph content( s ).) Clearly, each of the uncanceled indexes makes only up to n errors of commission. For each uncanceled pi, let Epi denote the set of these points for which it can be detected in steps that pi makes an error of commission. More precisely, .

		Now, for each uncanceled pi, let qi be an index of a program that behaves exactly like the program with index pi but is patched to agree with  s  on arguments in Epi. To be precise, qi is defined as follows:

		Finally, let p be an index of a program formed from each of these qi's (derived from the uncanceled pi's) whose behavior is described as follows. The program with index p on any input y simulates each of the programs with indexes qi's on input y and outputs the same value as the (lexicographically least) qi, which converges first. M' on input  s  outputs p.

		We now argue that . Let . Then any index q output infinitely often by M on f is such that  s q =n f. Choose m0 to be so large that the following hold:

		1. If program q is ever output by M on f, then q has been output at least once by M on f[m0], that is, .

		2. If, for some , we have , then q is cancelled by M' after it has seen f[m0].

		3. For each that is never cancelled, we have that q's at most n convergent anomalies (if any) are discovered in steps, and these anomalies are all less than m0.

		Clearly, such an m0 exists. Also, after M' has seen f[m0], M' performs no new cancelations. Hence, in the limit M' on f outputs an index p that simulates a collection of indexes qi, none of which makes an error of commission and at least one of which makes no more than n errors of omission. Hence,  j p =n f.

		A proof of the a = * case can be worked out by modifying the above argument. The modification is based on the following observation. For the a = * case, the main problem arises in determining when a program has made enough convergent errors (so that it can be cancelled). For this, the machine M', upon seeing f[m], cancels a program, p, just in case it can be determined in steps that p makes more convergent errors on inputs