Learning recursive functions: A survey

DOI10.1016/J.TCS.2008.02.021zbMath1146.68443OpenAlexW1981403153MaRDI QIDQ924164

Thomas Zeugmann, Sandra Zilles

Publication date: 28 May 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.02.021

zbMATH Keywords

inductive inferencecomplexity theoryrecursive functionsrecursion theoryalgorithmic learningcomputable numberings

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (18)

A solution to Wiehagen's thesis ⋮ On the Influence of Technology on Learning Processes ⋮ Enlarging learnable classes ⋮ Mind change speed-up for learning languages from positive data ⋮ Learning and classifying ⋮ On the complexity of learning programs ⋮ Learning algebraic structures with the help of Borel equivalence relations ⋮ Learning figures with the Hausdorff metric by fractals -- towards computable binary classification ⋮ Absolutely no free lunches! ⋮ Learning families of algebraic structures from informant ⋮ Learning indexed families of recursive languages from positive data: A survey ⋮ On the Amount of Nonconstructivity in Learning Recursive Functions ⋮ Algorithmic identification of probabilities is hard ⋮ Identification of probabilities ⋮ Hypothesis spaces for learning ⋮ On some open problems in reflective inductive inference ⋮ Hypothesis Spaces for Learning ⋮ On the interplay between inductive inference of recursive functions, complexity theory and recursive numberings

Cites Work

• Comparison of identification criteria for machine inductive inference
• On the power of probabilistic strategies in inductive inference
• One-sided error probabilistic inductive inference and reliable frequency identification
• An approach to intrinsic complexity of uniform learning
• Reflective inductive inference of recursive functions
• Learning indexed families of recursive languages from positive data: A survey
• Consistent and coherent learning with \(\delta \)-delay
• On the error correcting power of pluralism in BC-type inductive inference
• Saving the phenomena: Requirements that inductive inference machines not contradict known data
• Research in the theory of inductive inference by GDR mathematicians - A survey
• Equivalence of models for polynomial learnability
• Analogical and inductive inference. International workshop AII '89, Reinhardsbrunn Castle, GDR, October 1-6, 1989. Proceedings
• On the necessity of Occam algorithms
• Learning with the knowledge of an upper bound on program size
• On the power of inductive inference from good examples
• Some natural properties of strong-identification in inductive inference
• Identifying nearly minimal Gödel numbers from additional information
• Classical recursion theory. Vol. II
• The weighted majority algorithm
• On the intrinsic complexity of learning recursive functions
• Separation of uniform learning classes.
• Robust learning aided by context
• Avoiding coding tricks by hyperrobust learning
• Incremental learning from positive data
• Trade-off among parameters affecting inductive inference
• Learning classes of approximations to non-recursive functions.
• Incremental concept learning for bounded data mining.
• Robust behaviorally correct learning.
• Robust learning -- rich and poor
• Learning binary relations using weighted majority voting
• Asking questions to minimize errors
• On the intrinsic complexity of learning
• Theory of Formal Systems. (AM-47)
• Tradeoffs in the inductive inference of nearly minimal size programs
• ON THE NONBOUNDABILITY OF TOTAL EFFECTIVE OPERATORS
• Transformations that preserve learnability
• The position of index sets of identifiable sets in the arithmetical hierarchy
• Probabilistic Versus Deterministic Inductive Inference in Nonstandard Numberings
• Probabilistic inductive inference
• The Power of Pluralism for Automatic Program Synthesis
• Inductive inference and unsolvability
• Easy Constructions in Complexity Theory: Gap and Speed-Up Theorems
• Toward a mathematical theory of inductive inference
• Inductive inference of automata, functions and programs
• Ignoring data may be the only way to learn efficiently
• Inductive inference of recursive functions: Complexity bounds
• On the role of search for learning from examples
• Classes of computable functions defined by bounds on computation
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Limiting recursion
• The Operator Gap
• Some decidability results on grammatical inference and complexity
• On Effectively Computable Operators
• A formal theory of inductive inference. Part I
• Language identification in the limit
• A formal theory of inductive inference. Part II
• Computational Complexity and the Existence of Complexity Gaps
• Recursive Properties of Abstract Complexity Classes
• Probabilistic inductive inference: A survey
• Robust learning is rich
• Closedness properties in ex-identification
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Learning recursive functions: A survey