Extremes in the degrees of inferability

Annals of Pure and Applied Logic 66 (3):231-276 (1994)

Authors
Robert Solovay
University of California, Berkeley
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
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 45,662
Through your library

References found in this work BETA

Effective Search Problems.Martin Kummer & Frank Stephan - 1994 - Mathematical Logic Quarterly 40 (2):224-236.
A Proof of Beigel's Cardinality Conjecture.Martin Kummer - 1992 - Journal of Symbolic Logic 57 (2):677-681.
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.

Add more references

Citations of this work BETA

Learning Via Queries and Oracles.Frank Stephan - 1998 - Annals of Pure and Applied Logic 94 (1-3):273-296.
Approximation Methods in Inductive Inference.William R. Moser - 1998 - Annals of Pure and Applied Logic 93 (1-3):217-253.
The Complexity of Learning SUBSEQ(A).Stephen Fenner, William Gasarch & Brian Postow - 2009 - Journal of Symbolic Logic 74 (3):939-975.

Add more citations

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.
On the Structures Inside Truth-Table Degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
Bi-Isolation in the D.C.E. Degrees.Guohua Wu - 2004 - Journal of Symbolic Logic 69 (2):409 - 420.
Jump Operator and Yates Degrees.Guohua Wu - 2006 - Journal of Symbolic Logic 71 (1):252 - 264.
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.

Analytics

Added to PP index
2014-01-16

Total views
15 ( #581,538 of 2,280,770 )

Recent downloads (6 months)
5 ( #248,035 of 2,280,770 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature