A Good Oracle Is Hard to Beat

A well-known result of Sacks [24] states that if A is nonrecursive, then the set {B : A ≤ _T B} has measure zero. Thus, from a measure-theoretic perspective, a ``good' (i.e., nonrecursive) oracle is hard to beat in the partial order of Turing degrees. We show that analogous results hold for the standard notions of inductive inference, as well as for the notions of approximate inference. Received January 25, 1997; revised March 10, 1997, June 3, 1997, and June 15, 1997.