Page 73

		§4.3.3 Finding Unidentified Functions

		For this subsection, let M0, M1, . . . be an indexing of total computable scientists as in Corollary 4.23. Now, Theorem 4.28 states that for every computable scientist M, there is such that M does not identify f. But can an index for such an f be found effectively from an index for M? An affirmative answer to this question would imply the existence of a total recursive such that:

		4.29 (a) for all , , and

		(b) Mi does not identify  j h(i).

		However, we now show:

		4.30 Proposition There is no total recursive that satisfies the conditions in 4.29.

		Proof: Suppose by way of contradiction that there is such an h. Then by the recursion theorem there is an e such that for all  s , Me( s ) = h(e), Clearly, Me identifies  s h(e), a contradiction.

		Proposition 4.30 shows that no evil demon of a mechanical nature can examine the internal program of a given scientist and then select a function that the scientist fails to identify. On the other hand, the demon can map an arbitrary scientist's program into a different conundrum, described by the following proposition.

		4.31 Proposition There is a total recursive function such that for all :

		(a) Wh(i) contains exactly one index for a total function, say, j (W>h(i) may or may not contain indexes for partial functions);

		(b) Mi does not identify  j j; and

		(c)  j j(0) = i.

		Clause (c) means that  j j "names" the scientist Mi for which Wh(i) has been constructed (this property of h will be used later).

		Proof: Let be given. We describe, in stages, a procedure that uses Mi to enumerate the graphs of functions (in canonical order). Although many graphs will be initiated, only one will be extended indefinitely; the others will terminate after some finite initial segment. Mi will fail to identify the unique total function to be enumerated. Our construction will be uniformly effective in i and thus constitutes the witness h to