When oracles do not help
Theodore A. Slaman, Robert M Solovay · Conference on Learning Theory · 1991
We study the effect of allowing an inductive inference machine access to an oracle. Specifically, we resolve the question (raised by Gasarch) of exactly which oracles increase learning power. In [7] it was shown that if A is 1-generic and A T K then access to oracle A does not increase learning power. Here we show that these are the only such oracles, i.e., we show that the following two statements are equivalent conditions on the non-recursive set A : (1) access to A does not increase learning power (i.e., EX = EX A ), (2) A is 1-generic and A ≥ T K. The proof uses a (rather complex) finite injury priority argument.