|
 |
|
|
|
|
Henceforth, make j p(s) behave exactly like j p(0) on arguments greater than x'. |
|
|
|
|
|
|
|
|
( This ensures that p(s) is an (m + 1)-error index for j p(0). ) |
|
|
|
|
|
|
|
|
Go on to stage s + 1. |
|
|
|
|
|
|
|
|
Consider the following two cases. |
|
|
|
|
|
|
|
|
Case 1: Infinitely many stages are executed. In this case, let f = j p(0). It is clear that  and everything in its range is either an index for f or an (m + 1)-error index for f. Hence,  . But, for each s, there is a s such that  and M's conjecture on s makes at least m + 1 mistakes in computing f. Hence,  . |
|
|
|
|
|
|
|
|
Case 2: Some stage s starts but never terminates. In this case,  and, for all but finitely many x, t p(s)(x) = p(s). Let f = t p(s). Clearly,  . Also, for each s such that  , M's conjecture on s computes only a finite function because the search for y0, . . ., ym in step b fails. Hence,  . |
|
|
|
|
|
|
|
|
The proof of part (b) can be worked out on lines similar to the proof of Corollary 6.6. |
|
|
|
|
|
|
|
|
Bc* is the weakest criterion of success considered so far in our discussion. Although further liberalization could be envisioned, the following proposition shows that no further weakening is necessary. |
|
|
|
|
|
|
|
|
6.15 Proposition (L. Harrington cited in Case and Smith [35])  . |
|
|
|
|
|
|
|
|
Proof: Let MH be a scientist which, on input s , outputs a program with index e s , where, for each x, |
|
|
|
|
|
|
|
|
Fix an arbitrary  . We show that MH Bc*-identifies f. Let p0 be the least index for f. Choose n0 so large that (a)  and (b) for each  ,  . Claim: For each  ,  . To see this, take  and consider an  . By our choices of n0, n, xn, and x it follows that, on input x, p0 is the p found in clause (i) of the definition of  , and hence, |
|
|
|
|
|
|
|
|
Therefore, the claim follows. Thus, MH Bc* identifies f. |
|
|
|
|
