# Learning Algorithms in the Limit

arXiv: https://arxiv.org/abs/2506.15543 · HTML: https://mlsanity.com/paper/2506.15543/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 29 references that are in the map.
- First posted on arXiv 18 Jun 2025.

## Builds on (most cited first, 5 of 5)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [Language Generation in the Limit](https://mlsanity.com/paper/2404.06757/) (2024)
- [A Survey of Demonstration Learning](https://mlsanity.com/paper/2303.11191/) (2023)

## Built on by (most cited first, 9 of 9)

- [A Characterization of List Language Identification in the Limit](https://mlsanity.com/paper/2511.04103/) (2025)
- [Contrastive Identification and Generation in the Limit](https://mlsanity.com/paper/2605.06211/) (2026)
- [On the Price of Privacy for Language Identification and Generation](https://mlsanity.com/paper/2604.07238/) (2026)
- [Globally Consistent Coloring Schemes for Language Identification](https://mlsanity.com/paper/2607.11606/) (2026)
- [Exact Learning of Arithmetic with Differentiable Agents](https://mlsanity.com/paper/2511.22751/) (2025)
- [Space-Efficient Language Generation in the Limit](https://mlsanity.com/paper/2606.25777/) (2026)
- [Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs](https://mlsanity.com/paper/2607.06145/) (2026)
- [Language Identification with Succinct Machine-Independent Traces](https://mlsanity.com/paper/2607.12443/) (2026)
- [Hallucination Rates in Language Generation](https://mlsanity.com/paper/2607.23361/) (2026)

## Abstract (arXiv)

This paper studies the problem of learning computable functions in the limit by extending Gold's inductive inference framework to incorporate textitcomputational observations and textitrestricted input sources. Complimentary to the traditional Input-Output Observations, we introduce Time-Bound Observations, and Policy-Trajectory Observations to study the learnability of general recursive functions under more realistic constraints. While input-output observations do not suffice for learning the class of general recursive functions in the limit, we overcome this learning barrier by imposing computational complexity constraints or supplementing with approximate time-bound observations. Further, we build a formal framework around observations of textitcomputational agents and show that learning computable functions from policy trajectories reduces to learning rational functions from input and output, thereby revealing interesting connections to finite-state transducer inference. On the negative side, we show that computable or polynomial-mass characteristic sets cannot exist for the class of linear-time computable functions even for policy-trajectory observations.