Learning Algorithms in the Limit

Hristo Papazov, Nicolas Flammarion · 2025

Read Learning Algorithms in the Limit by Hristo Papazov, Nicolas Flammarion (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-15543.txt.

Introduction

Hristo Papazov and Nicolas Flammarion wrote this paper in two thousand twenty-five. It extends a classic theory of learning in the limit, asking what a learner can grasp when it can also watch how a program runs, not just what it prints.

Gold's framework asks which function classes a learner can pin down from endless examples. Plain input-output views cannot crack the class of all computable functions. The authors add time-bound views and views of an agent's action path. With cost caps, or rough time bounds, the wall falls. Learning from action paths turns out to match learning rational functions from inputs and outputs. A hard note closes the work: no neat test sets exist for fast functions, even with path views.

Catalog record

CREATORHristo Papazov, Nicolas Flammarion
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-15543

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Algorithms in the Limit Hristo Papazov, Nicolas Flammarion Abstract This paper studies the problem of learning computable functions in the limit by extending Gold’s inductive inference framework to incorporate computational observations and restricted 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 computational 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. \coltauthor EPFL, Lausanne, Switzerland keywords learning in the limit, inductive inference, algorithmic learning theory, recursion theory 1 Introduction Nearly a century ago, Hilbert and Ackermann 1928 formulated “the most general problem of mathematics” – the so-called Entscheidungsproblem 1 1 1 See ( Copeland 2023b ) for a brief history of the problem. – which sought an effective procedure for deciding the provability of any first-order logical sentence from a given set of axioms. Despite Hilbert’s steadfast optimism, progress eluded the Entscheidungsproblem for almost a decade because, perhaps ironically, “the main problem of mathematical logic” lacked a mathematical formulation. Indeed, the term effective procedure stubbornly evaded formal treatment and only represented the intuitive idea of a finitely described finite process whose execution requires no spark of creativity. The breakthrough came with the work of Church 1936 and Turing 1936 , who formalized the intuitive predicate effective through {\lambda} -calculability and Turing-computability , respectively. This paradigm shift ultimately led to the resolution of the Entscheidungsproblem in the negative. Interestingly, the death of Hilbert’s program elucidated a remarkable coincidence in mathematics: Every effort to formalize the intuitive notion of an effectively computable function appears to single out exactly the same set of functions. Initially proved for {\lambda} -calculability and Turing-computability, this extensional equivalence now captures all known reasonable 2 2 2 Some unreasonable formal models of computation, which lead to hypercomputation, utilize infinite precision arithmetic of real numbers and mechanisms for accelerating computation, see ( Piccinini and Maley 2021 ) . We refer the curious reader to ( Aaronson 2005 ) for a survey of how hypercomputation clashes with the known laws of physics. formalisms of computation. Due to the sheer and exhaustive abundance of equivalent models of computation, nowadays, computer scientists, philosophers, and mathematicians widely accept the Church-Turing Thesis (CTT) which states that Turing machines (TMs) can simulate all ‘‘intuitively computable’’ functions/processes. In our paper, we adopt the prevailing view that the umbrella term ‘‘intuitively computable’’ encompasses other informal notions such as ‘‘effectively computable,’’ ‘‘computable by an algorithm,’’ and ‘‘computable by a harnessable physical process.’’ 3 3 3 For a broad disambiguation between different interpretations of the CTT, we refer the reader to ( Piccinini and Maley 2021 ; Copeland 2023a ) . Remarkably, the CTT lives at the intersection of mathematics, physics, and philosophy. Hence, we take for granted that a TM can simulate any reasonable computational model (see Section A.3 for a discussion on simulations and the CTT). Learning Computable Functions in the Limit. Now, a computational model M working on an enumerable domain {\mathcal{D}} may not halt for all inputs x\in{\mathcal{D}} . Thus, when considering computation at the function level, we make a distinction between the family of total recursive functions {\mathcal{C}}_{\mathcal{D}} – computable on the full domain {\mathcal{D}} , and the family of general recursive functions G_{\mathcal{D}} – computable on subsets of {\mathcal{D}} . 4 4 4 Note that {\mathcal{C}}_{\mathcal{D}}\subsetneq G_{\mathcal{D}} as proved by Turing 1936 through the undecidability of the Halting Problem. Having briefly argued that every function computable by the laws of nature or the complex processes of the human brain ultimately resides in G_{\mathcal{D}} for the relevant domain {\mathcal{D}} , in this paper, we set out to prove that the family of general recursive functions are learnable in the limit from computational observations . In simplest terms, the learning-in-the-limit framework of Gold 1967 refers to the scenario where a learning algorithm {\mathcal{L}} at time t\in{\mathbb{N}} observes a piece of information i_{t} about an unknown function f from a concept class {\Omega} and comes up with a hypothesis based on everything observed so far: h_{t}\leftarrow{\mathcal{L}}(i_{1},\dots,i_{t}) . If for every ground truth f\in{\Omega} and every valid sequence of observations (i_{t})_{t=1}^{\infty} , the learner always converges on the correct function after finitely many mistakes (i.e., h_{t}=f,\ \forall t\geq t^{\star} ), then we say that {\mathcal{L}} learns {\Omega} in the limit and define {\Omega} as learnable in the limit. Though concise, the above description left out some important details. First, clearly {\Omega}\subseteq G_{\mathcal{D}} for some enumerable domain of computation {\mathcal{D}} . Second, with the notation h_{t}\leftarrow{\mathcal{L}}(i_{1},\dots,i_{t}) , we meant that the learning algorithm at time t outputs a representation R_{t} belonging to a computable set of representations {\mathcal{R}} 5 5 5 For example, one could think of {\mathcal{R}} as the set all finite-state automata, cellular automata, or TMs. such that R_{t} generates the function h_{t} when executed on a simulator, like a Universal TM. Third, each example i_{t}=(x_{t},f(x_{t}),{\alpha}(M,x_{t})) includes an input x_{t} , a function value f(x_{t}) , and auxiliary information {\alpha}(M,x_{t}) 6 6 6 Without {\alpha}(M,x) , we arrive at Gold 1967 ’s setup of learning in the limit with an informant . about the computation x_{t}\mapsto f(x_{t}) by some computational model M . Crucially, any valid sequence of observations (i_{t})_{t=1}^{\infty} must exhaust all possible inputs: i.e., \forall x\in{\mathcal{D}}\ \exists t\in{\mathbb{N}} s.t. i_{t}=(x,f(x),{\alpha}(M,x)) . 7 7 7 We relax this requirement in our paper. Instead, if all observed inputs come from an input source I\subseteq{\mathcal{D}} , we will require a successful learner {\mathcal{L}} to learn a representation for a function h in the limit s.t. h_{|I}=f_{|I} . Finally, the requirement that {\mathcal{L}} must correctly learn f in the limit for any ordering of the example set \{(x,f(x),{\alpha}(M,x)):x\in{\mathcal{D}}\} exists to facilitate genuine learning. Otherwise, an ordering function could encode M as the first input, allowing {\mathcal{L}} to learn f without meaningful generalization. Characteristic Sets. Learning-in-the-limit algorithms should correctly identify concepts for any adversarial ordering of examples. Nevertheless, one could still study the sample efficiency of such algorithms in the presence of favorable curricula through the notion of characteristic sets . First introduced by Gold 1978 for finite-state transducers (FSTs) and later generalized by De La Higuera 1997 for arbitrary concept classes, characteristic sets represent a core set of inputs linked to a representation which once observed allow the learner to identify the ground truth. Additional Information. Gold proved that, when the observations include no additional information about the computational process taking x to f(x) (i.e., {\alpha}(M,x)={\varepsilon} – the empty string), no algorithm can learn the concept class of totally recursive functions {\mathcal{C}}_{\mathcal{D}} in the limit ( Gold 1967 , Theorem I.5) . Although, we revisit this input-output-observations (IOOs) framework in Section 3 , we believe that intelligent agents hardly ever learn new

Read the complete text