Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarch
New work characterizes language generation in the limit via finite witnesses, proves a full separation-width hierarchy, and formalizes all results in Lean.
The paper fully characterizes when language generation in the limit is possible for arbitrary families over a countable universe: each target must admit a finite positive witness such that targets activated by any finite sample share an infinite common intersection. It defines positive separation width and proves every level of the resulting hierarchy occurs, with countable families admitting singleton witnesses and unions of families with infinite common cores requiring unbounded finite witnesses. The characterization, a universal normalization, and a diagonal capture lemma are machine-checked in the Lean proof assistant, with the development maintained on GitHub.
- Generation possible exactly when targets admit finite witnesses with infinite common intersection.
- Positive separation width hierarchy: every level is realized.
- Countable families admit singleton witnesses; finite widths realized by explicit families.
- Full characterization verified in the Lean proof assistant.
Full article190 words · extracted from arxiv.org · click to collapse
Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary families over a countable universe. Generation is possible exactly when each target can be assigned a finite positive witness so that the targets activated by any finite sample have an infinite common intersection. The necessary direction follows from a universal normalization: a search through unconfirmed histories converts any successful generator into one depending only on the observed set. We then ask how large compatible witnesses must be. Positive separation width records the smallest uniform size bound, with two further levels for unbounded finite witnesses and the absence of any compatible finite-witness assignment. Every level occurs. Countable families admit singleton witnesses, explicit families realize every finite width, and a union of two families with infinite common cores requires unbounded finite witnesses. Finally, countable-support and finite-profile obstructions explain why local combinatorial data cannot determine generation in the limit. The characterization and full width hierarchy are checked in Lean, including the simplified normalization and a direct diagonal capture lemma. The accompanying Lean development is maintained at https://github.com/xiaoyulics/language-generation-characterization
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.10525