Abstract
Humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense. In this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming. We give a precise methodology for studying this phenomenon from a computational viewpoint. It consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learnt using it in a reasonable (polynomial) number of steps. We find that inherent algorithmic complexity appears to set serious limits to the range of concepts that can be so learnt. The methodology and results suggest concrete principles for designing realistic learning systems.
Keywords
Computer science
Affiliated Institutions
Related Publications
Computational Sample Complexity
In a variety of PAC learning models, a trade-off between time and information seems to exist: with unlimited time, a small amount of information suffices, but with time restrict...
Quantum complexity theory
In this dissertation we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing Machine in De...
Oracle Quantum Computing
Abstract Building on the work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polyno...
Oracle Quantum Computing
Abstract Building on the work of Deutsch and Jozsa, we construct oracles relative to which (1) there is a decision problem that can be solved with certainty in worst-case polyno...
Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power has been unknown. We settle this ques...
Publication Info
- Year
- 1984
- Type
- article
- Pages
- 436-445
- Citations
- 4226
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
4226
OpenAlex
Cite This
Leslie G. Valiant
(1984).
A theory of the learnable.
, 436-445.
https://doi.org/10.1145/800057.808710
Identifiers
- DOI
- 10.1145/800057.808710