Page 55

		available to a scientist up to a given moment of her inquiry. In particular, the initial segment T[n] of text T is the evidential position at moment n of a scientist working on T. A scientist is any function — partial or total, computable or noncomputable — from the set of all such evidential positions to the set N of (indexes for) grammars. For a scientist F to identify a collection of languages, it must be the case that for every text T for any language , there is grammar i for L such that F(T[n]) = i for all but finitely many .

		Identification in the foregoing sense is a nontrivial concept inasmuch as there exist rich, identifiable collections of languages as well as rich unidentifiable ones. A necessary and sufficient condition for identifiability is given in Theorem 3.26.

		There are several respects in which the foregoing paradigm is inadequate as a model of language acquisition by children. To take just one example, children are unlikely to remember the entire record of sentences ever addressed to them. We are thus led to define formal scientists who operate under memory restrictions. It was shown in Section 3.7 that such scientists have less scientific competence than their memory-unlimited counterparts. Later chapters will consider other modifications to the language identification paradigm.

		The second major paradigm introduced in this chapter takes total recursive functions as the class of possible realities. Hypotheses are construed as (indexes for) programs to compute these functions. The information made available to scientists about a given function f is conceived as an enumeration of the graph of f. The criterion of successful inquiry is a straightforward adaptation of that defined for language identification.

		Function identification has a trivial aspect in the sense that there is a single scientist that can identify the entire class of recursive functions. We shall see in the next chapter, however, that this scientist cannot itself be computable.

		Similarly to language identification, scientists working under memory limitation suffer from a reduced ability to identify collections of recursive functions.

		§3.12 Exercises

		3-1 Let be given. Show that is identifiable.

		3-2 Let be any collection of nonempty, pairwise disjoint, recursive subsets of N. Show that is identifiable.

		3-3 Prove the following facts.