Extremes in the degrees of inferability

DOI10.1016/0168-0072(94)90035-3zbMath0813.03026MaRDI QIDQ1319507

Stuart A. Kurtz, Lance J. Fortnow, Sanjay Jain, Mark Pleszkovich, Martin Kummer, William I. Gasarch, Theodore A. Slaman, Frank Stephan, Robert M. Solovay, E. B. Kinber

Publication date: 3 May 1994

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(94)90035-3

zbMATH Keywords

inductive inference; recursive functions; oracles; inference machines

Mathematics Subject Classification ID

68T05: Learning and adaptive systems in artificial intelligence

03D15: Complexity of computation (including implicit computational complexity)

Related Items

Robust learning with infinite additional information, Probabilistic inductive inference: A survey, Aspects of complexity of probabilistic learning under monotonicity constraints, Enlarging learnable classes, Index sets and universal numberings, Input-dependence in function-learning, On the learnability of vector spaces, Learning languages from positive data and negative counterexamples, One-shot learners using negative counterexamples and nearest positive examples, Approximation methods in inductive inference, Learning via queries and oracles, Learning recursive functions from approximations, Probabilistic language learning under monotonicity constraints, Noisy inference and oracles, Robust learning aided by context, Structural measures for games and process control in the branch learning model, Equivalences between learning of data and probability distributions, and their applications, The complexity of universal text-learners., Learning languages from positive data and a finite number of queries, Index Sets and Universal Numberings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparison of identification criteria for machine inductive inference
• On the non-existence of maximal inference degrees for language identification
• Probability and plurality for aggregations of learning machines
• Terse, superterse, and verbose sets
• Trade-off among parameters affecting inductive inference
• Queries and concept learning
• A theory of the learnable
• The Power of Pluralism for Automatic Program Synthesis
• Inductive inference and unsolvability
• A proof of Beigel's cardinality conjecture
• Toward a mathematical theory of inductive inference
• Effective Search Problems
• Degrees in Which the Recursive Sets are Uniformly Recursive
• Language identification in the limit