Pith. sign in

REVIEW 3 major objections 6 minor 1 cited by

Learning Algorithms in the Limit

T0 review · 3 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Pith's one-line read The paper shows how time-bound and policy-trajectory observations can make every computable function learnable in the limit.

desk verdict A useful extension of Gold's framework with a real reduction idea, but Theorem 16's FST reduction is missing the halting-state reconstruction and needs a careful rewrite before I'd trust the PTO results. read the letter →

arxiv 2506.15543 v2 pith:FGHOOLGK submitted 2025-06-18 cs.LG cs.AIcs.DScs.FL

classification cs.LGcs.AIcs.DScs.FL MSC 68Q3268Q45
keywords learninginthelimitinductiveinferencealgorithmictheoryrecursiontime-boundobservationspolicy-trajectorycharacteristicsetsfinite-statetransducers
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper extends Gold's classical framework for learning functions in the limit by letting the learner observe not just input–output pairs but also computational traces: an approximate upper bound on the number of steps an unknown model takes (time-bound observations) or the full external sequence of its actions on the environment (policy-trajectory observations). Its central claim is that these additional observations dissolve the classical impossibility result of Gold, under which no algorithm can identify the class of computable functions from input–output data alone. In particular, the paper proves that, assuming a relaxed form of the Extended Church–Turing Thesis, the class of all general recursive functions is learnable in the limit from time-bound observations; without relying on that thesis, Turing-machine-computable functions are learnable from time-bound observations, and learning them from policy trajectories reduces to learning rational functions from input–output observations. The paper also establishes a negative result: no algorithm can have polynomial-mass or even computable characteristic sets for Turing machines from policy-trajectory observations. A sympathetic reader would care because the results turn an absolute-looking unlearnability barrier into a statement about the information available to the learner, and they connect Turing-machine inference to the well-developed theory of finite-state transducer learning.

What carries the argument

The machinery has three parts. First, learning-by-enumeration: the learner walks a computable ordering of Turing machines, discarding every candidate that disagrees with the observations or cannot finish within the allotted time bound, and outputs the first surviving machine; convergence follows once all earlier candidates have been refuted. Second, the q-ECTT (Assumption 4) lets the learner replace an arbitrary computational model $M$ by a simulating Turing machine whose slowdown is a computable, monotonically increasing function $q(c,t)$, so time-bound observations become concrete step-count budgets. Third, for policy-trajectory observations, the map $\psi$ from Turing machines to finite-state transducers with the same transition diagram turns tape behavior into input-output behavior of a rational function, reducing $(T^\Gamma_\Sigma,\alpha_{PT})$–LP to $\mathcal{P}^B_A$–LP; the Maximum-Similarity Merging (MSM) algorithm is then analyzed as a state-merging strategy for restricted input sources.

What would settle it

One concrete test is to seek a physically realizable computational model whose runtime cannot be simulated by any Turing machine within a computable overhead $q(c,t)$; exhibiting one would violate the q-ECTT and falsify Theorems 12 and 14, while leaving Corollaries 13 and 15 intact. A narrower check is to run the enumeration algorithm behind Theorem 14 on a fixed general recursive function and find an ordering of its inputs on which the hypothesis never stabilizes; that would refute the claim that the algorithm solves the $(M_D,\alpha_{TB})$–LP.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is a triple of theorems. Theorem 12 states that, assuming the q-ECTT, every parameterized complexity class of general recursive functions is learnable in the limit from input-output observations alone, so e.g. the polynomial-time computable functions are learnable. Theorem 14 states that, also under the q-ECTT, the full class $\mathbb{G}_D$ is learnable in the limit from time-bound observations of arbitrary computational models; Corollary 15 removes the thesis for Turing machines. Theorem 16 states that learning the class of Turing-machine computable functions from policy-trajectory observations reduces to learning the class of rational functions $\mathcal{P}^B_A$ from input-output observations, thereby placing Turing-machine learning inside finite-state transducer inference; the paper gives an explicit learning-by-enumeration algorithm for the reduced problem. Theorem 17 is the negative half: no algorithm can solve the $(T^\Gamma_\Sigma,\alpha_{PT})$–LP with polynomial-mass or computable characteristic sets, even when restricted to linear-time Turing machines.

Load-bearing premise

The universal learnability theorems (12 and 14) rest on Assumption 4, the q-ECTT: every physically realizable computational model can be simulated by a Turing machine with a computable, monotonically increasing overhead $q(c,t)$; if that thesis fails, or the paper's definition of a 'reasonable encoding' is rejected, the statements about arbitrary computational models are unsupported, though the Turing-machine-specific corollaries (13, 15, 16) survive.

Editorial extensions

If this is right

  • Polynomial-time computable functions—and any parameterized complexity class with a computable time bound—become learnable in the limit from input-output observations alone, so the standard reading of Gold's theorem as a blanket unlearnability result no longer applies to time-bounded classes.
  • Every Turing-computable function is learnable in the limit from time-bound observations even if the q-ECTT fails, so the positive results do not stand or fall with the physical thesis.
  • An algorithm that learns rational functions from input-output observations automatically learns Turing machines from policy trajectories, meaning the PTO-learning problem is exactly as hard as IOO-learning of rational functions under restricted inputs.
  • No polynomial-mass or computable characteristic sets exist for Turing machines under policy-trajectory observations; a different efficiency measure, polynomial-size characteristic sets, is proposed as the meaningful open target.
  • For every total recursive function there is a Turing machine with an extended alphabet on which greedy state-merging (MSM) learns the function in the limit from polynomially many trajectory samples.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An implication the authors leave implicit: the learnability boundary is a property of the observation channel, not of the function class—the same class $\mathbb{G}_D$ is unlearnable from input-output observations yet learnable from time-bound observations under the q-ECTT.
  • If the PTO reduction is taken as a design principle, existing finite-state transducer inference algorithms could be adapted into learners that infer Turing machines from behavioral traces; the paper itself only establishes the reduction and a special-case success for MSM, so the adaptive step is my inference.
  • The characteristic-set impossibility suggests that counting samples rather than total observation size may be the right efficiency measure; proving whether polynomial-size characteristic sets exist for rational functions under restricted input sources is an open question the paper raises, and a positive answer would make demonstration-driven learning sample-efficient.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper extends Gold's inductive-inference framework by adding computational observations: time-bound observations (TBOs), which give an upper bound on the number of computation steps, and policy-trajectory observations (PTOs), which record the visible tape behavior of a Turing machine. The main claimed results are: (i) under a computable-overhead version of the Extended Church-Turing Thesis (q-ECTT), Q-time-bounded general recursive functions are learnable in the limit from input-output observations (Theorem 12), with a TM-specific corollary (Corollary 13); (ii) all general recursive functions are learnable in the limit from TBOs under q-ECTT (Theorem 14), with a TM-specific corollary (Corollary 15); (iii) PTO-learning of all TMs reduces to IOO-learning of rational functions (Theorem 16); (iv) no algorithm for PTO-learning of TMs can have computable or β-bounded characteristic sets (Theorem 17); and (v) for every total recursive function f there is a TM T_f such that the MSM state-merging algorithm learns f in the limit from polynomially many PTO samples (Theorem 21). The paper also discusses the role of 'reasonable encodings' and proposes an FOL-based definition in Appendix A.3.

Significance. If the PTO reduction were correct, the paper would provide a valuable bridge between computational-process observations and finite-state transducer inference, and the TM-specific IOO and TBO results would genuinely circumvent Gold's classical unlearnability barrier for restricted settings. The enumeration arguments behind Corollaries 13 and 15 are straightforward and appear sound, and Theorem 17 is a clean negative result that does not depend on the disputed reduction. However, the central PTO claim (Theorem 16) is not established as written, and Theorem 21 inherits that gap. The universal claims in Theorems 12 and 14 also rest on informal assumptions about encodings beyond the stated q-ECTT. No code or machine-checked artifacts are provided; the proofs are traditional. The paper is worth serious revision, but its main PTO contribution requires substantial repair.

major comments (3)
  1. [Section 5, Theorem 16; Appendix D] The reduction of (TΓΣ, αPT)-LP to P^B_A-LP is not a valid concept-class reduction. The FST ψ(T) is defined to have the same transition diagram as T, and γ_{ψ(T)} records the read/write/move behavior of δ; it does not record the designated halting state q_f. Two TMs with identical (Q,δ,q0) but different q_f induce the same rational function γ_{ψ(T)} yet compute different partial functions, because they halt at different times and hence have different tape contents. The PTO observation T[x] contains the halting time, but the translated observation (T{x}, γ_{ψ(T)}(T{x})) does not encode q_f, and the Appendix D proof never explains how the learned FST is converted into a TM whose restriction to I is f|I. Moreover, the translation maps each original input x to the scanned-symbol string T{x}, which is not generally invertible, so a rational-function hypothesis on the restricted source {T{x}: x∈I} does not determine f on I. Consequently, the formal implication 'an algorithm solving P^B_A-LP will solve (TΓΣ, αPT)-LP' is unsupported, and the headline claim that PTO-learning reduces to rational-function IOO-learning is not established as written.
  2. [Section 5, Theorem 21; Appendix D] Theorem 21 inherits the unsound reduction of Theorem 16: even if MSM succeeds in recovering the rational function γ_{ψ(T_f)}, the proof does not specify how the resulting FST hypothesis is converted into a representation computing f|I, since the halting state of T_f is not encoded in γ_{ψ(T_f)}. Independently, the proof is incomplete. The sentence 'if ϕ(p),ϕ(q)∈X and ϕ(p)≠ϕ(q), then either there exists a distinguishing string for p and q in T_M(S_t), or s(p,q)=1' is unclear, and the crucial claim that MSM merges all states in ϕ^{-1}(X) before considering any other merger is asserted without deriving it from the definition of the similarity score s(p,q). A full proof of the greedy merging behavior is needed, or the theorem should be restated with a precise hypothesis on the merging order.
  3. [Assumption 4; Theorems 12 and 14; Appendix A.3] The universal statements of Theorems 12 and 14 quantify over all models M∈M_D and all enumerable domains D, but the proofs require more than Assumption 4. They require that the q-ECTT simulation bound holds for the specific 'reasonable encoding' φ chosen by the learner, and the text adds an informal extra assumption in §2.1.3 that all natural encodings cause the q-ECTT to 'kick in.' Assumption 4 itself only asserts the existence of some TM and constant for a physically realizable model, while M_D as defined in §2.1 includes arbitrary abstract machines, which need not be physically realizable. Appendix A.3's proposed definition of reasonable encodings via an 'inherent FOL representation' E is also informal and still refers to TM-computability, so it does not eliminate the circularity the paper acknowledges. Please restate these theorems with precise model-class and encoding assumptions; the TM-specific Corollaries 13 and 15 are not affected by this issue.
minor comments (6)
  1. [Definition 3] The TM tuple in Definition 3 is (Q,Γ,δ), but the computation convention refers to q0 and qf. Please include q0 and qf in the formal tuple or state explicitly that they are part of the model-class convention; the current notation contributes to the ambiguity exploited in the reduction.
  2. [Appendix B heading] Typo: 'IOO–earning Proofs' should read 'IOO–Learning Proofs'.
  3. [Theorem 17 proof] The assertion that Y_{T,w} and N_{T,w} are in the linear-time class LΣ is not justified in the text; a brief explanation (e.g., hardwiring T and w and tracking the simulated head in the finite control or on the tape) is needed. The main contradiction for TΓΣ does not depend on this stronger claim.
  4. [Remark after Theorem 12] The remark claiming polynomial-time per-example runtime is under-specified: it does not define the hypothesis returned when the time budget expires before the smallest consistent TM is found, and it is not clear that the resulting hypothesis sequence converges to T_K. This remark is not needed for the learnability claim.
  5. [Section 5, Observation Trees] The definition of I(M) as the partial automaton 'obtained after the pruning of unused states and transitions when all inputs come from I' is informal; since Theorem 21 uses it, a formal definition (which transitions are retained and how the start state is determined) is needed.
  6. [Appendix D, Theorem 21 proof] The sentence 'if ϕ(p),ϕ(q)∈X and ϕ(p)≠ϕ(q), then either there exists a distinguishing string for p and q in T_M(S_t), or s(p,q)=1' is garbled and should be rewritten.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the main theorems are explicit assumption-driven derivations, and the flagged Theorem 16 concern is a soundness gap, not a self-referential reduction.

full rationale

The derivation chain is not circular. Theorems 12 and 14 are explicitly conditional on the q-ECTT (Assumption 4), and their proofs in Appendices B and C are ordinary enumeration/consistency arguments: the learner simulates candidate TMs for a computable time bound and selects the first candidate consistent with the observed examples (x, f(x), alpha(...)). No parameter is fitted and then renamed a prediction; the time bounds Q and q are part of the stated assumption or the observation model, not inferred from the data. The universal claims inherit the q-ECTT as a postulate, which is a legitimate assumption rather than an imported conclusion. The PTO reduction in Theorem 16 is also not circular in the logical sense: it defines psi(T) and identifies T[x] with FST input-output pairs, and Appendix D proves learnability of P_B^A by enumeration independently of the TM result. The genuine weakness in Theorem 16 is that the rational function gamma_{psi(T)} does not encode the designated halting state q_f, so a rational-function hypothesis may not determine a TM computing the original partial function; however, that is a correctness/soundness problem in the reduction, not an equivalence-by-construction of the theorem's conclusion with its inputs. The discussion of 'reasonable encodings' in Appendix A.3 is self-referential in topic, but the paper explicitly flags the regress and treats the resolution as a definitional assumption, not as a theorem used to derive learnability. There are no load-bearing self-citations and no ansatz smuggled in through citation; external results (Gold 1967/1978, Myhill-Nerode, Hopcroft) are used as genuine prior facts. Hence the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted parameters. Its formal results rest on the q-ECTT, the CTT, and the authors' definition of reasonable encodings. The computational-agent and symbolic-universe definitions are modeling constructs, not new natural entities, so they are not listed as invented entities.

assumptions (4)
  • domain assumption q-ECTT (Assumption 4): for any physically realizable computational model M, there exists a constant c and a TM T such that if M takes t steps, T simulates it in q(c,t) steps, for a computable monotonically increasing function q.
    Used in Theorems 12 and 14 to convert arbitrary models into TMs with a known simulation overhead. The TM-specific corollaries avoid it by setting q(c,n)=n and encoding as identity.
  • domain assumption Church-Turing Thesis: TMs can simulate any intuitively computable function under a reasonable encoding.
    Section 1 and Appendix A.3. Motivates the focus on GD and on TMs as the universal model. Not directly load-bearing for the formal theorems, which are stated for TMs and for models in MD.
  • ad hoc to paper Reasonable encodings are compositions of an FOL description with a TM-computable transformation (Appendix A.3).
    The paper needs a definition of 'reasonable' to apply q-ECTT to the learner's chosen encoding. This definition is introduced by the authors and is not standard, so it is an added assumption.
  • standard math Standard facts: computable enumeration of TMs (Proposition 24), Generalized Myhill-Nerode theorem, Hopcroft's algorithm.
    Used in the enumeration proofs and in the FST reduction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning Algorithms in the Limit." pith.science (2026). https://pith.science/paper/FGHOOLGK

@misc{pith2026250615543,
  author       = {Pith},
  title        = {Pith review of: Learning Algorithms in the Limit},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FGHOOLGK}},
  note         = {Machine review of arXiv:2506.15543}
}
read the original abstract

This paper studies the problem of learning computable functions in the limit by extending Gold's inductive inference framework to incorporate \textit{computational observations} and \textit{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 \textit{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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs

    cs.CL 2026-07 conditional novelty 6.0 of 10

    The paper defines prompting complexity as the length of the shortest plausible prompt that deterministically generates a target text with a fixed language model.

Reference graph

Works this paper leans on

31 extracted references · 26 canonical work pages · cited by 1 Pith paper

  1. [1]

    Guest column: Np-complete problems and physical reality

    Scott Aaronson. Guest column: Np-complete problems and physical reality. ACM Sigact News, 36 0 (1): 0 30--52, 2005

  2. [2]

    Learning regular sets from queries and counterexamples

    Dana Angluin. Learning regular sets from queries and counterexamples. Information and computation, 75 0 (2): 0 87--106, 1987

  3. [3]

    Exploring length generalization in large language models

    Cem Anil, Yuhuai Wu, Anders Andreassen, Aitor Lewkowycz, Vedant Misra, Vinay Ramasesh, Ambrose Slone, Guy Gur-Ari, Ethan Dyer, and Behnam Neyshabur. Exploring length generalization in large language models. Advances in Neural Information Processing Systems, 35: 0 38546--38556, 2022

  4. [4]

    Computational complexity: a modern approach

    Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009

  5. [5]

    A note on the entscheidungsproblem

    Alonzo Church. A note on the entscheidungsproblem. The journal of symbolic logic, 1 0 (1): 0 40--41, 1936

  6. [6]

    Jack Copeland

    B. Jack Copeland. The Church-Turing Thesis . In Edward N. Zalta and Uri Nodelman, editors, The Stanford Encyclopedia of Philosophy . Metaphysics Research Lab, Stanford University, 2023 a

  7. [7]

    Jack Copeland

    B. Jack Copeland. The rise and fall of the entscheidungsproblem. In Edward N. Zalta and Uri Nodelman, editors, The Stanford Encyclopedia of Philosophy . Metaphysics Research Lab, Stanford University, 2023 b

  8. [8]

    A survey of demonstration learning

    Andr \'e Correia and Lu \' s A Alexandre. A survey of demonstration learning. Robotics and Autonomous Systems, 182: 0 104812, 2024

Show all 31 references
  1. [9]

    Characteristic sets for polynomial grammatical inference

    Colin De La Higuera. Characteristic sets for polynomial grammatical inference. Machine Learning, 27: 0 125--138, 1997

  2. [10]

    Ten open problems in grammatical inference

    Colin de la Higuera. Ten open problems in grammatical inference. In International Colloquium on Grammatical Inference, pages 32--44. Springer, 2006

  3. [11]

    Incremental regular inference

    Pierre Dupont. Incremental regular inference. In International Colloquium on Grammatical Inference, pages 222--237. Springer, 1996

  4. [12]

    Language identification in the limit

    E Mark Gold. Language identification in the limit. Information and control, 10 0 (5): 0 447--474, 1967

  5. [13]

    Complexity of automaton identification from given data

    E Mark Gold. Complexity of automaton identification from given data. Information and control, 37 0 (3): 0 302--320, 1978

  6. [14]

    Teaching a smart learner

    Sally A Goldman and H David Mathias. Teaching a smart learner. In Proceedings of the sixth annual conference on computational learning theory, pages 67--76, 1993

  7. [15]

    Grundz \"u ge der Theoretischen Logik

    David Hilbert and Wilhelm Ackermann. Grundz \"u ge der Theoretischen Logik . J. Springer, Berlin, 1928

  8. [16]

    An n log n algorithm for minimizing states in a finite automaton

    John Hopcroft. An n log n algorithm for minimizing states in a finite automaton. In Theory of machines and computations, pages 189--196. Elsevier, 1971

  9. [17]

    Language generation in the limit

    Jon Kleinberg and Sendhil Mullainathan. Language generation in the limit. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

  10. [18]

    Auto-regressive next-token predictors are universal learners

    Eran Malach. Auto-regressive next-token predictors are universal learners. In Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMLR.org, 2024

  11. [19]

    Inferring regular languages in polynomial updated time

    Jos \'e Oncina and Pedro Garcia. Inferring regular languages in polynomial updated time. In Pattern recognition and image analysis: selected papers from the IVth Spanish Symposium, pages 49--61. World Scientific, 1992

  12. [20]

    Computational complexity

    Christos H Papadimitriou. Computational complexity. Pearson, 1993

  13. [21]

    Learning dfa from simple examples

    Rajesh Parekh and Vasant Honavar. Learning dfa from simple examples. Machine Learning, 44: 0 9--35, 2001

  14. [22]

    Computation in Physical Systems

    Gualtiero Piccinini and Corey Maley. Computation in Physical Systems . In Edward N. Zalta, editor, The Stanford Encyclopedia of Philosophy . Metaphysics Research Lab, Stanford University, S ummer 2021 edition, 2021

  15. [23]

    Inductive inference, dfas, and computational complexity

    Leonard Pitt. Inductive inference, dfas, and computational complexity. In International Workshop on Analogical and Inductive Inference, pages 18--44. Springer, 1989

  16. [24]

    Artificial intelligence: a modern approach

    Stuart J Russell and Peter Norvig. Artificial intelligence: a modern approach. Pearson, 2016

  17. [25]

    Introduction to the Theory of Computation, volume 27

    Michael Sipser. Introduction to the Theory of Computation, volume 27. ACM New York, NY, USA, 1996

  18. [26]

    Bernhard Steffen, Falk Howar, and Maik Merten. Introduction to Active Automata Learning from a Practical Perspective, bookTitle=Formal Methods for Eternal Networked Software Systems: 11th International School on Formal Methods for the Design of Computer, Communication and Soft...

  19. [27]

    Sutton and Andrew G

    Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018

  20. [28]

    On computable numbers, with an application to the entscheidungsproblem

    Alan Turing. On computable numbers, with an application to the entscheidungsproblem. J. of Math, 58 0 (345-363): 0 5, 1936

  21. [29]

    A new approach for active automata learning based on apartness

    Frits Vaandrager, Bharat Garhewal, Jurriaan Rot, and Thorsten Wi mann. A new approach for active automata learning based on apartness. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 223--243. Springer, 2022

  22. [30]

    Chain-of-thought prompting elicits reasoning in large language models

    Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35: 0 24824--24837, 2022

  23. [31]

    Tractatus logico-philosophicus

    Ludwig Wittgenstein. Tractatus logico-philosophicus. Filosoficky Casopis, 52: 0 336--341, 1922

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.