Language Generation in the Limit - Transformers as a Computational Model

Explore language generation fundamentals in this 52-minute lecture by Jon Kleinberg from Cornell University. Delve into the core specifications of language generation problems, examining how to produce valid new strings from an unknown language using only finite training samples. Investigate models where an adversary enumerates strings from an unknown target language, and discover the non-trivial guarantees possible in this setting. Compare these findings with Gold and Angluin's negative results in language learning, highlighting the fundamental differences between language identification and generation. Gain insights into Transformers as a computational model and the implications for current large language models.