The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
A theory of the learnable
Open accessAbstract
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 learned using it in a reasonable (polynomial) number of steps.Although inherent algorithmic complexity appears to set serious limits to the range of concepts that can be learned, we show that there are some important nontrivial classes of propositional concepts that can be learned in a realistic sense.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“The theoretical characterization of catastrophic forgetting bounds is established through a rigorous framework grounded in Probably Approximately Correct (PAC) learning theory”
From Mitigating catastrophic forgetting in lifelong learning: a hybrid architecture integrating neural ordinary differential equations with memory-augmented transformers (2025) · cites this paper as [38]
Experimental — accuracy not yet measuredThe check wasn’t confident either way, so it gives no verdict — never disputed.
In the citing paper
“The forgetting bound quantifies the maximum expected performance degradation on task”
From Mitigating catastrophic forgetting in lifelong learning: a hybrid architecture integrating neural ordinary differential equations with memory-augmented transformers (2025) · cites this paper as [38]
Experimental — accuracy not yet measuredIn the citing paper
“Research focusing on inconclusive evidence refers to the way in which non-deterministic, ML algorithms produce outputs that are expressed in probabilistic terms (James et al. 2013;Valiant 1984).”
From The ethics of algorithms: key problems and solutions (2022) · cites this paper as Valiant 1984
In the citing paper
“These types of algorithms generally identify association and correlation between variables in the underlying data, but not causal connections.”
From The ethics of algorithms: key problems and solutions (2022) · cites this paper as Valiant 1984
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The complexity of theorem-proving procedures
Cook, S. A. (1971) · Proceedings of the third annual ACM symposium on Theory of computing - STOC '71 · doi:10.1145/800157.805047 · Cited by 6,385
Inductive Inference: Theory and Methods
Angluin, D., & Smith, C. H. (1983) · ACM Computing Surveys · doi:10.1145/356914.356918 · Cited by 872
A complexity theory based on Boolean algebra
Skyum, S., & Valiant, L. G. (1981) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1981.3 · Cited by 42
Self-citation
Flagged first, then by citations
Research works printed but not linked: 6
- Barr A., 1982, Calif.
- Duda R.O. and Hart P.F. Pattern Classification and Scene Analysis. Wiley New York. 1973. Duda R.O. and Hart P.F. Pattern Classification and Scene Analysis. Wiley New York. 1973.
- ErdSs P., 1974, Academic Press
- Goldreich O., 1984, Proceedings of 25th IEEE Symposium on Foundations of Computer Science (Singer Island, Fla., Oct. 24-26)
- Michalski R.S., 1983, Calif.
- Valiant L.G. Deductive learning. Philosophical Transactions of the Royal Society of London (1984). To be published. Valiant L.G. Deductive learning. Philosophical Transactions of the Royal Society of London (1984). To be published.
Cited by
Sorted by citations
Mining association rules between sets of items in large databases
Agrawal, R., Imieliński, T., & Swami, A. (1993) · Proceedings of the 1993 ACM SIGMOD international conference on Management of data · doi:10.1145/170035.170072 · Cited by 14,907
Approximation by superpositions of a sigmoidal function
Cybenko, G. (1989) · Mathematics of Control, Signals, and Systems · doi:10.1007/bf02551274 · Cited by 13,883
Machine learning: Trends, perspectives, and prospects
Jordan, M. I., & Mitchell, T. M. (2015) · Science · doi:10.1126/science.aaa8415 · Cited by 9,955
The capacity of wireless networks
Gupta, P., & Kumar, P. R. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.825799 · Cited by 8,192
Wolpert, D. H. (1992) · Neural Networks · doi:10.1016/s0893-6080(05)80023-1 · Cited by 7,951
Metadata
- Authors
- Valiant, L. G.
- Affiliations
- Harvard University (US)
- Corresponding author
- Valiant, L. G.
- Venue
- Communications of the ACM
- Published
- 1984-11-05
- Volume
- 27
- Issue
- 11
- Pages
- 1134-1142
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W4238893454
- Cited by
- 3,279
- References
- 3
- Citations by year
- 2026: 58 · 2025: 93 · 2024: 117 · 2023: 106 · 2022: 123 · 2021: 116 · 2020: 96 · 2019: 91 · 2018: 89 · 2017: 94 · 2016: 89 · 2015: 84 · 2014: 62 · 2013: 91 · 2012: 71
- FWCI
- 10.16
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Communications of the ACM (publishedVersion)
- Funders
- National Science Foundation
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
- Keywords
- learnability, concept learning, knowledge acquisition, learning protocols, information gathering, computational complexity, algorithmic complexity, computational learning theory
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
