|
|
|
|
|
|
Phase a: Receive an element of the graph of f. |
|
|
|
|
|
|
|
|
Phase b: Issue an hypothesis. |
|
|
|
|
|
|
|
|
9.18 Lemma (Pitt [149, 150]) Let P be a probabilistic scientist. Then there exists a nice P' such that, for each  ,  . |
|
|
|
|
|
|
|
|
§9.4.3 Infinite Computation Trees |
|
|
|
|
|
|
|
|
Let P be a nice probabilistic scientist and let  be given. The infinite computation tree for P on f, denoted  , is a record of P's behavior on all possible 2-ary oracles when P is fed the graph of f in canonical order. We describe  and its relation to probabilistic Ex-identification in this subsection. |
|
|
|
|
|
|
|
|
Convention: Throughout this subsection we will keep P and f fixed. All terminology and notation will be understood to be relative to the choice of particular P and f. When we use these terms and notation in later sections, the particular P and f we have in mind will always be understood. |
|
|
|
|
|
|
|
|
 is an infinite complete binary tree. Each node of  is labeled with an element of  . The root of  is labeled with  (the empty sequence) and, if a. node of  is labeled with r , then the node's left child is labeled  and its right child is labeled  . A node with label r represents the state of P just after phase b of round  when P is fed the graph of f in canonical order and receives r as the result of its first  coin flips; guess( r ) denotes the hypothesis issued by P in phase b of this round. We identify nodes with their labels so that when we speak of node r we mean the node in  with label r . The depth of node r is simply  . Hence, the depth of the root is 0. |
|
|
|
|
|
|
|
|
A path  in  is an infinite sequence of nodes  ,  ,  , . . . , such that, for each i,  and  extends  . (That is,  is the root and  occurs at depth i in the tree and is the parent of node  .)  will range over paths in  . There is an obvious one-to-one correspondence between paths and 2-ary oracles. By convention, when we speak of the measure of a set of paths, we will mean the measure of the corresponding set of oracles. The next definition introduces the path analog of the  . |
|
|
|
|
|
|
|
|
9.19 Definition For each node r of  ,  denotes  |
|
|
|
|
|
|
|
|
It is obvious that  corresponds to  , and, hence,  The measurable sets  will be used in computing probabilities of more interesting collections of |
|
|
|
|
