|
|
|
|
|
|
§11.4 Language Identification by Oracle Scientists |
|
|
|
|
|
|
|
|
We now consider the identification of languages by oracle scientists. The next definition extends the TxtEx paradigm to identification by oracle scientists. We again let the reader verify that notation about computable scientists converging on a text carries over to oracle scientists. |
|
|
|
|
|
|
|
|
11.13 Definition Let  . |
|
|
|
|
|
|
|
|
(a) An oracle scientist M OATxtEx-identifies L (written:  ) just in case, for each text T for L, we have  and  . |
|
|
|
|
|
|
|
|
(b)  |
|
|
|
|
|
|
|
|
As was the case with functions, the first natural question is whether there are omniscient oracles, that is, whether there is an A such that  . In contrast to the function case, in this setting we obtain a negative answer to this question. |
|
|
|
|
|
|
|
|
11.14 Proposition For all A,  . |
|
|
|
|
|
|
|
|
Proof: As the reader can check, Proposition 3.22 extends to oracle scientists. Hence, Corollary 3.28 implies the present proposition. |
|
|
|
|
|
|
|
|
Since no oracle suffices to make e identifiable, an interesting question is whether employing a more powerful oracle in the arithmetic hierarchy yields extra learning power. The following result provides a sufficient condition for an oracle B allowing the identification of at least one collection of languages that cannot be identified using oracle C. Recall that  . |
|
|
|
|
|
|
|
|
11.15 Proposition Suppose A0, A1, A2, . . . is a sequence of subsets of N such that  . Let  and let C be any set such that  . Then, there is an  . |
|
|
|
|
|
|
|
|
For an example of a sequence of sets A0, A1, A2, . . . satisfying the proposition's hypothesis, take  for each  . Our proof of the above result relies on the following lemma, which is a relativization of the locking sequence lemma (Theorem 3.22). The proof of the lemma is left to the reader. |
|
|
|
|
|
|
|
|
11.16 Lemma Suppose M OATxtEx-identifies L. Then there is a s such that: |
|
|
|
|
|
|
|
|
(a)  |
|
|
|
|
