Page 65

		4.7 Proposition .

		Proof: By Exercise 3-1, . To show , suppose by way of contradiction that a computable scientist M identifies . Note that since for any . Therefore, by Corollary 3.25, there is a locking sequence  s 0 for M on K. Suppose that M( s 0) = i0, an index for K. Using M and  s 0 we will exhibit as recursively enumerable, contradicting the nonrecursivity of K.

		Let k0, k1, k2, . . . be some fixed, recursive enumeration of K. For every , let Tx be the text . Note that:

		4.8 (a) For all , Tx is a text for K.

		(b) For all , Tx is a text for , and .

		By 4.8a and the choice of  s 0, we have:

		4.9 Suppose that . Then F(Tx[n]) = i0 for all .

		On the other hand, from 4.8b, the fact that i0 is an index for no set of the form with , and the choice of M, we may infer:

		4.10 Suppose that . Then for some .

		Thus, 4.9 and 4.10 imply:

		4.11 For all , if and only if there is an such that .

		Now define the function by the condition that for all ,

		.

		Since k0, k1, k2, . . . is a recursive enumeration, it is easy to see that X is partial recursive. However, the domain of X is , which implies that is recursively enumerable.

		We mentioned in Section 3.3 that consideration of noncomputable scientists can clarify the respective roles of computational and information-theoretic factors in our theory. This is illustrated by comparing the collections and . By Propositions 4.7 and 3.28, no computable scientist identifies either collection. However, the reasons for the nonidentifiability differ in the two cases. presents a computable scientist with an insurmountable computational problem, whereas the computational structure of is trivial. In contrast, presents the scientist with an insurmountable informational problem, namely, that no allows the finite and infinite cases to be distinguished. No such informational problem exists for . The available information simply cannot be put to use by a recursive learning function.