Abstract
Although current large language models are complex, the most basicspecifications of the underlying language generation problem itself are simpleto state: given a finite set of training samples from an unknown language,produce valid new strings from the language that don't already appear in thetraining data. Here we ask what we can conclude about language generation usingonly this specification, without further assumptions. In particular, supposethat an adversary enumerates the strings of an unknown target language L thatis known only to come from one of a possibly infinite list of candidates. Acomputational agent is trying to learn to generate from this language; we saythat the agent generates from L in the limit if after some finite point in theenumeration of L, the agent is able to produce new elements that comeexclusively from L and that have not yet been presented by the adversary. Ourmain result is that there is an agent that is able to generate in the limit forevery countable list of candidate languages. This contrasts dramatically withnegative results due to Gold and Angluin in a well-studied model of languagelearning where the goal is to identify an unknown language from samples; thedifference between these results suggests that identifying a language is afundamentally different problem than generating from it.