|
|
|
|
|
|
Thus presenting simple sentences first and difficult ones later amounts to presenting the text in increasing order. We call such texts ''ascending." By convention, we order  thus: # < 0 < 1 < 2 < · · ·. |
|
|
|
|
|
|
|
|
8.27 Definition A text T over natural numbers is ascending just in case T is nondecreasing as a function from N to  . A text G over pairs of natural numbers is ascending just in case p 1 ° G is nondecreasing where, for all x and y, p 1( (x, y) ) = x. |
|
|
|
|
|
|
|
|
Consider the identification of functions on perfect text (i.e., containing no noise or omissions). It is important to see that presenting such texts in ascending order does not augment the family of identifiable collections of functions. This is because any perfect text for a function can be gradually and effectively converted into an ascending text for the same function (see Exercise 8-30 for details). The present section will therefore limit itself to language learning. |
|
|
|
|
|
|
|
|
8.28 Definition Let  . |
|
|
|
|
|
|
|
|
(a) We say that M AscTxtExa-identifies L (written:  ) just in case for all ascending texts T for L,  and WM(T) =a L. |
|
|
|
|
|
|
|
|
(b)  . |
|
|
|
|
|
|
|
|
(c) AscTxtBca is defined similarly. |
|
|
|
|
|
|
|
|
8.29 Proposition  . |
|
|
|
|
|
|
|
|
Proof: Consider the following collection of languages: |
|
|
|
|
|
|
|
|
 . |
|
|
|
|
|
|
|
|
We leave it to the reader to show that  . We argue that  . Let Gram be a recursive function such that for all finite sets D, WGram(D) = D. Let iN be an index for N. Now, for each s , define: |
|
|
|
|
|
|
|
|
It is easy to verify that M AscTxtEx-identifies  . |
|
|
|
|
