Page 281

		13 Beyond Identification by Enumeration

		§13.1 Gold's and Barzdins' * Conjectures

		This chapter concerns the strategy of identification by enumeration. Under this strategy a scientist has a fixed list of possible hypotheses and, at any point in time, the current conjecture is always the first hypothesis on the list that is consistent with the current data. We consider only identification of functions. A similar study can be carried out for identification of languages from informants.1 We formalize identification by enumeration as follows.

		13.1 Definition

		(a) A scientist M is an enumerator just in case there exists a recursive f such that and, for all , M( s ) = f(i), where i is the least number such that .

		(b) is identifiable by enumeration just in case there exists an enumerator M such that .

		Many collections of functions are identifiable by enumeration, as shown by the following, easy proposition.

		13.2 Proposition (Gold [80]) Each r.e. indexable class of computable functions (see Definition 5.10) is identifiable by enumeration.

		Since identification by enumeration can be viewed as a search for the correct hypothesis in a suitably generated space of hypotheses, this strategy captures an essential property of most practical systems of empirical inquiry. The naturalness of this strategy led Gold [80] to conjecture that:

		Identification by enumeration is the only method of identification in the sense that each identifiable collection of functions is also identifiable by enumeration.

		1 For identification of languages from texts, it can be shown that identification by enumeration is not a very powerful strategy, as even the class is not identifiable by enumeration.