|
|
|
|
|
|
Part (b). Suppose i* = MinGram j (L). Then, by our choice of i* and Claim 12.17(a), we have that, for all (i, 0) < (i*,0),  . Since  , we have that  and, hence, for some  , we must have  . Thus, it follows that j > 0, although we may well have (i, j) < (i*, j*). |
|
|
|
|
|
|
|
|
Part (c). Suppose L is infinite. Suppose by way of contradiction that for some  we have r(i', j') = MinGram y (L). By part (a) and the ordering on A, it follows that (i', j') < (i, j). By the argument for part (b) it must be the case that j' > 0. Since L = Wr(i', j') is infinite, it follows from Claim 12.17(b) that  . Let p = h (i', j'). By Claim 12.17(c) we have that, for infinitely many n, g(p, n) = p. Hence, by Claim 12.17(d), Wp = W h (i', j') = Wr(i', j'), which by hypothesis is  . So, by Claim 12.16, we must have h (i', j') p = iL. But since (i', j') < (i, j), this contradicts our choice of (i, j) as the least element of A with h (i, j) = iL. Hence, part (c) follows. |
|
|
|
|
|
|
|
|
It is convenient to introduce a y -analog of Wi, s. Towards this end fix p h , some j -program for h . Then, for each  and  , define |
|
|
|
|
|
|
|
|
By Claim 12.17 we have that, for all  ,  , and, for all s,  . Moreover, deciding whether  is recursive in i, j, s, and x. |
|
|
|
|
|
|
|
|
Now let M be a scientist that TxtEx-identifies  . We define a scientist M' as follows. |
|
|
|
|
|
|
|
|
Program for M' on s .
Let k = M( s ),  , and p = g(k, n).
Find the least  , if any, such that  and  .
If no such (i, j) is found, then output 0 and halt.
If such an (i, j) is found, then:
 Find the least  , if any, such that  and  .
If no such an (i', j') was found, output r(i, j).
If such an (i, j) was found, output r(i', j'). |
|
|
|
|
