|
|
|
|
|
Finally, choose an be such that neither (n, 0) nor (n, 1) is in , and let be the characteristic function for DU{n}. We will show that F fails to identify some text for g'. |
|
|
|
|
|
|
|
|
By 3.48(c) and the fact that , we have: |
|
|
|
|
|
|
|
|
3.50 . |
|
|
|
|
|
|
|
|
From 3.50 and the memory-limitation of F, we have: |
|
|
|
|
|
|
|
|
3.51 . |
|
|
|
|
|
|
|
|
By the choice of s ', 3.49 and 3.51 imply: |
|
|
|
|
|
|
|
|
3.52 . |
|
|
|
|
|
|
|
|
On the other hand, by 3.51 and memory-limitation, we have: |
|
|
|
|
|
|
|
|
3.53 . |
|
|
|
|
|
|
|
|
We deduce from 3.49, 3.52, and 3.53: |
|
|
|
|
|
|
|
|
3.54 . |
|
|
|
|
|
|
|
|
Let G' be an enumeration of all the pairs of g' except for (n, 1) (hence , for all ). Let G be the text that begins with and finishes with G'. Then it is easy to verify that G is a text for g'. However, by 3.54, F converges on G to an index for , hence fails to identify g'. |
|
|
|
|
|
|
|
|
It is easy to verify that every singleton collection of functions is identifiable by a memory-limited scientist, and that the collection of characteristic functions for finite sets is similarly identifiable. So Proposition 3.46 implies that the family of subsets of that are identifiable by a memory-limited scientist is not closed under finite union. |
|
|
|
|
|
|
|
|
The present chapter defined and investigated two paradigms of scientific discovery that are fundamental to our work. The paradigms introduced in later chapters may be conceived as elaborations or revisions of these two. |
|
|
|
|
|
|
|
|
The first paradigm takes languages (that is, r.e. sets of numbers) as possible realities, and grammars as scientific hypotheses. The data generated by a language is represented by a text, which is essentially an enumeration of the numbers in the language. Each finite, initial segment of a text is an "evidential position," summarizing all the information |
|
|
|
|