Extremes in the degrees of inferability
type: Item
instance of: scholarly article
title: Extremes in the degrees of inferability
zbMATH Open document ID: 0813.03026
DOI: 10.1016/0168-0072(94)90035-3
author: Lance Fortnow
author: William Gasarch
author: Sanjay Jain
author: Martin Kummer
author: Stuart A. Kurtz
author: Mark Pleszkovich
author: Theodore A. Slaman
author: Frank Stephan
author: Efim Kinber
author: Robert M. Solovay
published in: Annals of Pure and Applied Logic
publication date: 1994-05-03T00:00:00Z
review text: Formal learning theory tries to describe which classes of theories are learnable under which information presentation conditions, using a learning system with given capacities. Theories are often represented by functions. Then the question is how to infer a function \(f\) from observations about the behavior of \(f\). Usually these observations include the answers obtained from a teacher answering questions about the function. In this paper, the authors study in a more general setting the inference capacities of inference machines that also might consult colleagues, not necessarily teachers, about \(f\). Such colleagues function as oracles for the inference machine. Then the question is how to discriminate between those oracles. Two oracles are called equivalent (w.r.t. a given inference machine) if they allow the same functions to the mastered by the machine. Then some results are proven if two extreme equivalence classes are examined: What are the oracles that are of no help to the machine? And which oracles allow the learner to infer the set of all recursive functions?
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68T05
zbMATH DE Number: 550135
zbMATH Keywords: inductive inference
zbMATH Keywords: inference machines
zbMATH Keywords: oracles
zbMATH Keywords: recursive functions
reviewed by: Cees Witteveen
MaRDI profile type: Publication
full work available at URL: 0168-0072(94)90035-3
OpenAlex ID: W2064496697
cites work: Inductive inference and unsolvability
cites work: Queries and concept learning
cites work: Toward a mathematical theory of inductive inference
cites work: Terse, superterse, and verbose sets
cites work: Comparison of identification criteria for machine inductive inference
cites work: Q3919704
cites work: Trade-off among parameters affecting inductive inference
cites work: Language identification in the limit
cites work: Q4013540
cites work: Degrees in Which the Recursive Sets are Uniformly Recursive
cites work: Q3905267
cites work: On the non-existence of maximal inference degrees for language identification
cites work: Effective Search Problems
cites work: A proof of Beigel's cardinality conjecture
cites work: Probability and plurality for aggregations of learning machines
cites work: The Power of Pluralism for Automatic Program Synthesis
cites work: Q3819052
cites work: A theory of the learnable
description: scientific article; zbMATH DE number 550135