ML Anthology

When Oracles Do Not Help

Theodore A. Slaman, Robert Solovay
COLT 1991 pp. 379-383
doi:10.1016/B978-1-55860-213-7.50038-9 /colt/1991/slaman1991colt-oracles/

Abstract

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 = EXA ), (2) A is 1-generic and A ≥T K. The proof uses a (rather complex) finite injury priority argument.

COLT Semantic Scholar

Cite

Text

Slaman and Solovay. "When Oracles Do Not Help." Annual Conference on Computational Learning Theory, 1991. doi:10.1016/B978-1-55860-213-7.50038-9

Markdown

[Slaman and Solovay. "When Oracles Do Not Help." Annual Conference on Computational Learning Theory, 1991.](https://mlanthology.org/colt/1991/slaman1991colt-oracles/) doi:10.1016/B978-1-55860-213-7.50038-9

BibTeX

@inproceedings{slaman1991colt-oracles,
  title     = {{When Oracles Do Not Help}},
  author    = {Slaman, Theodore A. and Solovay, Robert},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1991},
  pages     = {379-383},
  doi       = {10.1016/B978-1-55860-213-7.50038-9},
  url       = {https://mlanthology.org/colt/1991/slaman1991colt-oracles/}
}