|
|
|
|
|
|
For example, it is easy to see that Ffinite reliably identifies  . |
|
|
|
|
|
|
|
|
Reliability is a useful property of scientists, since a reliable scientist never fails to signal the inaccuracy of a previous false conjecture. The signal is given by eventually changing the previous conjecture, or by producing no conjecture at all on a later input. Show, however, that reliability is an excessively strong success criterion by proving the following. |
|
|
|
|
|
|
|
|
Suppose that  is reliably identifiable. Then  . |
|
|
|
|
|
|
|
|
3-21 F identifies  confidently just in case F identifies  and F converges (to some number or other) on every text for a language in the complement of  . Show that there is identifiable  such that no scientist identifies  confidently. |
|
|
|
|
|
|
|
|
3-22 One strategy for generating conjectures is to choose the first index in some list of indexes that is consistent with the data seen so far. This strategy is known as "induction by enumeration," and is employed by the scientist in Proposition 3.43 concerning function identification. Let us now see how well induction by enumeration works in the paradigm of language identification. |
|
|
|
|
|
|
|
|
3.58 Definition (Gold [80]) A scientist  is an enumerator just in case there is total  such that for all  F( s ) = f(i), where i is the least number such that  (f need not be computable). |
|
|
|
 |
|
|
|
|
(i) some enumerator identifies  . |
|
|
|
|
|
|
|
|
(ii) some enumerator identifies  . |
|
|
|
|
|
|
|
|
(b) Given  , define  and  . Show that  is identifiable, but not by any enumerator. |
|
|
|
|
|
|
|
|
3-23 Let  be the collection of all  such that f is the characteristic function of a finite set. Let  be the collection of all  such that f is the characteristic function of a cofinite set. Show: |
|
|
|
|
|
|
|
|
(a) Some memory-limited scientist identifies  . |
|
|
|
|
|
|
|
|
b) Some memory-limited scientist identifies  . |
|
|
|
|
|
|
|
|
(c) No memory-limited scientist identifies  . |
|
|
|
|
