|
|
|
|
|
(c.2) . |
|
|
|
|
|
|
|
|
We illustrate the above definitions with a few examples. Let , where E denotes the set of even numbers and O denotes the set of odd numbers. Let e and o be indexes for E and O, respectively. Let scientist M, fed s , emit e if the majority of content( s ) are even; o otherwise. It is easy to see that M identifies on *-noisy texts, *-incomplete texts, and *-imperfect texts. In contrast, there are two-clement classes of languages that are not identifiable on 1-noisy texts. For example, let , , where , and let T be some text for L'. Then T is also a 1-noisy text for both L and L'. Since , no scientist M converges on T to an index for both languages. It is also easy to verify that . |
|
|
|
|
|
|
|
|
The above example demonstrates that inaccuracies in texts affect identifiability. The next proposition highlights the disruptive effects of 1-noisy texts. The reader is referred to the exercises for a discussion of identification from noisy texts without the computability restriction on scientists. |
|
|
|
|
|
|
|
|
8.7 Proposition There is a collection of infinite, pairwise disjoint r.e. languages in TxtEx - N1TxtEx |
|
|
|
|
|
|
|
|
Proof: For each m define . It is easy to verify that no scientist N1TxtEx-identifies both Ln,m and Ln,m' for . Now let h be any permutation of N, and define . It is easy to see that for any permutation h, . But if , and if M N1TxtEx-identifies , then M falls to N1TxtEx-identifies . Since there are only N0 many scientists and many permutations of N, there must be a permutation h such that no scientist N1TxtEx-identifies . |
|
|
|
|
|
|
|
|
The next proposition parallels Proposition 8.7 and highlights the disruptive effects of identification from 1-incomplete texts. A proof analogous to the above suffices; details are left to the reader. |
|
|
|
|
|
|
|
|
8.8 Proposition There is a collection, , of infinite, pairwise disjoint r.e. languages, such that . |
|
|
|
|
|
|
|
|
Paradigms for function learning may be defined analogously to the language case. |
|
|
|
|
|
|
|
|
8.9 Definition Let a, and scientist M be given. |
|
|
|
|