|
|
|
|
|
|
are referred to as oracle machines. In this section we consider identification by scientists that have access to such a membership oracle. A membership oracle for  may be thought of as an infinite sequence of 0's and l's whose bits appear in the sequence |
|
|
|
|
|
|
|
|
c A(0), c A(1), c A(2), . . . , |
|
|
|
|
|
|
|
|
where XA denotes the characteristic function of A. We use A to denote both the set and its membership oracle. |
|
|
|
|
|
|
|
|
An oracle scientist may be construed as a computable scientist with the added ability to consult an oracle for membership queries. More concretely, an oracle scientist may be viewed as a Turing machine with an extra read-only tape, called the oracle tape, upon which the membership oracle for some set A is written. This oracle Turing machine behaves like a usual Turing machine except that its actions may also depend on the content of the oracle tape. In this chapter we let M, with or without decorations, range over oracle, as well as ordinary, scientists. It will always be clear from context whether M is intended as an ordinary or oracle scientist. We denote a scientist n equipped with an oracle A as MA, and MA( s ) denotes the conjecture of M with access to a membership oracle for A on evidential state s . |
|
|
|
|
|
|
|
|
The next section concerns function identification by oracle scientists. Section 11.4 discusses language identification in this context. |
|
|
|
|
|
|
|
|
§11.3 Function Identification by Oracle Scientists |
|
|
|
|
|
|
|
|
Suppose M is an oracle scientist and  . If the sequence of hypotheses issued by MA on  corresponds to an Ex-identification of f, then MA is said to OAEx-identify f, or alternatively, as defined below, M is said to OAEx-identify f (Gasarch and Pleszkoch [76]). We formalize this paradigm in the following definition, and leave it to the reader to check that the notion of convergence of a computable scientist on a function can be easily adapted for convergence of an oracle scientist on a function. |
|
|
|
|
|
|
|
|
11.1 Definition (Gasarch and Pleszkoch [76]) Let  . |
|
|
|
|
|
|
|
|
(a) M, OAEx-identifies f (written  ) just in case. and  . |
|
|
|
|
|
|
|
|
(b)  . |
|
|
|
|
