Page 143

		s . If the number of distinct indexes output by M on  s  is less than n, then Lastn(M,  s ) is the entire set of indexes output by M on  s .

		For each , define the collection of languages

		.

		It is easy to verify that . It remains to show that .

		Fix an arbitrary scientist M. By a padded version of the (n + 1)-ary recursion theorem (Theorem 2.5), there are distinct programs e0, el, · · ·, en defining r.e. sets , , . . ., , respectively, which are constructed as follows. All of the will be in and one of the will witness that M fails to . It will thus follow that .

		Let . Go to stage 0.

		Begin ( Stage s ) For each , enumerate <s, e0> into . ( This guarantees in Case 1 below that the are all infinite. ) Set . Dovetail between a and b below until, if ever, the search in b succeeds. a. enumerate <x, ej> into for each . Endfor b. Search for a extending  s  such that (i) and (ii) . If and when the search in b succeeds, then: Let . For each , enumerate S into . Choose  s s+1 to be an extension of such that content( s s+1) = S. Go on to stage s + 1.

		End ( Stage s )

		We have the following two cases.