|
|
|
|
|
|
Case 2: M does not identify N. Define a recursive function ƒ by |
|
|
|
|
|
|
|
|
We leave it to the reader to argue that ƒ defined in this way is recursive. |
|
|
|
|
|
|
|
|
Suppose Gi is a grammar (effectively obtained from i) for  . Let  . Clearly, S is an r.e. index set for some collection of languages,  . Note that S contains all languages identified by M, together with all initial segments of N. Let r be a total recursive function such that for every  ,  . To see that  , define scientist M' as follows: |
|
|
|
|
|
|
|
|
Since M does not identify N, M' identifies all that M does, together with all initial segments of N. |
|
|
|
|
|
|
|
|
A scientist that occasionally converges to an incorrect language may be termed "unreliable." |
|
|
|
|
|
|
|
|
5.40 Definition (Minicozzi [132])(a) M is reliable on L just in case for any text T for L, if  , then WM(T) = L. |
|
|
|
|
|
|
|
|
(b) M is reliable on  just in case M is reliable on each  . |
|
|
|
|
|
|
|
|
(c) M is reliable just in case M is reliable on each  . |
|
|
|
|
|
|
|
|
Thus a scientist that does not converge on any text is reliable. Only the global version of reliability yields a useful strategy. |
|
|
|
|
|
|
|
|
5.41 Definition |
|
|
|
|
|
|
|
|
It is easy to see that the collection of finite languages is identifiable by a reliable scientist. On the other hand, the obvious scientist for identifying  |
|
|
|
|
