ISSN:
1432-0541
Keywords:
Key words. Inductive inference, Oracle, Degree, Recursive functions.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00013829
Permalink