Extremes in the degrees of inferability

, , , , , , , , &
Annals of Pure and Applied Logic 66 (3):231-276 (1994)
  Copy   BIBTEX

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

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(94)90035-3

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 103,449

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Learning via queries and oracles.Frank Stephan - 1998 - Annals of Pure and Applied Logic 94 (1-3):273-296.
On the complexity-relativized strong reducibilities.Jari Talja - 1982 - Bulletin of the Section of Logic 11 (1-2):77-78.
Reverse mathematics and Peano categoricity.Stephen G. Simpson & Keita Yokoyama - 2013 - Annals of Pure and Applied Logic 164 (3):284-293.
Π 1 0 classes, L R degrees and Turing degrees.George Barmpalias, Andrew E. M. Lewis & Frank Stephan - 2008 - Annals of Pure and Applied Logic 156 (1):21-38.
Pa Relative to an Enumeration Oracle.G. O. H. Jun Le, Iskander Sh Kalimullin, Joseph S. Miller & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (4):1497-1525.
Degrees of belief, expected and actual.Rosanna Keefe - 2017 - Synthese 194 (10):3789-3800.
Elementary differences between the degrees of unsolvability and degrees of compressibility.George Barmpalias - 2010 - Annals of Pure and Applied Logic 161 (7):923-934.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
On a conjecture of Lempp.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (4):281-309.
Non-empty open intervals of computably enumerable sQ 1-degrees.Roland Omanadze & Irakli Chitaia - forthcoming - Logic Journal of the IGPL.

Analytics

Added to PP
2014-01-16

Downloads
47 (#491,890)

6 months
6 (#572,300)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Robert Solovay
University of California, Berkeley

Citations of this work

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.

Add more citations

References found in this work

Effective Search Problems.Martin Kummer & Frank Stephan - 1994 - Mathematical Logic Quarterly 40 (2):224-236.
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.

Add more references