Page 268

		§12.5 Strictly Minimal Identification of Languages

		Identification places no constraint on the size of the final hypothesis, so long as it corresponds to the incoming function or language. More realism in this regard is easy to justify since conciseness is widely touted as a virtue of good theory. Similarly, there is reason to study small, final hypotheses in the acquisition of language by children. To the extent that developmental psycholinguists seek to characterize the form of the grammar in the child's mind, models of learning should recognize that final hypotheses cannot be arbitrarily large (assuming that the child cannot implement a Turing Machine whose states exceed the number n of synapses in the brain — or 2n if we crudely attempt to model all possible brain configurations).

		In this and the next section we consider two approaches to restricting the size of final hypotheses. We consider results only for language learning, leaving functions to the exercises. One of our main concerns is to study the dependence of size restrictions on the underlying programming system in which a scientist's conjectures are interpreted.

		A natural restriction on hypothesis size is that it be minimal. Recall from Chapter 2 that the index of a program satisfies the requirements of a Blum program size measure. The next definition introduces a paradigm in which scientists are required to converge to minimal-size hypotheses in a given programming system

		12.12 Definition

		(a) M TxtMin y -identifies L (written: ) just in case, for all texts T for L, .

		(b) .

		12.13 Proposition There is an acceptable programming system  y  such that TxtMin y  contains an infinite collection of infinite r.e. languages.

		Proof: For each y, let and let . Recall that  j  is our standard acceptable programming system. We define a programming system  y  as follows. (The  y 2i+1 case in this definition guarantees that  y  is acceptable.) For all i, define:

		.