|
|
|
|
|
|
9.7 Definition Suppose t > 1. |
|
|
|
|
|
|
|
|
(a) Nt denotes {0, 1, 2, . . ., t - 1}, the set of possible outcomes of a flip of a t-sided coin. |
|
|
|
|
|
|
|
|
(b) For each  ,  denotes the collection of all length k sequences of possible flips of a t-sided coin.  denotes  , the collection of all finite t-ary sequences. (A typical variable for elements of  is r ). |
|
|
|
|
|
|
|
|
(c)  denotes the collection of infinite sequences of flips of a t-sided coin. Elements of  are called oracles for a t-sided coin or t-ary oracles. O will range over oracles. |
|
|
|
|
|
|
|
|
We treat a t-ary oracle somewhat like a text for the finite language Nt and carry over notation for texts to oracles as follows. |
|
|
|
|
|
|
|
|
9.8 Definition Let t > 1. |
|
|
|
|
|
|
|
|
(a) Let  . The length of r is denoted by  For  , the nth member of r is denoted by r (n), and the initial sequence of length n in r is denoted by r [n]. |
|
|
|
|
|
|
|
|
(b) Let O be a t-ary oracle. Then, the nth member of O is denoted O(n). The initial finite sequence of O of length n is denoted O[n]. |
|
|
|
|
|
|
|
|
Let P be a probabilistic scientist equipped with a t-sided coin,  , and let  be given. Then P r ( s ) denotes the output (if any) of P on s after  or fewer coin flips are read from r . That is, the outcome of P's first coin flip (if it occurs) is r (0), the outcome of the second flip is r (1), and so on. If P tries to perform more coin flips than  in responding to the evidential state s , then P r ( s ) is undefined. Let O be an oracle. Then PO( s ) denotes PO[n]( s ), where n is the least number, if any, such that PO[n]( s ) is defined; if no such n exists, then PO( s ) is undefined. Finally, PO(f) is the limit of PO(f[m]) (as  ) as usual. If  to an index for f, we say that PO Ex-identifies f. Intuitively, the probability of P Ex-identifying f will be the same as the probability of { Ex-identifies f}. We formalize this notion in Section 9.4.2 after reviewing some basic probability theory in the next subsection. |
|
|
|
|
|
|
|
|
Convention: For the rest of this chapter we shall assume that probabilistic scientists are total in the sense that, for each P, O, and s , there is an n such that PO[n]( s ) is defined. It can be easily verified that this assumption does not affect the generality of the results discussed below. |
|
|
|
|
|
|
|
|
The subject of identification by probabilistic scientists was first studied by Freivalds [63] and by Pitt [149, 150]. Our presentation closely follows that of Pitt. |
|
|
|
|
