Please use this identifier to cite or link to this item:
https://scholarbank.nus.edu.sg/handle/10635/115724
| Title: | Extremes in the degrees of inferability | Authors: | Fortnow, L. Gasarch, W. Jain, S. Kinber, E. Kummer, M. Kurtz, S. Pleszkovich, M. Slaman, T. Solovay, R. Stephan, F. |
Issue Date: | 5-Apr-1994 | Citation: | Fortnow, L.,Gasarch, W.,Jain, S.,Kinber, E.,Kummer, M.,Kurtz, S.,Pleszkovich, M.,Slaman, T.,Solovay, R.,Stephan, F. (1994-04-05). Extremes in the degrees of inferability. Annals of Pure and Applied Logic 66 (3) : 231-276. ScholarBank@NUS Repository. | Abstract: | Most theories of learning consider inferring a function f from either (1) observations about f or, (2) 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 (i.e., the set of recursive function is learnable). © 1994. | Source Title: | Annals of Pure and Applied Logic | URI: | http://scholarbank.nus.edu.sg/handle/10635/115724 | ISSN: | 01680072 |
| Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.