Page 52

		3.43 Theorem is identifiable.

		Proof: The key property of is this. Suppose that f, and . Then there are such that , and . It follows that if G is a text for f, there is such that the information in G[n] shows that G is not for g.

		Now define scientist F as follows. For all , let F( s ) be the least such that:

		(a)  j i is total; and

		(b) .

		By Lemma 3.40, F is well defined.

		Thus, F guesses the first member of that is consistent with  s . Our preceding remarks show that, given a text G for , F will eventually conjecture and stay with the least index for f, having verified that G is not a text for any function with smaller index.

		Although some scientist identifies , there is no guarantee that a scientist with various special properties can do so as well. In particular, we shall see in the next chapter that no computable scientist has this ability. Memory limitation also prevents identification of , even by scientists representing noncomputable mappings of SEG to N. We examine this matter now; it is the last topic to be discussed in the present chapter.

		§3.10.1 Memory Limitation for Function Identification

		The following definitions parallel those given in Section 3.8 for the language case.

		3.44 Definition Let be given.

		(a) The result of removing the last pair in  s  is denoted by  s -; if , then .

		(b)  — i.e., the last pair in  s  — is denoted by  s last; if , then  s last is undefined.

		3.45 Definition Scientist F is memory limited just in case for all of positive length, if and , then .

		We shall now define a simple collection of functions that is identified by no memory-limited scientist. For this purpose, the following standard terminology is helpful. Recall