|
|
|
|
|
Intuitively, a child is memory-limited if her conjectures arise from the interaction of the current input sentence with the latest grammar that she has formulated and stored. This grammar, of course, may provide information about all the sentences seen to date. |
|
|
|
|
|
|
|
|
To illustrate, Ffinite defined in 3.9a is memory-limited. To see this, suppose that and . These equalities imply that so . In view of Proposition 3.15, this proves: |
|
|
|
|
|
|
|
|
3.33 Proposition Ffinite is memory-limited, and hence some memory limited scientist identifies . |
|
|
|
|
|
|
|
|
The foregoing example shows that memory limitation is not uniformly fatal, even for nontrivial problems. Nonetheless, memory limitation places genuine restrictions on the identifiable collections of languages, as shown by the next proposition. |
|
|
|
|
|
|
|
|
3.34 Proposition There is an identifiable collection of languages that is not identified by any memory-limited scientist. |
|
|
|
|
|
|
|
|
Proof: As a witness to the proposition, let consist of the language along with, for each , both the languages: |
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
It is easy to verify that is identifiable. On the other hand, suppose that memory-limited scientist F identifies L. We will show that F does not identify . By Corollary 3.25, let s be a locking sequence for F on L. Choose such that . Because , we have: |
|
|
|
|
|
|
|
|
3.35 . |
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
Then by 3.35, and . So, since F is memory-limited, . Now let S be a text obtained by omitting all instances of from a given text for L. Define: |
|
|
|
|
|
|
|
|
. |
|
|
|
|
|
|
|
|
. |
|
|
|
|