Page 66

		§4.2.3 A Comprehensive, Identifiable Collection of Languages

		The languages comprising and are computationally transparent, yet Corollaries 3.28 and 3.29 show that neither is identifiable. In conjunction with Proposition 4.7, these facts might encourage the belief that TxtEx contains only computationally impoverished subsets of  e . The purpose of the present section is to show that this belief is mistaken. In particular, it will be seen that there is a computable scientist of simple design that identifies "nearly all" of  e . This idea is made precise by the following definition. First, recall from Chapter 2 that two languages L and L' are finite variants just in case both L - L' and L' - L are finite.

		4.12 Definition Let be given. covers  e  just in case for every there is such that L and L' are finite variants.

		Languages that are finite variants have similar computational properties. For example, if one is recursive, then so is the other, and similarly for being decidable in polynomial time, etc. Hence, if covers  e , then even the most computationally complex sets in  e  have equally complex counterparts in . Nonetheless:

		4.13 Proposition (Wiehagen [196]) There is such that covers  e .

		Proof: By Exercise 2-3, one can construct, for each , an such that:

		(a) L and L' are finite variants; and

		(b) L' = Wx where x is the smallest member of L'.

		It follows that covers  e . Now define scientist M by the condition that for all , M( s ) = the least It is evident that M is computable and identifies .

		§4.2.4 Computability in the Context of Other Constraints

		In Section 3.7 we noted that a model of language acquisition places greater constraint on theories of comparative grammar to the extent that it succeeds in locating the language acquisition mechanism of children in a narrow subset of the class of all scientists. One such subset was discussed, namely, memory-limited scientists, and it was shown that there are identifiable collections of languages that are not identified by any memory-limited scientist. The computable scientists constitute another subset of the same nature, as shown by Corollary 4.5.