ISSN:
1432-0541
Schlagwort(e):
Key words. Inductive inference, Oracle, Degree, Recursive functions.
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/PL00013829