Lance Fortnow, William Gasarch, Sanjay Jain, Efim Kinber, Martin Kummer, Stuart Kurtz, Mark Pleszkovich, Theodore Slaman, Robert Solovay & Frank Stephan
Annals of Pure and Applied Logic 66 (3):231-276 (1994)
| Authors |
|
| Abstract |
Most theories of learning consider inferring a function f from either observations about f or, questions about f. We consider a scenario whereby the learner observes f and asks queries to some set A. If I is a notion of learning then I[A] is the set of concept classes I-learnable by an inductive inference machine with oracle A. A and B are I-equivalent if I[A] = I[B]. The equivalence classes induced are the degrees of inferability. We prove several results about when these degrees are trivial, and when the degrees are omniscient
|
| Keywords | No keywords specified (fix it) |
| Categories | (categorize this paper) |
| DOI | 10.1016/0168-0072(94)90035-3 |
| Options |
Mark as duplicate
Export citation
Request removal from index
|
Download options
PhilArchive copy
Upload a copy of this paper Check publisher's policy Papers currently archived: 71,512
External links
- From the Publisher via CrossRef (no proxy)
- citeseerx.ist.psu.edu
(no proxy) - linkinghub.elsevier.com (no proxy)
- cs.umd.edu (no proxy)
- sciencedirect.com (no proxy)
- linkinghub.elsevier.com [2] (no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
- Sign in / register and customize your OpenURL resolver..
- Configure custom resolver
References found in this work BETA
Effective Search Problems.Martin Kummer & Frank Stephan - 1994 - Mathematical Logic Quarterly 40 (2):224-236.
Learning Via Queries in [ +, < ].William I. Gasarch, Mark G. Pleszkoch & Robert Solovay - 1992 - Journal of Symbolic Logic 57 (1):53-81.
Inductive Inference and Unsolvability.Leonard M. Adleman & M. Blum - 1991 - Journal of Symbolic Logic 56 (3):891-900.
Inductive Inference and Unsolvability.Leonard M. Adleman & M. Blum - 1991 - Journal of Symbolic Logic 56 (3):891-900.
A Proof of Beigel's Cardinality Conjecture.Martin Kummer - 1992 - Journal of Symbolic Logic 57 (2):677-681.
Citations of this work BETA
Teachers, Learners, and Oracles.Achilles Beros & Colin de la Higuera - 2019 - Notre Dame Journal of Formal Logic 60 (1):13-26.
Learning Via Queries and Oracles.Frank Stephan - 1998 - Annals of Pure and Applied Logic 94 (1-3):273-296.
The Complexity of Learning SUBSEQ(A).Stephen Fenner, William Gasarch & Brian Postow - 2009 - Journal of Symbolic Logic 74 (3):939-975.
Approximation Methods in Inductive Inference.William R. Moser - 1998 - Annals of Pure and Applied Logic 93 (1-3):217-253.
Similar books and articles
Lowness for Kurtz Randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
Infima of D.R.E. Degrees.Jiang Liu, Shenling Wang & Guohua Wu - 2010 - Archive for Mathematical Logic 49 (1):35-49.
On the Very Idea of Degrees of Truth.Timothy Cleveland - 1997 - Australasian Journal of Philosophy 75 (2):218 – 221.
Relative Enumerability in the Difference Hierarchy.Marat M. Arslanov, Geoffrey L. Laforte & Theodore A. Slaman - 1998 - Journal of Symbolic Logic 63 (2):411-420.
On the Structures Inside Truth-Table Degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees.Klaus Ambos-Spies & Ding Decheng - 1994 - Mathematical Logic Quarterly 40 (3):287-317.
Complementation in the Turing Degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
An Almost Deep Degree.Peter Cholak, Marcia Groszek & Theodore Slaman - 2001 - Journal of Symbolic Logic 66 (2):881-901.
Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
Elementary Differences Between the (2p)-C. E. And the (2p + 1)-C. E. Enumeration Degrees.I. Sh Kalimullin - 2007 - Journal of Symbolic Logic 72 (1):277 - 284.
Analytics
Added to PP index
2014-01-16
Total views
21 ( #537,621 of 2,520,895 )
Recent downloads (6 months)
1 ( #405,457 of 2,520,895 )
2014-01-16
Total views
21 ( #537,621 of 2,520,895 )
Recent downloads (6 months)
1 ( #405,457 of 2,520,895 )
How can I increase my downloads?
Downloads
