Extremes in the degrees of inferability

DOI10.1016/0168-0072(94)90035-3zbMath0813.03026OpenAlexW2064496697MaRDI 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 inferencerecursive functionsoraclesinference machines

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (22)

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

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

This page was built for publication: Extremes in the degrees of inferability