Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy (arXiv:2609.10525)

Forum topic · 小凯 · 2026-09-11

Summary

This arXiv paper (2609.10525) by Xiaoyu Li, Andi Han, Jiaojiao Jiang, and Junbin Gao characterizes language generation in the limit for arbitrary language families over a countable universe. The task requires generating valid unseen elements from every exhaustive positive presentation of an unknown infinite language. The authors prove that generation is possible exactly when each target language can be assigned a finite positive witness such that targets activated by any finite sample share an infinite common intersection. The proof introduces a universal normalization showing any successful generator can be converted into one depending only on the observed set. The paper further develops a hierarchy of witness sizes: positive separation width, unbounded finite witnesses, and absence of compatible finite-witness assignments, with examples at every level. Countable families admit singleton witnesses, explicit families realize every finite width, and unions of families with infinite common cores require unbounded finite witnesses. Countable-support and finite-profile obstructions show local combinatorial data cannot determine limit generation. All results are formally verified in Lean.

Paper Overview

Field: Machine Learning
Authors: Xiaoyu Li, Andi Han, Jiaojiao Jiang, Junbin Gao
Published: 2026-09-09
arXiv: 2609.10525

Abstract

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

Key Points

Provides a complete characterization of language generation in the limit for arbitrary families over a countable universe.
Equivalence: generation is possible iff every target admits a finite positive witness, with targets activated by any finite sample having an infinite common intersection.
Proof technique: a universal normalization converts any successful generator into one depending only on the observed set via a search through unconfirmed histories.
Introduces a separation-width hierarchy: positive separation width (smallest uniform bound), unbounded finite witnesses, and no compatible finite-witness assignment — every level is realized by examples.
Countable families admit singleton witnesses; explicit families realize every finite width; unions of two families with infinite common cores require unbounded finite witnesses.
Countable-support and finite-profile obstructions show local combinatorial data cannot determine limit generation.
All results formally verified in Lean (repository linked above).