Page 72

		exhibit an element of SD that M fails to identify. By use of the recursion theorem., we shall exhibit an index e such that:

		4.26 (a) . (b) M fails to identify  j e. (c)  j e(0) = e.

		Given such an e,  j e is the required element of SD.

		We construct  j e in stages. For each s,  s s will denote the finite initial segment of the graph of  j e defined as of the end of stage s. We will have , and we let .

		By the recursion theorem we can choose e such that  j e(0) = e, and we set  s 0 =  j e[1] (that is  s 0 = (0, e)). For remaining stages of the construction we rely on the following claim.

		4.27 Claim Given a , one can effectively find a such that and .

		Proof: (of Claim 4.27) Note that if there exists a such that one can effectively find such a by exhaustive search. Therefore it suffices to show that for each  s  there is such a . Suppose for a contradiction that for all canonical , . But then M can Ex-identify at most one function whose canonical text begins with  s . Since there are infinitely many functions in A e Z whose canonical text begins with  s , we have a contradiction to M Ex-identifying each function in A e Z.

		Here then is the construction.

		The Construction of  j e:

		Stage 0:  s 0 = (0, e).

		Stage s+1: Suppose that  s s has been defined. Find a canonical such that . (By Claim 4.27 such a can be found effectively from  s s.) Set .

		It is easy to verify that  j e satisfies 4.26 as promised.

		Theorem 4.25 shows that Ex is not closed under union. As another corollary we have:

		4.28 Theorem (Gold [80])