|
|
|
|
|
|
(a) M is said to be accountable on L just in case, for every s with  , we have that WM( s ) - content( s ) is nonempty. |
|
|
|
|
|
|
|
|
(b) M is said to be accountable on  just in case M is accountable on each  . |
|
|
|
|
|
|
|
|
(c) M is accountable just in case M is accountable on each  . |
|
|
|
|
|
|
|
|
Thus the hypotheses of accountable learners are always subject to further confirmation. The next definition considers the global and the class versions of accountability. |
|
|
|
|
|
|
|
|
(a)  . |
|
|
|
|
|
|
|
|
(b)  . |
|
|
|
|
|
|
|
|
It is easy to see that  and that no accountable scientists can identify any finite language. This suggests the following question. If attention is restricted to infinite languages, are there identifiable collections of languages that cannot be identified by class-accountable scientists? The next proposition provides an affirmative answer. |
|
|
|
|
|
|
|
|
5.16 Proposition There is an  such that every  is infinite. |
|
|
|
|
|
|
|
|
Proof: Recall from Chapter 2 that for each L and x,  . Let  . |
|
|
|
|
|
|
|
|
Clearly,  . |
|
|
|
|
|
|
|
|
Suppose by way of contradiction that a class-accountable scientist M identifies  . By Kleene's recursion theorem (Theorem 2.3) there exists an index e such that We may be defined in stages s = 0, 1, 2, . . ., as below. For each s,  denotes the finite portion of We enumerated as of the beginning of stage s. In each stage s, we determine a number ys+1, finite sets Ss+1 and Xs+1, and sequence s s+1. We begin with  ,  ,  , s 0 chosen so that content( s 0) = S0, and  . Go to stage 0. |
|
|
|
|
|
|
|
|
Begin ( Stage s )
Search for the least  , if any, such that  . |
|
|
|
|
