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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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.
- [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)
- [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.
- [Appendix B heading] Typo: 'IOO–earning Proofs' should read 'IOO–Learning Proofs'.
- [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.
- [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.
- [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.
- [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
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
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.
- domain assumption Church-Turing Thesis: TMs can simulate any intuitively computable function under a reasonable encoding.
- ad hoc to paper Reasonable encodings are compositions of an FOL description with a TM-computable transformation (Appendix A.3).
- standard math Standard facts: computable enumeration of TMs (Proposition 24), Generalized Myhill-Nerode theorem, Hopcroft's algorithm.
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.
Forward citations
Cited by 1 Pith paper
-
Prompting Complexity: Shortest Prompts for Texts and Behaviors in LLMs
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
-
[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
work page 2005
-
[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
work page 1987
-
[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
work page 2022
-
[4]
Computational complexity: a modern approach
Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009
2009
-
[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
work page 1936
-
[6]
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
work page 2023
-
[7]
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
work page 2023
-
[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
work page 2024
Show all 31 references
-
[9]
Characteristic sets for polynomial grammatical inference
Colin De La Higuera. Characteristic sets for polynomial grammatical inference. Machine Learning, 27: 0 125--138, 1997
1997
-
[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
2006
-
[11]
Incremental regular inference
Pierre Dupont. Incremental regular inference. In International Colloquium on Grammatical Inference, pages 222--237. Springer, 1996
1996
-
[12]
Language identification in the limit
E Mark Gold. Language identification in the limit. Information and control, 10 0 (5): 0 447--474, 1967
1967
-
[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
1978
-
[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
1993
-
[15]
Grundz \"u ge der Theoretischen Logik
David Hilbert and Wilhelm Ackermann. Grundz \"u ge der Theoretischen Logik . J. Springer, Berlin, 1928
1928
-
[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
1971
-
[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
2024
-
[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
2024
-
[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
1992
-
[20]
Computational complexity
Christos H Papadimitriou. Computational complexity. Pearson, 1993
1993
-
[21]
Learning dfa from simple examples
Rajesh Parekh and Vasant Honavar. Learning dfa from simple examples. Machine Learning, 44: 0 9--35, 2001
2001
-
[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
2021
-
[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
1989
-
[24]
Artificial intelligence: a modern approach
Stuart J Russell and Peter Norvig. Artificial intelligence: a modern approach. Pearson, 2016
2016
-
[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
1996
-
[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...
2011
-
[27]
Sutton and Andrew G
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018
2018
-
[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
1936
-
[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
2022
-
[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
2022
-
[31]
Tractatus logico-philosophicus
Ludwig Wittgenstein. Tractatus logico-philosophicus. Filosoficky Casopis, 52: 0 336--341, 1922
1922
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.