|
|
|
|
|
We thus sometimes refer to TxtMex y (for acceptable programming system y ) as simply TxtMex. If the fudge factor is required to be some fixed computable function, then drastic things can occur, as the next proposition demonstrates. |
|
|
|
|
|
|
|
|
12.22 Proposition For each computable h, there is an acceptable programming system such that no infinite collection of infinite languages can be h-TxtMex ½ -identified. |
|
|
|
|
|
|
|
|
As an immediate corollary of Proposition 12.22 and Proposition 12.13 we have: |
|
|
|
|
|
|
|
|
12.23 Corollary There are acceptable programming systems, y and y , for which we have . |
|
|
|
|
|
|
|
|
Thus, TxtMin y -identification is dependent on the choice of acceptable programming system y . If we take as a given that the notions of our theory must be recursively invariant, this corollary precludes the study of TxtMin y -identification as an interesting criterion of language learning. On the other hand, it may be the case that the dependence of size-restricted paradigms on the underlying acceptable programming system is a fundamental fact about learnability rather than a mere mathematical inconvenience. |
|
|
|
|
|
|
|
|
Proof (of Proposition 12.22): Fix an which we assume without loss of generality is strictly increasing. Let denote a finite sequence uniformly formed from j and s such that: (i) and (ii) . Let M0, M1, M2, . . . be a recursive enumeration of total computable scientists along the lines of Corollary 4.16. We define |
|
|
|
|
|
|
|
|
Clearly, g is strictly increasing and recursive. For each i, define , where for each s and x, |
|
|
|
|