Language Identification in the Limit with Computational Trace
Authors: Binghui Peng
Amin Saberi
Grigoris Velegkas
Venue: ICLR 2026 Poster (2026)
Keywords: language identification
complexity theory
Primary area: learning theory
TL;DR: We define a theoretical model of language identification with CoT, where CoT is defined as having access to computational traces, and we show that with this extra information we can learn Turing machines, thus circumventing classical lower bounds.

Abstract: Training on Chain-of-Thought (CoT) traces has empirically shown to dramatically improve the capabilities of Large Language Models (LLMs), yet a formal understanding of its power remains limited. 
In this work, we investigate the role of training on such computational traces from the perspective of language learnability. We introduce a new learning model, identification in the limit with trace, which augments Gold's classic paradigm [Gold'67] by providing the learner not only with examples from a target language but also with computational traces from the machine that accepts them. 
Our results reveal that access to these traces dramatically enhances the power of the learner. We first prove that with perfect computational traces, the class of all computable languages (those recognizable by Turing Machines) becomes identifiable in the limit. This stands in sharp contrast to Gold's famous impossibility result, which holds even for the simple class of languages that are recognizable by deterministic finite automata.
We then analyze the more challenging scenario where the learner has only partial information regarding the computational traces, which are also subject to adversarial corruptions. In this setting, we establish a set of trichotomic results on the amount of error that can be tolerated for the successful identification of language classes across the Chomsky hierarchy.

Published as a conference paper at ICLR 2026
LANGUAGE IDENTIFICATION IN THE LIMIT WITH COMPUTATIONAL TRACE
Binghui Peng
Amin Saberi Stanford University saberi wnw.anooodd...m edu
University of Maryland, College Park binghuipf umd. edu
Grigoris Velegkas
Google Research gvelegkas@google.com com
ABSTRACT
Training on Chain-of-Thouggh (CoT) traces has been empirically shown dra- matically improve the capabilities of Large Language Models (LLMs), yet for- mal understanding
its power remains limited. In this work, we investigate the role of training on such computational traces from the perspective of language learnability, We introduce a new learning model, identification in the limil with trace, which augments Gold's classic paradigm (Gold) 1967) by providing the learner not only with examples from a target language but also with computational traces from the machine that accepts them.
Our results reveal that access these traces dramatically enhances the power of the learner. We first prove that with perfect computational traces, the class of all recursively enumerable languages (those recognizable by Turing Machines) be- comes identifiable in the limit. This stands in sharp contrast to Gold's famous impossibility result, which holds even for the simple class of languages that are recognizable by deterministic finite automata. We then analyze the more challeng- ing scemario where the learner has only partial information regarding the compu- tational traces, which are also subject adversarial corruptions. In this setting, we establish a set of trichotomic results on the amount of error that can be tol- erated for the successful identification of language classes across the Chomsky hierarchy.
INTRODUCTION
Large Language Models (LLMs) have demonstrated remarkable capabilities across vast array of complex tasks, yet they can still falter on scemingly elementary problems. A fascinating empirical such tasks often improves dramatically when they trained
discovery is that their performance on a corpus of data that contain not only input-output pairs, but also a "chain-of-though"" (CoT), i.e.,
a step-by-step explanation of the reasoning process (Wei et al. 2022 Chung et al. 2024). Despite these important practical successes, a comprehensive theoretical understanding of the benefits of reasoning traces in the training of LLMs remains elusive.
Prior work has begun to formalize the usefulness of different types of CoT traces in the training process through theoretical models that are primarily statistical in nature (Malach) 2023 Joshi al. 2022 Altabaa et al.) 2023). In our work, we adopt perspective that is complementary to these statistical approaches and seeks to understand if CoT training helps L.MSs learn the correct world model (Vafa et al.) 2024), i.e., the correct "rules" that describe the environment they operate in. In order to make progress on this question, we need to first give a mathematical definition of the world model. For that, we rely on classical work from Gold (Gold) 1967) who introduced the notion of language identification in the limit. Gold's model there is a countable collection of strings X' (e.g., the set of all finite-lenghh binary strings) and countable collection of languages C. where each language is defined as a (potentially infinite) subset of X. Every language can be thought of as representing all the "facts" within some world. For instance, building the ideas of

---

Published as a conference paper at ICLR 2026
Li et al. (2023) Nanda et al. (2023) who used the task of learning rules of board games to test if LLMs are capable of learning world models, we can think of different languages in as representing the valid states of different board games. Gold's model formalizes learning
two-player game where an adversary chooses some K E L. and presents an enumeration of it to the learner, who must eventually converge correct description of that language, after making a finite number of mistakes, It is well-established that under this paradigm, most of the interesting classes of languages are not identifiable (Angluin) [980). Thus, it is natural to ask: if we augment the Gold-Angluin model with notion of chain-of thain-of-thooe ahothhu can we expand the class of languages that are identifiable in the limit? We introduce a new model, identification in the limit with traces, where the learning algorithm observes not only examples from the target language but also computational trace, which in our model defined as the sequence of computational steps (i.e., "trace") that a fixed machine takes to accept them.
Our first result shows that, perhaps surprisingly. the class of all languages accepted by Turing Ma- chines (TMs) is identifiable with traces. This is in striking contrast to the negative results in Gold's setting, who showed that the much simpler class of regular languages, i.c., those that are recogniz- able by DFAs, is not identifiable in the limit (Gold 1967).
Informal Theorem 1 (Informal statement of Theorem 3.1 The class of languages recognized by
Turing machines is identifiable in the limit with traces.
Having established these strong positive results, we turn to a crucial question of robustness: how resilient are these learning guarantees to imperfections in the provided traces? To model these imperfections, we consider scenarios where the computational traces are corrupted-the traces that are only partially observable, skip important steps, or contain errors. As a unified metric, we measure this corruption as the deviation from the true computational trace, quantified by the edit distance. In this setting, we establish tight bounds on the amount of error a learner can tolerate while still successfully identifying regular languages (recognizable by DFAs), deterministic context- free languages (recognizable by Deterministic Pushdown Automata, DPDAs), and recursively enumer- able languages (recognizable by TMs).
includes
Informal Theorem 2 (Informal statement of Theorem 4.3 4.5 identification in the limit with traces:
Consider the task of language
For languages recognizable by DFAs, identification is possible even with a constant fractont of corruption (for any constant rate less than 1).
For languages recognizable by DPDAs, identification impossible for any constant frac- tion of corruption, but becomes possible when the corruption rate is diminishing
For languages recognizable by TMs, identification is possible if and only if the total rumber of errors per trace is bounded.
Formal definitions of our corruption model are provided in Detinitions 4 and Informal Theo- rem reveals a varied landscape of identifiability corresponding to the error rate and the language's complexity. For the most powerful model (TMs), identification can only be achieved if the number of errors present in an example is finite. In contrast, for the weakest model (DFAs), identification remains possible even when 0.999 fraction of the computational trace is corrupted (per example). The intermediate model (DPDAs) occupies a middle ground: it cannot tolerate even a 0.01 fraction of error, but identification becomes possible when the corruption rate diminishes with the length of the computational trace.
1.1 RELATED WORK
Identification and Generation in the Limit. The paradigm of language identification in the limit was introduced in the pioneering work ofld (1967) and learnability in this setting was fully char- acterized by Angluin [1999 1980). Gold's setting has been very influential both in learning theory and in computational linguistics; we refer the interested reader to Lange et al.] (2008) for a com- prehensive survey of results in this area. Inspired by this line of work, Kleinberg & Mullainathan (2024) recently introduced the notion of generation in the limit: instead of having exactly identify the target language, like in Gold's setting, the learner here is required to eventually start producing valid unseen elements of the language, ie.,, elements of the target language that have not appeared in
2

---

Published as a conference paper at ICLR 2026
the input it has witnessed far. The finding of Kleinberr & Mullainathan (2024) is rather surpris- ing: under this modified objective all countable collections of languages become generatable in the limit. This result has led to flurry of follow-up work. [Li et al. (2024) further developed this notion using learning-theoretio tools and studied a hierarchy of notions of generation. Moreover, several works have formalized and studied trade-offss between breadth and hallucinations in language gen- eration (Kalavasis et al.) 2024b a Charikar & Pabbaraju, 2024: Peale et al. [2025] Kleinberg & Wei 2025a b). Raman & Raman (2025) Bai et al. (2025) ; Mehrotra et al. (2025); Li & Zhang] (2026)
studied notions of noisy language generation, while Hanneke et al. (2025); : Bai et al. (2025) showed Inspired by these lines of work, Karbasi et al. 2225)) formalized and studied a setting of automated hullucination detection. Recently, Li et al.
that generation is not closed under finite unions!" !
2026) formalized notion of generation in continuous spaces, and Högsgaard & Pabbaraju
studied notion of agnostic identification and generation. Lastly, Anastasopoulos et al. (2026) pro- posed a setting of safe language generation in the limit.
Learning Algorithms in the Limit. The most closely related setting ours is the very recent work of Papazov & Flammarion (2025). They consider a different version of the identification problem where the goal is to learn recursive functions in the limit, and the learner receives input a stream of evaluations of the target function on every point of the domain. In the context of binary functions, this means that the learner observes both positive and negative examples, of the target language, whereas in our setting it receives only positive examples. This difference is subtle yet critical; in the presence of negative examples, identification in the limit becomes trivial as one can simply output the smallest-indexed language that is consistent with the enumeration Nevertheless, there exist classes of languages such that the above task is undecidable. The work of Papazov& & Flammarion (2025) focuses on the computability of the task and proves that with certain side information (such as the computation time of the target machines), the identification task also becomes decidable. These results are derived with the presence of negative examples they are fundamentally different from our work.
far.
Theory of COT. Recent theoretical work has advanced our understanding of chain-of-thought (CoT) reasoning by grounding it in formal statistical learning frameworks. |Malach| (2023) studies autoregressive next-token prediction in a PAC-style setting, showing that even linear models trained on i.i.d. examples can approximate any ciently long intermediate sequences. This introduces a new statistical complexity measure- measure-length length complexity-wii -hicch captures the tradeoff between reasoning depth and learnability. (Joshi et al. (202) extend this perspective by formalizing a time-invarian autoregressive learning setup, where reasoning steps are repeated applications of shared predictor. Their analysis provides generaliza- tion bounds and sample complexity guarantees for learning with and without intermediate super- vision, showing that sample complexity can remain independent of the CoT length under certain conditions. Allabaa et al. (2025) adopt an information-theorete approach, quantifying the statistical advantage of CoT superviston Via a new measure called CoT information. Their results demonstrate that observing intermediate reasoning steps can provably reduce sample complexity, with matching upper and lower bounds. Since these works study statistical settings, they are orthogonal to the focus of our paper. On related note, a recent line of work (Liu & Moitra 2025 Gaitonde et al.) 2025 Wen et al.] (025) also shows that, with the presence of computation trace, one could circumvent computational lower bounds in various statistical learning settings.
function when allowed to emit suffi-
2 MODEL
We begin by recalling the classic paradigm of language learnability, followed by our main definition which augments this model with computational traces.
Definition 1 (Identification in the Limit (Gold 1967)). Let L. be a countable class of languages over a finite alphabet Σ. An infinite sequence of strings E = (I1, (2........ ... is an enumeration of language K L if the set {ot hee is equal K. The class L identifiable in the limit if there exists an algorithum I that, for any K E L and any enumeration E of K, converges to a correct representation of K. That is, there exists a time ts such that for all 2 t", the algorithm's guess Te(zI,..., It) is constant and correct.
'This result holds for uncountable collections of languages, which are outside the scope of our work.
3

---

Published as a conference paper at ICLR 2026
Below, we give concrete instantiation of this definition inspired by Vafa et al. (2024) who evaluated LLMs on the task of reconstructing maps of cities.
Example 1. We instantiate Definition 1 by interpreting languages as city maps, where each lan- guage represents all valid routes within a city. Let Σ be (finite) set of vertices representing inter- sections, and X the set of all finite sequences of elements of E. We let G be the set of all graphs over E, where each graph G = (V, E) E 9 models a city layout, with edges representing roads. The class of languages is then L = {LG G g}. A specific language LG consists of all valid routes (paths) in the graph G: formally, a string w = 0102 0k E X is in LG if and only if (aj, 05+1) E E for all j j <. k. Finally, for a target city K f, an enumeration E (r1, is an infinite sequence of observed valid routes such that the set (re tee equals K.
We consider set of canonical models of computation: Deterministic Finite Automata, Determin- istic Pushdown Automata, and Turing Machines. These are standard textbook models of computa- tion (Sipser) T996) and they capture an increasing complexity of the underlying languages (regular language, deterministic context free grammar and recursively enumerable languages) and the corre- sponding identification tasks. We present brief introduction to these models in Definition 2 for a comprehensive overview, we refer to the textbook of (Sisser (1996). In the following definition, each machine is formalized of states representing the machine's ' possible internal configurations. Σ is the input alphabet, i.e. finite set of symbols that form the input strings. Computation begins at designated start state, qu E Q. A subset of states, F C Q. is defined as the set of final (or accepting) states. The behavior of the machine is governed by a transition function, ó, which dictates how the machine changes state and manages its memory in response to the input it reads. The distinctions of DFAS/DPDAs/TM, lie in their specific memory structures and the definition of 8. To implement memory, models utilize an additional alphabet r (representing the stack or tape contents). They may also employ specific constants such as Zo for the initial stack symbol, for the blank tape symbol, and directions (L, R} to indicate the movement of the tape head.
tuple comprising several core components. Q denotes finite set
Definition (Computational Models). A Deterministic Finite Automaton (DFA) is a 5-tuple (Q, Σ, 8, qo. F) with a transition function 8 : Q x Σ + Q. Here Q denotes the set of states, E the set of input symbols, qu is the initial state, and F C Q are the accepting (final) states.
A Deterministic Pushdown Automaton (DPDA) is a 7-tuple (Q. 8, qu, Zu, F) that includes set of states Q, an input alphabet E., a stack alphabet r, the initial state qo, an initial stack symbol Zo E T, set of accepting states F C Q and a transition function 5: Q x (EU x - Q* l
Turing Machine (TM) is a 7-tuple [Q, J, 5, qo: F) that includes a set of states Q, an imput alphabet Σ, a tape alphabet T 2 E. the initial state 90- a blank symbol B E T E, a set of accepting states F Q and a transition functioon 8 Q x r + Q x r x {L, R}.
We now introduce our primary object of study, which equips the learner with step-by-star computa- tional traces (like CoT).
Definition 3 (Identification in the Limit with Traces), Let L be a class of languages and M be a class of machines. For a machine M E .M and an input sequence of computational steps of M on T. An enumeration of K with traces from M is a sequence Firace = ((I1, cas (ax))) )), (I2, Cas (x.)))....) where (Ix) is an enumeration of K = L(M). The class C is identifiable in the limit with traces from M if there exists an algorithm I that converges to correct representation of K when given any such Emace-
L(M), let cM(x)) be the accepting
When the underlying machine and the input x are clear from context, we write c for cM (z). Let us briefly elaborate on the notion of trace we consider in our work. At every timestep of its execution, every computational machine we are considering can be described by a set of parameters (e.g. its current state, memory tape, position the tape etc.). A computational trace simply deseribes the set of (changing) parameters of the underlying machine in every timestep. Thus, the length of the trace is the number of computational steps the machine needs to accept the given string. For concrete example in the case of DFAS we refer the reader to EEample 2
Example 2 (DFA Computational Trace). To illustrate the concept of a computational trace (CoT) as defined in Definition 3) we provide a concrete example using a Deterministic Finite Automaton (DFA). For DFA, the machine's 's configuration
any point in time is entirely determined by its current state. Thus, the computational trace is simply the sequence of states visited. Let us de- fine a DFA M (Q, F, 5, go, F) over the alphabet E {0,1) }} that recognizes the language L
4

---

Published as a conference paper at ICLR 2026
consisting of all strings containing even number of Is. Here, Q {gevens 9odd the starting
state is qo Geven: and the accepting state is = {9even) ). The transition function is defined as
6(even 0) qeven: 8(gods, 0) qodds 8 8(eevn qodd 5 ('odds 1) qeven- Pictorially, the DFA is
shown in Figure Suppose the learner is presented with the input string I = 1010. The execution
0
start
Leven
Todhd
1
Figure 1: DFA M accepting strings with an even number of 1s.
of M on z proceeds as follows: start state qeven. transition to qodd, stay in qodd. transition qeven and, finally, stay in qeeen Thus, the computational trace cas (α) is the complete sequence of states visited during this execution: CM (1010) (geven qodd: Qodd; Geven; Jeven).
Lastly, we provide the notion of robust identification in the limit with CoT, where we allow for imperfect traces that differ from the correct one edit distance.
Definition 4 (Robust Identification in the Limit with Traces). The task of robust identification has similar selup as language identification with traces, except that now the TM (22a) the algorithm observes is noisy, i.e., is corrupted version of the true trace CMr with edit distance error eM (M(2)) The criterion for identification is the same as in Definition 3 where the true trace is replaced with the corrupted one.
Assumption 1 (States in the Corrupted Trace). We assume that (the corrupted trace) does introduce non-existent states of the machine, i.e., ifQ is the set of states of the machine, the corrupted trace does not introduce states that
in Q.
To give a concrete example of the notion of error we allow for, consider the DFA in Example where the string is 1010 and the true trace is (goven: Godd, qodd; qeven: Joven). Corrupted traces for that string can be (among others)
(geven; Leven; Godd, Geven; Geven), which has edit distance 1 to the original (substitute the second element);
(Jeven; Yodd Geven: 9even), which has edit distance 1 to the original (delete the third element);
(Jeven: lodd, Jodd lodds lodd Geven: Ieven), which has edit distance 2 to the original (insert two Godd s).
is clear that whether language identification can be done depends on the edit distance error. On the one hand, if the error is always zero, then it is equivalent to the language identification with traces (Definition 3). On the other hand, the edit distance error is equal to or greater than the length of the actual trace, the trace presents useful information and it goes back to the original language identification task (Definition T). Our goal is to understand the intermediate settings between these two extremes, which we divide into three regimes:
Definition (Error regime). We consider the following three error regimes:
Constant error rate: There is fixed constant a E (0, 1), such that the edit distance error rate is bounded by a asymptotically, Formally, there exists a pair of constants a, la such for any input string with length at least l. (|x) > La), its corruption error is at most an u-fraction of actual computation trace, i.e., EM (xx)//c))) (c)))c(())))))))))))()) | < a.
Diminishing error rate: The edit distance error rate is o(1) asymptotically. Formally, for any constant 10 there exists constant f., (depending the value of ai) such that for any input string & of length at least la (|x) 2 La), the corruption error is at most an ax-raction of the actual computation trace, iee. eas (xx)/(ea(())) S a.
Edit distance is the minimum number of single-character insertions, deletions, substitutions required to transform string into another.
5

---

Published as a conference paper at ICLR 2026
Finite error: The edit distance is bounded by absolute constant C asymptotically, For- mally, there exists a constant length & such that for any input string x of length at least lc ([z) 2 &c). the edit distance enror is bounded by C, i.e., em S C.
For all the results of this paper, we assume the algorithm knows which error regime it operates in. Moreover, for the constant error rate regime, the constant and la are known in advance; for the diminishing error rate regime, (a,, fa) are known for all a (0, 1), while for the finite error, the algorithm knows the constant and lc.
2.1
USEFUL FACTS
Below state some facts from prior work that useful for derivations.
Fact 2.1 ((Gold 1967)). Language identification (without CoT) can be done when the class of languages L is finite.
Proof Sketch. At any time step f, the identification algorithm outputs the index ig of a language in C that is consistent with the input ø1.... It and is minimal with respect to the subset ordering. To see why this leads to identification in the limit, first notice that after some finite timestep t" all the languages that are consistent with the input are the target language K and its supersets (this is because L is finite, so any language that is not superset of K will eventually be contradicted by the input). Thus, outputting minimal language after 1 leads to correct identification.
The next result illustrates the difficulty of identification of countable collections in the absence of COT. We describe a simple collection of regular languages that is not identifiable in the limit. The crux of the difficulty is that the algorithm never receives information about strings that are not in the target K, i.e., it receives only positive examples.
Fact 2.2 (Gold 1967)). Language identification (without CoT) is impossible for the language col- lection C (N, L1, .2....), where L; {1, i)..
Proof Sketch. Assume towards contradiction that there exists some algorithm that identifies C in the limit. Consider the adversary that starts enumerating for multiple timesteps. Since the algorithm identifies in the limit, there must be some timestep that it identifies L₃ (otherwise the algorithm fails since the adversary can keep enumerating indefinitely). Now at timestep / + the adversary enumerates 2 and keeps doing until the algorithm identifies L2. The construction continues in this fashion. Hence, the adversary ends up enumerating N and it constructs an infinite sequence of timesteps &,, ......, in which the algorithm makes mistake.
IDENTIFICATION WITH PERFECT TRACE
We start with the result identification the limit with traces that does not contain any noise.
Theorem 3.1. Let M be the collection of all TMs and L {Li, L2y...) where every L C is recognized by some M E M. Then, C is identifiable in the limit with trace from M.
As a warm-up, it instructive to prove the result for the simpler setting where M is the set of all DFAs. It is worth highlighting that without access to computational trace, i.e., in the original model of Gold, this collection is not identifiable in the limit (see Fact 2.2). Due to space constraints, we present the proof of the theorem for Turing machines in Appendix A
Identification of DFAS (sketch). Fix a binary alphabet Σ = {0, 1}. Let = E0",E.0" (Q',""00 go. F*) be a DFA for the unknown target regular language K. For E K, let c(x) be the (unique) accepting state sequence visited by M on x, including the final accepting state.
Learner. At every step maintain DFA M, (Q+, E, 5t 9o, Fi) with reject sink & F..
1. Initialization: Qo (90, r) Fo 0, and do a) = for all g E Qo. a E (0,

---

Published as a conference paper at ICLR 2026
2. Upon receiving ((z)), let Qe be the set of states occurring in c(2i) and set Qe Q:-1 UQQ. For every newly observed state q E Qi \ Qi 1 and a E {0, 1}, set provisionally (g a) t r. If the last state of c(zz) is qace, then set Fe t U Uqq00
3. Traverse c(xx), Te and for each observed transition (g, a, g'), set de a) t d'-
Invariant (subset property). For all t, the language recognized by the constructed DFA satisfies L(M) S K. By construction, M, differs from M in two conservative ways: (i) it may omit states that have not yet appeared on any accepting trace (so runs that would visit those states in A are simply unavailable in M, and lead to rejection), and (ii) for any g E Qt and E Σ whose outgoing edge has not been witnessed, it maps (g. a) to the non-accepting sink r; on witnessed pairs copies 8* exactly. Hence every accepting run of M, from @u stays within Qi and uses only witnessed edges, which coincide with the corresponding edges of M Moreover, the run can end only in a state in F, C F* (accepting states are added only when witnessed). Therefore the same input is accepted by M and ((M) C L(M*) K.
Eventual completeness. Let Q+ C S and E+ C Q E be the states and labeled edges that lie on at least one accepting computation of M For every E Q+ there exists some x E K whose accepting trace visits q; hence each q Q+ appears some c(x) and is added Q: after finitely many steps. Likewise, for each (q, E E+ there exists some x E K whose accepting trace uses that transition, so 5g a) eventually overwritten to 8" a). Since E* is finite, there is finite time t* after which óe a) = 8" (q. a) for all (q. a) E E and Qt contains all of Q+. Thus, after some time t", every accepting path of M is also an accepting path of Mr. and by the subset invariant, M, accepts no string outside K. Hence L(M))= = K for all f 2 t*.
4 ROBUST IDENTIFICATION
THE LIMIT
We next present our results on robust identification in the limit. Our results demonstrate a trichotomy on the tolerance error. In Section 4.1 we prove that for DFAs, robust identification can be done in the constant error-rate regime. In Section 4.2 we show that robust identification is impossible for DPDAs in the constant error rate regime, but plausible the diminishing error regime. Finally, for the set of TMs, robust identification is impossible even with diminishing error, but for a finite number of errors, there is a robust identification algorithm; see Section 4.3
Overview of technique At high level, the algorithms in this Section are very different from the algorithm in section 3 Instead of reconstructing the state transition from the (corrupted) traces, we use them as evidence on the target function class. In particular, we maintain the set of states that are observed in the computational trace and we prove that either (1) the number of states keeps growing, or (2) the target function class contains not so many states (compared to the observed states). The first case can only occur for finite number of times so eventually we can reduce the task to finite class language identification. All algorithms in this section follow the same template, and the main technical step is to establish the size bound of (2). While this is not so hard for DFAs and TMs, the size bound for DPDAs is quite tricky and we need analyze DPDAs through the Chomsky Normal Form (CNF) decomposition and bound the size of the corresponding CNF tree. Due to space constraints, we only sketch the main idea of the proofs and the formal proof's can be found at Appendix B
4.1 DETERMINISTIC FINITE AUTOMATA
Theorem 4.1. For the task of robust identification in the limit with the set of machines as DFAs, there is a robust identification algorithm that guarantees to succeed in the constant error rate regime.
We use M to denote the target DFA and Q* the set of states in M Let Q Piccept S Q" be the set of states that have ever appeared in the computation trace of an accepted string x E L(M*). Without loss of generality, we assume the alphabet size is 2 (Σ) 2).
Notation
7

---

Published as a conference paper at ICLR 2026
Algorithm.
Aime t, let Qi be the set states that appear in the noisy traces čyr (x1).... CM (244).
Let
B [Qc1 221Q. /1--a)+f.
At step the algorithm outputs minimal DFA M, that is (i) consistent with the history ..,.... (i.e., 2, E ((M) for all t) and (ii) has at most B, states.
We state few simple facts. First, the set of Qt must stabilize after some finite time step. Fact 4.1. There exists t' such that Q+ = Q² for all t 2 t'
Fix from Fact 4.1 and define == Qr. For any accepted string x E L(M*) with trace cas (I),
write
m(x)= == Iii car- cxr-(r) $ U..
That is, m(x) is the number of states that are not in U.
Fact 4.2. For every accepted x E L(M*) with length |ar] 2 ta we have m(x) S a/x/.
For state y E Q", define its graph distance to U (along DFA transitions) as
disty min(m 2 3 g E U and path of length m from o' to q).
The key step is to prove that every accepting state is not far from the set U Qr
Lemma 4.2. For any state Quccept we have
disty (q) < max 2 (1 101
Proof of Theorem 4.1
By Lemma 4.2 every E Qaccept lies within distance at most [I-a) |0| + la
from U Qr. We have assumed the alphabet size [Σ] 2, the size of Qaccept is at most
Qaccept! S 1Qr1 20 19.1+ B 1.
Therefore, from time L' onward, the hypothesis class considered by the algorithm is fixed finite family that contains I.(M)). Applying the finite-class identification argument (Fact 2.1) the algo- rithm will identify the target language in the limit. This completes the proof.
4.2 DETERMINISTIC PUSHDOWN AUTOMATA
Theorem 4.3, Consider the task of robust language identification in the limit with the set machines as DPDAs, then
There is an algorithm that guarantees succeed in the diminishing error rate regime;
Robust language identification is impossible in the constant error rate regime, for any con- stant a > 0.
Notation We use M* denote the target DPDA and Q" the set of states in M* Let Viccept C Q* be the set of states that have ever appeared in the computational trace of accepted string ((M)). We assume the alphabet for input string and stack string are binary. For each operation of DPDA, it reads input symbol, then pushes pops pushes-then- tithen-pppp the stack. A string is accepted if and only the stack is empty at the end for this to be true, we allow the DPDA pop stack symbols when it reaches the end of the string.
symbol top of
Remark 1 (DPDA normal form). Throughout Section 4.2 assume DPDAs are in normal form where each transition (1) reads either one input symbol or and (2) modifies the stack by at most one symbol (push or pop symbol). We also assume acceptance by empty stack. These assumptions ensure that for fixed alphabets and a state bound, the induced hypothesis class is finite, and they can be enforced by standard conversion the cost of polynomial blow-up in the number of states.
8

---

Published as a conference paper at ICLR 2026
Algorithm Let Qi be the set of states observed in the traces čM- (21), cM- (2x) up time t. Let 04 = 2-21 Let Mr be the set of DPDAS with number of states most
B. 1Qal (322 Re1l +fa,
+1
The algorithm outputs the minimal DPDA Mr E Mr that accepts $1..... St. As before, we show: Fact 4.3. The sei Qt is monotone non-decreasing and Qt C Q', Therefore, there exists time lo. such that Q = Qt for any lo-
We write S = s= 1Qtal and a = 2 from now on.
Definition 6 (Transition graph). Define the transition graph with the node set being the state set Q". There is a directed edge from a state a one step transition from to q', i.e. there exists input symbol in E [2], top stack symbol is E [2]. operation E [3], write symbol E [2], such that ö(g, (1, (g' u.. For any state q Vacepp define its
Q" to another state of E Q", if and only if there is
distance dist.s(g) to S as the length of the minimum path that starts from state in S and ends at
Our main result here is as follows.
Lemma 4,4. For any state E Veccept one has
dists(() S max fla, 20²) 2
The proof of Lemma 4.4 can be found Appendix B.2 The key idea is convert DPDA computa- tion trace to its corresponding Chomsky Normal Form (CNF), and then prove that the CNF tree can not be too large, otherwise there too many unobserved states in the CNF tree.
Proof Sketch of Theorem We first prove the correctness of our algorithm in the diminishing error regime. By Lemma 4.4 all acceptable states are at most max { 2a² far from the set S. By the definition of the transition graph (Definition ( each state has constant out degree (actually at most 32), so the total number of acceptable states is bounded by B; 1. The correctness of our algorithm then follows directly from Fact(2.1 for finite class language identification.
In the constant error rate regime, fix any constant a E (0, 1), and consider the following set of lan- guages L Usen L, where for any i E N, T., == {ani)an/a n S i} and T. = [a"/2n/a n E N). is possible construct DPDAs (Mr Ma such that M; recognizes I,, (i E Nu (oo)). For any string
an/2n/a the adversary would remove the first n steps such that the computa- tional trace reveals zero information regarding the core mechanism of [Mi]ie U Moc except the membership of x. Then, from the learner's perspective, the problem essentially reduces to the hard instance of Fact 2.2
4.3 TURING MACHINES
Theorem 4.5. Consider the task of robust language identification in the limit with the set machines Turing machines, then
There is an algorithm that guarantees to succeed when the number of errors is finite;
Robust language identification is impossible even in the diminishing error regime.
The algorithm, analysis and the hard instance for Theorem 4.5 are quite similar Theorem 4.3 due
to space constraints we defer the full proof to Appendix B.3
5 CONCLUSION AND FUTURE WORK
In this work we have studied the problem of identification in the limit augmented with a notion of chain of thought. Our results show strong theoretical benefit of utilizing CoT: while in Gold's

---

Published as a conference paper at ICLR 2026
original setting almost every interesting collection of languages is nor identifiable in the limit, in our setting all collections languages that are recognizable by Turing machines are identifiable in the limit with COT. Moreover, that underlie the collection of languages, there are identification algorithms that can handle varying amounts of noise in the COT. There are several interesting follow-up questions related to our work. Firstly, our results are asymptotic in nature. It is, thus, natural to try to find conditions under which one can prove quantitative bounds on the amount of time that is needed in order identify the target language with CoT information. A similar question can be asked in the setting of generation in the limit. While Kleinberg Mullainathan (202)) showed that, asymptotically, every collection is generatable, it is known that achieving correct generation might take arbitrarily long for several collections (Li et al. 2024). Hence, it would be interesting to see how CoT information can speed up the generation process. Relatedly, several works have studied trade-offs between generation with breadth and hallucinations Kleinberg & Mullainathan (2024); Kalavasis et al. (2024b a); Charikar & Pabbaraju (2024); Pealee al. (leinbrr & Wei (2025a). is intriguing to understand how the landscape of these trade-offs changes in the presence CoT information.
results show that, depending on the complexity of the machines
LCKNOWTEDGEEMENTS
This work was supported in part by AFSOR grant FA9550-23-1-0251 and ONR grant N000142212771.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Awni Altabaa, Omar Montasser, and John Lafferty. Cot information: Improved sample complexity under chain-of-thought supervision. arXiv preprint arXiv:2505.15927, 2025.
Antonios Anastasopoulos, Giuseppe Ateniese, and Evgenios M Kornaropoulos. Safe language gen- eration in the limit. arXiv preprini arXiv:2601.0m 108648, 2026.
Dana Angluin. Finding patterns common to a set of strings (extended abstract). In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pp. 130-141, New
York, NY, USA, 1979. Association for Computing Machinery. ISBN 978 450374335. doi: 10.
URL httpt:tttts/ttt wwwpei..rr10..00.0 1040/ 8001 000000155500440408 804406
Dana Angluin. Inductive inference of formal languages from positive data. Informa- doi: https://oi.oor//00
fion and Control, 45(2):117-135,
1980. ISSN 0019-9958.
0105500019-9958888)9022855 URL https:/ /www sci scienceirrect. wwwpe/eeeettttcceeeeeeeeeeeeeeee ccm/scinnce/////cccccccccccmcccc articee/p1//00119999998222
Yannan Bai, Debmalya Panigrahi, and Ian Zhang. Language generation in the limit: Noise, loss, and feedback. arXiv preprint arXiv:2507.1533 2025.
Moses Charikar and Chirag Pabbaraju. Exploring facets of language generation in the limit, 2024. URL httpps://aax....r/ppppppo//////s
153444
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, et al. Scaling instruction-iintuu lan- guage models. Journal of Machine Learning Research, 25(70):1-53, 2024.
Jason Gaitonde, Ankur Moitra, and Elchanan Mossel. Bypassing the noisy parity barrier: Learning higher-order markov random fields from dynamics. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pp. 348-359, 2025.
E. Mark Gold. Language identification in the limit. Information and Control, 10(5):447-474 1967. ISSN 0019-9958. doi: http:///w..orr//.o.oo///0/099999 /www
URL https:
Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. On union-closedness of language generation. arXiv preprint (501:::2006..6422 2025.
Mikael Møller Høgsgaard and Chirag Pabbaraju. Agnostic language identification and generation. arXiv preprint arXiv:2601.23258 2026.
Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz. and Nathan Srebro. A theory of learning with autoregressive chain of thought. In Conference on Learning Theory, pp. 1390-2430. PMLR, 2022.
Alkis Kalavasis, Anay Mchrotra, and Grigoris Velegkas. Characterizations of language generation with breadth. arXiv preprint 11Xi::2412.185300 pp. 3, 2024a.
Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. On the limits of language generation: Trade-offs between hallucination and mode collapse, 2024b. URL https://arxiv org/ abs/ 0oss/241.000 09642
Amin Karbasi, Omar Montasser, John Sous, and Grigoris Velegkas. (im) possibility of automated hallucination detection in large language models. arXiv preprint arXiv:250..17004, 2025.
Jon Kleinberg and Sendhil Mullainathan. Language generation in the limit. In Advances in Neural Informatinn Processing Systems, volume 37, 2024. URL HtRLhhtps::///// arxiv. / wwwpiiv.org/bbbr. abg./////bb/...///
06757
Jon Kleinberg and Fan Wei. Density measures for language generation. arXiv:2504. 14370, 2025a.
arXiv preprint
Jon Kleinberg and Fan Wei. Language generation and identification from partial enumeration: Tight density bounds and topological characterizations. arXiv preprint arXiv:25/ 1.X.5.2511.05295, 2025b.
11

---

Published as a conference paper at ICLR 2026
Steffen Lange, Thomas Zeugmann, and Sandra Zilles. Learning indexed families of recursive lan- guages from positive data: a survey. Theoretical Computer Science, 397(1-3):194 232, 2008. arXiv preprint
Aaron Li and Ian Zhang. arXiv:2601.21237, 2026.
Quantifying noise in language generation.
Jiaxun Li, Vinod Raman, and Ambuj Tewari. Generation through the lens of learning theory, 2024.
URL
absaabssaao /0oo/2241... 13714
Jiaxun Li, Vinod Raman, and Ambuj Tewari. On generation in metric spaces. arXiv preprint arXiv:2602.07710, 2026.
Kenneth Li, Aspen K Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, and Martin Watten- berg. Emergent world representations: Exploring sequence model trained synthetic task. ICLR, 2023.
Allen Liu and Ankur Moitra. Model stealing for any low-rank language model. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, pp. 1755-1761, 2025.
Eran Malach. Auto-regressive next-token predictors are universal learners. arXiv:2309.066 099999999999,.... 2023.
arXiv preprint
Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. Language generation with infinite contamination. arXiv preprint arXiv:2511.07417 2025.
Neel Nanda, Andrew Lee, and Martin Wattenberg, Emergent linear representations in world models of supervupe sequence models. arXiv preprint arXiv:2309.00941, 2023.
Hristo Papazov and Nicolas Flammarion. Learning algorithms in the limit. In Conference on Learn- ing Theory. PMLR, 2025.
Charlotte Peale, Vinod Raman, and Omer Reingold. preprint arXiv:2505.2/819 2025.
Representative language generation. arXiv
Ananth Raman and Vinod Raman. Generation from noisy examples.
arXiv preprint
MrXiv:2501.04179, 2025.
Michael Sipser. Introduction the theory of computation. ACM Sigact News, 27(1):27-29, 1996.
Keyon Vafa, Justin Y Chen, Ashesh Rambachan, Jon Kleinberg, and Sendhil Mullainathan. Evalu- ating the world model implicit in a generative model. Advances in Neural Information Processing Systems, 17:26941-26974 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. Chain-of -hain-of-thoougt prompting elicits reasoning large language models. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 24824 2022. URL httpss://prccsd/// org.://0.....aaaaaeeeeeeee--errr www.erenceecccccccocccccoocc pdf
Curran Associates, Inc.,
neur ps wttpppppccpppppppppppppppppppp.. httpp//errrieeeepeeeee/ee// 2002 [1L1://5601133222e11111111133333
Kaiyue Wen, Huaqing Zhang, Hongzhou Lin, and Jingzhao Zhang. From sparse dependence to sparse attention: Unveiling how chain-of-thought enhances transformer sample efficiency. In The Thirteenth International Conference on Learning Representations, 2025.
12

---

Published as a conference paper at ICLR 2026
A OMITTED PROOF FROM SECTION 3
Below, we give the proof of Theorem 3.1
Proof of Theorem 3.7 We now show that access perfect traces suffices to identify in the limit any language recognized by a deterministic Turing machine. We maintain a working TM M, (Q.. r. ot, qo. B, Fr) together with designated non-accepting reject sink state r. Intuitively, any transition entry not yet witnessed on an accepting trace is pessimistically set to jump to r; witnessed entries are overwritten to match 8"
Initialization. Set Qo = (go,r) Fo = 0, and To = (B)US Define do(g,7) = (r,7, R) for all q E Qo and y E To (and, say, do(r; 7) (r, 7, R) keep dg total).
Update on a positive example (Ire, c(x+)). Parse the trace and:
1. Add to Qt every state that appears in c(x:): add to I3 every tape symbol that appears in c(ze).
2. If the last configuration is in some accepting state qTt0 set Fi +- Ft-1 (ga00).
3. For each revealed step (g. 7) + 7', D) the trace, overwrite 6, (q, - 7 D). For any newly added pair (g, 7) still undefined after this pass, set (g (T, 7, to keep 6, total.
Determinism of M* implies no conflicts can arise when overwriting previously set entries.
Subset invariant. For all i, L(M)) S K. Indeed, any accepting of M, uses only (i) transitions copied verbatim from 8* because they appeared on some accepting trace, or (ii) default entries to r, which cannot lie on an accepting computation. Hence Mr never accepts string outside K.
Eventual completeness on the accepting support. Let S+ = {((. 7) E Q' x I (4, 7) is used on at least one accepting computation M
Since Q' and I* are finite, S+ is finite. For every (g. 7) S fix witness string ((g.7) E K whose accepting trace uses (g, 7). Each W(g.)) appears at some finite time, after which the update step overwrites de(g, 7) to 8 (g. 7). Let 1a be the latest such time over all (g.7) E S+. Then for all t t":
8e(g, 7) (" 7) for every (g, 7) S+,
and all states/symboollaaccptttngg states that ever occur on accepting runs have been added to Qr, Pe, Ft.
Convergence. Fix any E K and consider its accepting computation under M Every step of that computation uses an entry in S+. Therefore, for 2 L*, the same sequence of steps is valid accepting computation under M,. yielding K S L(M:). Combined with the subset invariant, we obtain ((M) = K for all > t* No further changes occur after t* (determinism prevents conflicting overwrites), so the hypothesis stabilizes, as required by Definitions 1 []ddd
B OMITTED PROOF FROM SECTION
B. OMITTED PROOF FROM SECTION
4.
Proof of Fact 4.1 The sequence Q1 S Q2 C ... is monotone increasing and bounded above by the
finite set Q*: hence it stabilizes.
Proof of Fact 4.2 The edit distance between čM- (x) and the actual trace eas- (x) is most a///] By the definition of t'. e (z) only contains states in U, while there are m(x) states of car- (wr-(x) that not in U. By the finite emor rate assumption, must have m(x)) S al/c].
13

---

Published as a conference paper at ICLR 2026
Proof of Lemma 4.2
Consider any state q Qiccept and take the shortest accepted string It
suffices to consider the case that |a] 2 |&al (otherwise disty la). Consider its computation trace CM- (x) ;= Cpre o q o Cauf, both the prefix Cpre and the suffix Csuf of the position is a simple path (otherwise the string be shortened), therefore, one has
Kí CM (x); E UH - 2/0).
By Fact 4.2
we have
m(x)
2
x S 2 a
a 2
|0|
[
[
Hence, we have disty (g) I |2|| S
2
10% this completes the proof.
(1-a)
B.2 OMITTED PROOF FROM SECTION
Definition (CNF tree). For any two states p. 9 E Q", we introduce a non-terminal Ap.g intended to generate precisely the strings that the DPDA reads, starts with state ends with state q. and leaving the original stack untouched. This similar the standard conversion Chomsky normal form and generates grammar rules of
Ap.g Ap. Ar.g E Q"
Ap. - aA,, a
Given an accepted string x. we can generate a unique trinary tree according to the the grammar, and we denote this tree (xx).
Proof of Lemma 4.4 Let E Quccept be any acceptable state. Among all accepted strings whose computation visits the state v, pick one of minimum length and denote the string by x. | S la then it holds trivially that dists(v) la- Hence, it suffices to consider the case that |ar| 2 la By our assumption the edit distance between cM-(x) and Cy- (æ) at most a a/cx- (x) J. Let = T(x) be the CNF derivation tree of string æ under Definition 7 Define the principal path as any root- to-internal-ne path ending at the node N₂ labeled by some Ap. with E {p, 4). Let H be the number of internal nodes on this path and [ be the size of the tree.
Lemma B.1 (Non repetition). Consider any path P in the tree (not necessary leaf to the root), then there is no repetition for P,
the path P has no intersection with the principal path
. the principal path.
Here no repetition means for any Ap.ay Avd E P, Apo + Ag
Proof. We prove by contradiction. Suppose there are two states Ap. = Ap.g's Ap.g. Ag E P, then consider the string x' that removes the Ap. Apr.g (suppose Ap.q is closer to the root), x' is an accept string shorter than moreover, Ap. An. does not contain N.. This is because, (1) when is the principal path, N, Ap (2) when P has intersection with the principal path, N, & Ap.q. Therefore, the string x' is shorter than x and also contains the state v. This is contradiction.
We treat cases based the size of T.
14

---

Published as a conference paper at ICLR 2026
By Lemma B.1 along the principal path, at most s² nodes can be labeled by variables Ap.s whose both endpoints p. q lie S therefore at least 22 nodes involve new state in their endpoints. Here we say state q new state if q Vaccept S. Each such node forces a visit to new state in the accepting computation.
Case 1. The tree is relatively small comparing to the principal path: []] S 2"
If H > 3 then,
# ntw-state visits
H-
H/2
2
>2 = a,
(cM-(x)]
2/11
2 2
which contradicts the fact that CM- (x) has at most az ccM- (x) edit distance error, as it impossible remove all these new states.
Therefore, in case 1, we must have < s², and thus
dists(e) & | & [TI S 2 H
200
20
Case 2. The tree is relatively large comparing to the principal path: [1'] > 2# И We prove
this can not happen. Call a leaf off-path if its distance to the principal path is at least d = sh. In trinary tree, the number of leaves within distance of path of length H is most 3 H, hence the number of off -ath leaves is at least
T 3 -
T 30
2
[
[
For each off-path leaf u, let (T) the truncated chain of the last d edges on the leaf-to-root path. By definition (u)) is disjoint from the principal path. By Lemma B.1 there is no repetition any
π (u). Along (u), at most s² nodes have both endpoints in S, hence at least s2 2 d/2 = s $ nodes involve new state.
I there are at least [T]) such length path, each path contains 3²) /2/2 new states, and each states be counted for most 3 30d times, so there least
By Eq. equation
T /2
new states appear the computation trace, this violates the edit distance error assumption. Hence this case can not happen.
Combining the above two cases, we conclude that d4st,s()) S max max (fa, 20"} and complete the proof.
every state q E Qiccept lies within distance at most la 2- from the set Qe, By the definition of the transition graph (see Definition 6). the out-degree for each state at most 32, hence, we have
Proof of Theorem 4.3 Part 1. By Lemma 4.4
@iccept S |S| 32 = =1Q 332 +2 Bro -
where the second step follows from the definition that S = Qt and s (S]. Therefore, from time to onward, the hypothesis class considered by the algorithm is a fixed finite family that contains L(M"). Applying the finite-class identification argument (Fact the algorithm would identify target set of languages in the limit. This completes the proof.
We next prove that robust language identification is impossible for DPDAs in the constant error regime.
Proof Theorem 4.3 Part 2. Fix any constant E (0, 1), consider the following set of language == U, U Koe, where for any i E N,
K; {a" 2n// S i)
15

---

Published as a conference paper at ICLR 2026
and
Kx == {a"b2n/a n N}
Consider the set of DPDAs M = {Mihee U Mc and we would construct them such that Mj recognize exactly the set of language K; NU (oo)).
For i E N, the DPDA M, has i 2/a + Q11) states. Given an input string it first reads all the symbol in the beginning. It pushes all a symbol to the stack, and the same time, it uses the first i states to perform counting. If the number of a is greater than i, then it goes to a reject state after reading the (i + 1) 1. Upon reading the first symbol, the DPDA moves state if the number of it has read is at most i. After this, the DPDA starts to pop out the symbol in the stack.
temporary accept
particular, it pops out one a symbol after reading 2/ar symbol b (counting can be done using 2/a states). The DPDA M, would accept the string if it is in the temporary accept state and the stack is empty at the end.
The DPDA Mx has 2/a + O(1) states. It has the same transition function except it is always in the temporary accept state when reading the a symbol at the beginning.
It is easy to prove that M, recognize exactly the set K2, i... K, ((M). For the corruption, given string a"b2n/a, the adversary would remove the first state transitions, so the algorithm sees only the popping operations starting from the temporary accept state or the reject state. The number of deletion is so the edit distance error rate between the corrupt computation trace and the actual trace is n/(n + 2n/a) < a. The corrupted string reveals zero information regarding the DPDA, except the membership of the string. Hence, by simple reduction from the hard instance of Fact 2.2 it is impossible for language identification in the constant error rate regime.
B.3 OMITTED PROOF FROM SECTION
Notation We use M to denote the target Turing machine, Q" be the set of state in M Let
Quccept S. Q" be the set of states that have ever appeared in the computation trace of an accepted
string x E I(M"). We assume the alphabet for both input string and the writing tape are binary. We assume Turing machine has an input tape (read-only) and one write-tape, our results extend to multiple write-tapes casily. The transition function ò takes an input state q, tape value w E [2]. and outputs the transition state q', head movement m1, m2 E {-1.0, 0, 1} and write value w' E [2].
a.k.a. 5 x 2 2 Q x [3] x 3 x [2].
Algorithm Recall in the finite-error regime, there exist a pair of constants C E N and lc E N, such that for any example (2r, Cw-) with input length at least |ar| 2 fc. the edit distance between the actual trace cM- (z) and the corrupted trace ča- (I) is at most C.,
For any time step I, let Q: be the of states that appears in the noisy traces Tar- (x1), TM- (2x). Let M, be the set of Turing machines that have at most
B 1Q 72 +1
states. The algorithm at step & selects the minimal Turing machine in Me that accepts the strings
I1,...,
Similar as before, we have
Fact B.1. The set Qt is monotone non-decreasing and Q: C Q-, Therefore, there exists time to such that Q = Qro for any 2 to-
From now on, write 5 Quo, s -Q Next, we define the state transition graph over states Q". For any state g. E Q", there is a directed edge from to of if and only if there is a one step transition from g g'. More formally, there is an edge from q o' if there exists r, w E [2]. mi, m2 E [3]. w' E [2]. such that 8(g, w) (g', m., m2, w'). For any state q E Q define its distance to S as the length of the minimum path that starts from a state S and ends in q, i.c.
(g) minfm m 2 0: 3 g0 + 91
Im q, go U, Q1. Jm $ U
We have
16

---

Published as a conference paper at ICLR 2026
Lemma B.2. For any q E Q accepp have
dists(g) S max[lo, C}.
Proof. Consider an arbitrary accept string whose computation path visits the state q. the compu- tation path cM (x) & lc. then we already have (i) S lc. On the other hand, if cM- (x) 2 lc. have the edit distance between ČM- (z) and eM- (z) is at most C. We note that all states that appear in Car (x)) must in S, hence there are at most C states in cM- (x) that are not in (due to
the bound edit distance). This implies that dists(g) C and completes the proof.
Now we can wrap up the first part of Theorem 4.5
Proof of Theorem 4.5 Part I. By Lemma B.2 every state E Qaecept lies within distance at most la + C from the set Qu. By the definition the transition graph, the out-degree for each state is at most 72, hence, we have
@iccopel S -S1-7250+++1 -Q
72 --
Bio
Therefore, from time lo onward, the hypothesis class considered by the algorithm is fixed finite family that contains L(M*). Applying the finite-class identification argument (Fact the algo- rithm would identify the target of language in the limit. This completes the proof.
Next, we prove that robust language identification for TM is impossible in the diminishing error regime
Proof of Theorem 4.3 Part 2. We construct hard family of target languages and Turing machines. For E N. define Kg = {a, aa,...,, a²} and Kx == a" Consider the following set of Turing machines (Mo)) We would use a padding approach. For any N, the Turing machine M, has i (11) states. It first counts the number of a in the input string and compares with i, if the number of is greater than i, then it enters a reject state, otherwise, it enters the accept states. This takes at most [x]] steps in total. After this, M, would cycle in this state for |x|² steps. The definition of Mo is similar, except it skips the first stage, it always enter the accept state (as long as all symbol in the input are a).
It is casy to see that K; is exactly the set of string accepted by M,, i.c., K, = L(M) (i E (oo))) }). Consider the following adversary, for each accepted string, the corrupted trace сM (z) would delete all state transition in the first stage and contain only |xr cycle steps. We note the corrupt ratio 1/|x the error rate diminishing. On the other hand, the corrupted trace Cas reveals zero information about the state transitions of the TM, except the membership of æ. Hence, by simple reduction from the hard instance of Fact 2.2 it impossible for robust language identification the diminishing error regime.
17


Reviews:
[{"review_id": "9dyt7pjnUi", "reviewer": "Reviewer_6Cej", "summary": "This paper studies the benefit of CoT from the perspective of language identification in the limit with computation. While Gold proved the impossibility of recognizing most interesting language classes without computational traces, the authors show that as long as each $L\\in\\mathcal{L}$ is recognizable by some $M\\in\\mathcal{M}$, the class $\\mathcal{L}$ is identifiable by $\\mathcal{M}$ in the limit if computational traces are available. Furthermore, the authors consider robust language identification, concluding that identification is achievable with finite error, but robust language identification remains impossible even under diminishing error.", "questions": "See Weaknesses", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This work offers an interesting TCS perspective on the role of CoT, connecting the LLM phenomenon with the theory of language identification in the limit.\n\n2. The results on robust identification provide valuable insights into the significance of CoT quality.", "weaknesses": "1. The paper lacks intuitive explanations regarding how CoT contributes to identification.\n\n2. There appear to be conceptual gaps between the theoretical model and realistic CoT. For example, the paper’s model consider enumeration over a language, whereas real-world CoT operates on individual instances (i.e., strings $x\\in L$). Moreover, while the robust identification results highlight sensitivity to noise, empirical studies suggest that other factors, such as CoT format or length, may outweigh the correctness of CoT.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OGYLWhhPAO", "reviewer": "Reviewer_evx1", "summary": "An existing result shows that only a very small set of languages can be identified in the limit (i.e., eventually the identifier produces the same prediction forever) from exclusively positive examples provided. The work in this paper demonstrates that a larger class, all Turing Complete languages, can be recognized in the limit when provided with an exact computational trace (the state of one machine which recognizes the language at every step of its computation). Additionally, it demonstrates that this is possible even if there are errors in the trace, with different bounds on the error rates depending on the class of languages discovered.", "questions": "The algorithm for identifying robustly only seems to me to use the traces solely to identify the number of states. Is this accurate? If so, it should be explicitly stated in the text, as this sounds like a much weaker assumption than having access to the full traces with errors. If not, the additional information gained should be discussed.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "While I did not precisely check every single aspect of the theorems, what I did check appears to be completely accurate, and the theorems are quite interesting in their results.\n\nThe fact that the computational trace enables a lot more identifiability is interesting\n\nThe text is written quite clearly", "weaknesses": "This is primarily a framing issue, but I don't really see the relationship between this work and chain of thought in particular, it seems to be mostly about utilizing information about intermediate states in computational models in order to theoretically learn languages in an unbounded computational setting (with no limits on time to process each sample or the number of samples). In practice, chain of thought uses a very small number of examples and an extremely bounded computation.\n\nMinor errors/suggestions:\n\nYou should emphasize early on that “constant number of errors\" means a constant per trace, not a constant overall.\n\nRevisiting the regular language example with traces might be helpful, it made the utility of the trace more obviously useful when I went through the example with a trace and realized that the main thing it provides is a distinction between a model that accepts everything (single accept state) and a model that accepts N things (many states).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qNTGAInHe9", "reviewer": "Reviewer_WbPo", "summary": "This paper proves theoretical results concerning language identification in the limit in the case when the learner is given an enumeration of positive strings plus the computational traces that demonstrate that an automaton for the language to be identified accepts each string (e.g., a sequence of states in a finite automaton). The main result of the paper is this: unlike the classical case consisting only of positive strings  without computational traces, in which case most interesting language classes are not identifiable, the class of computable languages is identifiable in the limit when computational traces are provided. The authors then prove results for cases when the computational traces contain a certain number of errors for the classes of regular languages, deterministic context-free languages, and computable languages.", "questions": "1. 088: Do you mean that the number of errors per trace is $O(1)$ with respect to length, not finite?\n1. Fact 2.2: In this example, what is the alphabet $\\Sigma$?\n1. Theorem 3.1: Do we assume all the TMs are deciders?\n1. 310: Does this work if the alphabet is not fixed to {0, 1} ahead of time?\n1. 380: How is it possible for $m(x)$ not to be 0? $U$ is already the set of all states that occur in all traces. Can different instances of the traces for the same $x$ be edited in different ways, or are they always consistent?\n1. 388: This statement doesn't make sense to me. Do you mean \"not every accepting state is from the set $U$\"?\n1. Def 6: What about non-scanning transitions?\n\nTypos:\n1. 267: the the\n1. 371: set states -> set of states", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, this is an interesting paper with significant, original theoretical results. As the authors point out, these results are relevant to the use of CoT to train LLMs. The paper is written clearly and does a good job of contextualizing itself amid prior work. The robustness results are quite interesting.", "weaknesses": "The paper would benefit from some clarifications; see my comments in the Questions section.\n\n1. A minor point, but I would point out in the abstract that you are assuming that the learner only has access to positive examples, not negative examples.\n1. 072: DPDAs correspond to DCFLs, not CFLs.\n1. 183: The definition of DPDA is missing constraints on $\\delta$ that make it deterministic. I think you need to allow $\\varepsilon$ as the popped symbol too.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8gUpiXazHL", "reviewer": "Reviewer_XJpB", "summary": "The paper extends Gold’s seminal formal language learning framework from learning only based on positive examples to learning based on positive examples and computational traces associated with them. This is relevant to modern language models as chain-of-thought traces have been theoretically linked to such execution traces, making the setting useful to study learnability of algorithms.\nThe authors find that, in stark contrast to Gold’s result, traces make large classes of languages, including all recursively-enumerable languages, learnable. The authors then study learnability under corrupted traces, and find that it makes the learning problem markedly harder; while regular languages remain learnable under a constant fraction of errors, context-free languages and Turing machines require much stricter restrictions on the corruption.", "questions": "- As you mention, the results are asymptotic in nature, which is okay. I was just wondering if you have any ideas for next steps, i.e., how one would proceed/extend the results to some complexity bounds? I imagine the methodology would have to be quite different.\n- Can you elaborate on the connection to generation in the limit? It seems like, since there are fewer impossibility results there, traces would not be as useful?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I believe the paper studies a very interesting and useful problem and puts a new spin on an old/classic setting \n\t- In particular, it provides another possible contributing factor behind how CoT helps improve models\n- The exposition and motivation are clear; it’s easy to discern what the paper’s contributions are, andthe  methodology was used/developed\n\t- For example, the proofs are first well-described on simpler models (finite-state automata)\n\t- The related work section is thorough and useful", "weaknesses": "- Although this is not a major drawback, I feel like the connection to generation in the limit, which first appears in the Introduction, is not really justified; I’m not sure how learning with traces is any more connected to generation in the limit than the original learning in the limit setting\n- Very minor, and I don’t think this undermines the theoretical contributions: It is slightly unclear how the results translate into practice; maybe at least describing how this could be used or tested in practice could be useful", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)