Page 67

		Let us now consider how such hypotheses interact with each other. Consider two subsets A and B of scientists. Exercise 4-3 shows that it is possible for a collection of languages to be identified by some member of A and by some member of B without being identified by any member of . Thus, the constraint on comparative grammar offered by two hypotheses about children's learning mechanisms cannot be conceived as the intersection of the classes of collections of languages that each permits. This point is illustrated by memory limitation and computability.

		4.14 Proposition There is such that:

		(a) ;

		(b) some memory limited scientist identifies ; and

		(c) no computable, memory limited scientist identifies .

		Proof: Let be a fixed, nonrecursive r.e. set, let , and define for all , , . The collection will witness the proposition.

		We give informal proofs of parts (a) and (b) of the proposition. A computable scientist M that identifies works as follows. On incoming text T, M conjectures L until some pair appears in T; then M conjectures Ln forever unless appears or has already appeared in T, in which case M conjectures forever. Note that M is computable but not memory limited. A memory limited scientist F' that identifies does the following on T. F' conjectures L until either appears in T for any , or appears in T for . In the former case, F' conjectures Ln forever unless appears in T, in which case F' conjectures forever. In the latter case, F' conjectures forever. It can be seen that F' is memory limited but not computable (since F' determines whether for nonrecursive A).

		To prove part (c) of the proposition, suppose for a contradiction that some computable, memory limited scientist M identifies . Let  s  be a locking sequence for M on L. This implies that for every , . It follows that for some , , for if this were not the case it would be easy to show (since M is computable) that is r.e., and this would contradict the choice of A. Fix such an m, and let S be any enumeration of L. We define two texts, T and T' thus.