Language identification in the limit

TL;DR — In 1967 E. Mark Gold proved a clean theorem: no learner can exactly identify a "superfinite" class of languages (all finite languages plus at least one infinite one) from positive examples alone, if an adversary controls the order of examples. For fifty years this was cited as the mathematical backbone of the poverty-of-the-stimulus argument — grammar can't be learned from exposure, so it must be innate. LLMs trained on positive-only text now acquire syntax to near-human levels, not by refuting Gold's theorem but by escaping every one of its assumptions. Pinning down exactly which assumption fails, formally and experimentally, is a live and underexplored problem — and one this reader's tools are well suited to.

The idea as Gold had it

Gold asked the question with startling precision for 1967: what does it mean for a machine to learn a language, and which classes of languages are learnable in that sense?

His setup, identification in the limit, is a game. Fix a class \mathcal{L} of languages (sets of strings). Nature picks a target L \in \mathcal{L} and presents an infinite sequence of examples. The learner sees the sequence one item at a time and after each item emits a guess — a grammar. The learner identifies L in the limit if, after some finite time, its guesses stabilize on a correct grammar for L forever. It never has to announce "I'm done"; it just has to eventually stop being wrong. A class is learnable if one learner works for every language in the class and every legal presentation.

Two presentation modes matter:

• Informant: the learner sees labeled examples — strings marked as in L or not in L.
• Text: the learner sees only positive examples — strings of L, every string appearing eventually, in an order chosen adversarially.

Gold's headline results: from an informant, remarkably rich classes are learnable — the primitive recursive languages, comfortably including context-sensitive grammars. From text, learnability collapses. Any superfinite class — one containing all finite languages plus at least one infinite language — is unlearnable. Since the regular languages are already superfinite, no class in the classical Chomsky hierarchy above the finite languages is learnable from positive examples alone.

Why the trap snaps shut

The proof is a beautiful adversary argument, worth having in your head as a picture.

Suppose the class contains an infinite language L and all of its finite subsets. The adversary feeds the learner strings from L. Whenever the learner conjectures L (or any infinite language), the adversary simply repeats strings it has already shown. The evidence so far is consistent with a finite language — and that finite language is in the class — so a learner that ever wants to converge on finite targets must eventually retreat to a finite hypothesis. The moment it does, the adversary reveals a fresh string of L, forcing another mind-change. Repeat forever. The learner oscillates infinitely and never stabilizes.

The deep asymmetry: positive-only data gives you no signal that you have overgeneralized. An informant fixes this instantly — one negative example collapses the infinite hypothesis. Gold saw the implication for language acquisition and stated it plainly: children apparently learn from something close to text (parents rarely provide, and children rarely use, systematic negative evidence), yet natural languages are presumably at least context-free. Something has to give.

The fifty-year shadow

Chomsky and the nativist tradition took the theorem as formal vindication: since grammar can't be induced from exposure, the child must come pre-equipped with a constrained hypothesis space — Universal Grammar — small enough to evade Gold's trap. This became the canonical citation for the poverty of the stimulus, arguably the most consequential borrowing of a theorem in cognitive science.

Gold himself, to his credit, listed the escape routes in the paper's discussion: maybe the class of natural languages isn't superfinite; maybe children get more than raw text (statistical regularities of the presentation, indirect negative evidence); maybe "identification in the limit" is too strict a success criterion. All three turned out to matter. The literature mostly ignored the caveats and kept the slogan.

Why it could not be resolved then

Three limits, one conceptual and two material.

No alternative theory of learning existed. In 1967 the mathematical vocabulary for learning was exact identification. Valiant's PAC framework was 17 years away (1984); Vapnik–Chervonenkis theory was being written in Russian and wouldn't reach Western ML for decades. The idea that a learner could succeed by getting the distribution approximately right with high probability — trading exactness for tractability — simply wasn't available as mathematics. Nor was the observation that adversarial presentations are the wrong model: a child's input is a sample from a distribution, and distributional information is itself evidence (a string's persistent absence from a large sample is soft negative evidence).

No data. The Brown Corpus, the era's flagship, was roughly 10^6 words and was considered enormous. A child hears very roughly 10^7–10^8 words by adolescence. Modern LLM pretraining runs on the order of 10^{13} tokens. No empirical learner of any stripe could be tested at meaningful scale.

No compute. A 1967 mainframe delivered roughly 10^6 operations per second with core memory measured in hundreds of kilobytes. Training even a small modern language model takes on the order of 10^{20}-plus FLOPs — twenty-odd orders of magnitude away. The question "what does a strong statistical learner actually acquire from positive text?" was unanswerable by experiment.

What changed

The theory was patched first, quietly. Horning (1969) showed that if the presentation is stochastic — strings drawn i.i.d. from a probabilistic grammar — then probabilistic context-free grammars are identifiable in the limit with probability one from positive data. The adversary is the whole problem; replace it with a distribution and the negative result dissolves for measure-one convergence. Angluin (1980) gave the exact characterization of text-learnability via tell-tale sets: a class is learnable from text iff every language L has a finite subset T_L such that no other language in the class sits strictly between T_L and L. This turned Gold's binary verdict into a structural criterion — and showed that plenty of nontrivial, infinite, even linguistically motivated classes pass it. Valiant (1984) then replaced exact identification with approximation, and statistical learning theory replaced worst-case presentations with distributions. Later, Chater and Vitányi's MDL analyses argued an ideal simplicity-based learner extracts grammar from positive data alone; Clark and Lappin's 2011 book assembled the case that Gold's framework never modeled the child's situation. (A useful counterweight: Kearns–Valiant-style hardness results show that even with labels, learning automata is cryptographically hard in the worst case — the escape is average-case, distributional, and biased, not free.)

Then came the empirical hammer. Transformers trained on positive-only text — no negative examples, no corrections, no grammar annotations — acquire long-distance agreement, filler-gap dependencies, island constraints, and binding phenomena at levels that match or exceed human acceptability judgments on targeted syntactic evaluations (the Linzen, Wilcox, Warstadt lines of work; BLiMP; the BabyLM challenge showing much of this survives at child-scale ~100M-word corpora). This does not contradict Gold — the theorem is true — but it demonstrates that the theorem's assumptions do not describe any learner or environment we care about. The learner isn't required to identify exactly; the presentation isn't adversarial; the effective hypothesis class induced by architecture + SGD is not "all finite languages plus an infinite one."

What a serious 2026 revival looks like

The debate is resolved in practice but not in theory, and that gap is the opportunity. The revival has two coupled parts.

Formal. Characterize what a distributional, approximate learner provably acquires from positive stochastic text — a modern Horning/Angluin theorem for the LLM setting. Keep from Gold: the learning-as-a-game formalism and the focus on language classes rather than single languages. Replace: adversarial presentation → i.i.d. (or weakly dependent) draws from a distribution with realistic tail behavior (Zipfian, not uniform); exact identification → convergence in KL or total variation of the learner's predictive distribution; unrestricted learners → learners with an explicit simplicity/architecture bias. The target theorem shape: for a class \mathcal{L} with property P (a probabilistic analogue of tell-tale sets — something like "distinguishable expected prefixes at rate \epsilon"), a compression-biased predictor converges with sample complexity polynomial in 1/\epsilon and description length. Fragments of this exist scattered across distribution learning, grammatical inference (the ICGI community, Clark's distributional learning of substitutable languages), and recent theory on what transformers can represent (bounded hierarchy, Dyck languages, RASP-style analyses). Nobody has assembled it into a clean answer to Gold.

Experimental. Build synthetic language classes that sit exactly on Gold's boundary — superfinite classes, classes with and without tell-tale sets, probabilistic versions of both — and train transformers from scratch on positive samples. Measure: does the model's predictive distribution converge to the target? How does sample complexity scale with the tell-tale structure? Does the model exhibit the oscillation Gold's adversary forces, or does the distributional presentation kill it, as Horning predicts? This is cheap by modern standards (tiny vocabularies, models under 10^8 parameters) and would produce the first direct empirical map of Gold's negative territory. The crisp falsifiable claim: learnability in practice tracks a probabilistic tell-tale condition, not Gold's condition. Pair it with BabyLM-scale natural-language runs to check the synthetic findings transfer.

Already tried, and what's open

Partially vindicated, never consolidated. Horning and Angluin answered the theory question for restricted settings decades ago; the grammatical-inference community (Angluin's L* with queries, Clark & Eyraud's substitutable languages, spectral methods for PCFGs) built positive learnability results largely unread by both linguists and deep-learning researchers. On the empirical side, targeted syntactic evaluation and BabyLM have effectively won the "can syntax be learned from positive text" argument for practical purposes — Piantadosi's 2023 broadside and the ensuing replies mark the debate's current front line.

Still open: a learnability theorem whose assumptions actually match SGD-trained neural predictors; whether human-scale data (~10^7–10^8 words) suffices without LLM-scale inductive shortcuts, which BabyLM only partially answers; what residual innate bias, if any, the architecture is smuggling in (the nativist position hasn't died, it has retreated to "the transformer's priors are the UG"); and whether the probabilistic-tell-tale characterization sketched above is even the right conjecture.

Where to read it

Gold's paper is in Information and Control 10(5), 1967 (doi:10.1016/S0019-9958(67)91165-5) — short, lucid, and more careful than its citers. Read alongside: Angluin, "Inductive inference of formal languages from positive data" (1980) for the tell-tale characterization; Horning's 1969 Stanford thesis for the stochastic escape hatch; Kent Johnson, "Gold's theorem and cognitive science" (2004) for a philosopher's audit of what the theorem does and doesn't license; Clark & Lappin, Linguistic Nativism and the Poverty of the Stimulus (2011); and Warstadt & Bowman's work plus the BabyLM reports for the modern empirical state of play.