- Rating
- 2(+1)
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper considers fundamental limitations and capabilities of transformer-based systems in simulating Turing machines. First, the paper shows that finite precision transformers are unable to simulate arbitrary Turing machines. Second, the paper shows that, under certain conditions, the set of transformer parameters simulating Turing machines has measure 0. Third, the paper shows that an agentic system, augmenting the transformer with decision and read/write modules, can be Turing complete. Finally, experiments are run to compare the performance of the bare transformer and an agentic system on an arithmetic task.
Critical strengths
The paper is mathematically grounded
The paper is written clearly and the formalisms are rigorous and generally well-presented. The proofs are spelled out in detail in the appendix. These are probably the most important aspects of a theory paper at ICLR -- being sound and readable.
The theory is testable
The theory directly addresses an important architecture (transformer, agentic systems) and makes predictions about their limitations that can be tested. Thus the paper is directly relevant to the ICLR community.
Critical weaknesses
Paper's position is unclear
The paper cites in several places that previous works only consider Turing completeness over a bounded input length. However, the actually limitation (as the cited Cui et al. 2026 discuss in more detail) is not the bounded input length but the fact that the transformer's precision and positional encodings may vary with the input length.
On the other hand the agentic system the paper describes also varies with the input length -- the memory module varies in size according to O(t_T(x)+len(x)+log(|Q|)).
The non-fixed size of the transformer is a limitation in the previous literature, but the non-fixed size of the memory module in the agentic system is a requirement. It is unclear why the paper suggests one is ok but the other is bad.
Disconnectedness of results
There are a number of different theoretical results on the expressivity of both finite and infnite-precision transformers. There is also a result on learnability. There are also experiments.
The theoretical results suggest that
- on long contexts, finite-precision transformers will converge
- infinite precision transformers are not confident about their predictions
- training a transformer by randomly selecting parameters is nearly guaranteed to not result in a Turing machine simulator
The experiments suggest that the agentic system allows better performance, at longer lengths, on the arithmetic task. It is not clear at all how these experimental results relate to the theoretical results. The experiments are about performance, but it is not shown whether or not the failures are a result of convergence on long context or unconfidence of predictions. Furthermore the training result seems to not fit in the picture at all.
Questions for authors
Questions
- Can you comment on the use of growing memory in the agentic system's memory module, and why this would be more desirable than growing precision in the transformer Turing machine simulations from the literature?
- Can you clarify how the experiments directly your theoretical predictions? I understand that the theoretical results suggest there are limitations of non-agentic systems that can be overcome, but the experiments and error analyses seem completely disjoint from the specific limitations brought up in the theoretical results.
- Theorem 4.2 seems similar in spirit to Lemma 5 in https://aclanthology.org/2020.tacl-1.11.pdf. What are the differences?
5 comments
Rebuttal for Weakness2 and Question2
W2 & Q2. Connections between the Theoretical Results and Experiments
Question:
Disconnectedness of results
There are a number of different theoretical results on the expressivity of both finite and infnite-precision transformers. There is also a result on learnability. There are also experiments.
The theoretical results suggest that
- on long contexts, finite-precision transformers will converge
- infinite precision transformers are not confident about their predictions
- training a transformer by randomly selecting parameters is nearly guaranteed to not result in a Turing machine simulator
The experiments suggest that the agentic system allows better performance, at longer lengths, on the arithmetic task. It is not clear at all how these experimental results relate to the theoretical results. The experiments are about performance, but it is not shown whether or not the failures are a result of convergence on long context or unconfidence of predictions. Furthermore the training result seems to not fit in the picture at all.
Q2 (excerpts): Can you clarify how the experiments directly your theoretical predictions? I understand that the theoretical results suggest there are limitations of non-agentic systems that can be overcome, but the experiments and error analyses seem completely disjoint from the specific limitations brought up in the theoretical results.
Response:
We would like to clarify that our theoretical results and experiments are connected by a common research objective: understanding the computational limitations of fixed Transformers and how these limitations can be overcome through Agent architectures. In particular, Theorem 4.6 is not an isolated result about training dynamics, but a measure-theoretic extension of our sensitivity-based analysis that removes the positive confidence requirement under additional CoT restrictions. The experiments complement this theoretical investigation by comparing standalone Transformers and Agents on arithmetic tasks of increasing computational length.
1. The role of Theorem 4.6.
Theorem 4.6 is not intended to be an independent result about training dynamics. Rather, it provides a second route to establishing the limitations of infinite-precision Transformers, based on the sensitivity bound developed in Theorem 4.2.
The theoretical results are organized around one central question: whether a single fixed Transformer can memorize arbitrary Turing machines on inputs of unbounded length.
We approach this question through two different numerical models.
For finite-precision Transformers, Theorem 4.1 establishes an impossibility result for non-converging Turing machines under our finite-precision computational model.
For infinite-precision Transformers, Theorems 4.2 and 4.4 establish a tight sensitivity bound. Based on this result, we derive two further conclusions.
- Theorem 4.5 proves a deterministic impossibility result for non-tame Turing machines under a uniform positive confidence margin.
- Theorem 4.6 removes the positive confidence requirement. Under a fixed, prescribed family of CoT rules satisfying the theorem's growth restriction, it establishes that the set of successful Transformer parameters has Lebesgue measure zero.
If the parameter distribution induced by a training algorithm is absolutely continuous with respect to Lebesgue measure, Theorem 4.6 further implies that the probability of obtaining a successful model is zero.
Therefore, the training algorithm is not itself the main object of our analysis. Its role is to translate a measure-theoretic property of the parameter space into a probabilistic statement about the trained model.
2. The relationship between theory and experiments.
Our theoretical results characterize the computational limitations of fixed Transformers and the additional capabilities enabled by Agent architectures on unbounded inputs. Our experiments complement this analysis by comparing the two architectures on finite arithmetic tasks of increasing computational length. The observed performance differences illustrate the practical relevance of our theoretical investigation, rather than directly verifying specific mechanisms such as finite-precision periodicity or sensitivity decay. Indeed, Turing completeness cannot be established or refuted through finite experiments.
We will revise the Introduction, Contributions, Section 6, and Conclusion to clarify this distinction. In particular, we will replace overly strong statements such as "experimentally validate our theoretical results" with more accurate descriptions such as "provide proof-of-concept empirical evidence illustrating the architectural comparison."
Rebuttal for Question3
Q3. Comparison with Hahn (2020)
Question:
Theorem 4.2 seems similar in spirit to Lemma 5 in Hahn (2020). What are the differences?
Response:
We thank the reviewer for drawing our attention to Hahn (2020). We apologize for overlooking this relevant work and will include an explicit comparison in our Related Work section.
We acknowledge that Hahn (2020) established the fundamental observation that the influence of individual input tokens diminishes in soft-attention Transformers. The paper further applied this observation to formal language recognition problems, including PARITY and Dyck languages.
Our work shares a similar perspective on sensitivity decay but addresses a broader computational question. While Hahn (2020) focuses on formal language prediction, we investigate Turing machine memorization with potentially unbounded autoregressive chain-of-thought generation.
First, Theorem 4.2 establishes the depth-dependent sensitivity rate
for the fixed causal softmax Transformer architecture considered in our paper, compared with the full-attention architecture in Hahn (2020). Theorem 4.4 additionally provides a matching lower bound, showing that this rate is tight.
Second, rather than focusing on formal language recognition, Theorem 4.5 applies sensitivity decay to the memorization of non-tame Turing machines on inputs of arbitrary length, including settings with unrestricted autoregressive CoT under a uniform positive confidence margin.
Third, under restrictions on the prescribed CoT rule family, Theorem 4.6 establishes that the successful parameter set has Lebesgue measure zero without requiring a positive confidence margin. If the parameter distribution induced by a training algorithm is absolutely continuous with respect to Lebesgue measure, the probability of obtaining a successful model is also zero.
We therefore agree that the basic sensitivity-decay idea should be attributed to earlier work. Our contributions lie in establishing the tight depth-dependent rate for our architecture and deriving further consequences for Turing machine memorization. We will revise the Related Work and the discussion surrounding Theorems 4.2–4.6 to distinguish these contributions more explicitly from Hahn (2020).
Rebuttal for Weakness1 and Question1
W1 & Q1. Growing Memory versus Growing Numerical Precision
Question:
Paper's position is unclear
The paper cites in several places that previous works only consider Turing completeness over a bounded input length. However, the actually limitation (as the cited Cui et al. 2026 discuss in more detail) is not the bounded input length but the fact that the transformer's precision and positional encodings may vary with the input length.
On the other hand the agentic system the paper describes also varies with the input length -- the memory module varies in size according to
O(tT(x)+len(x)+log(∣Q∣)).
The non-fixed size of the transformer is a limitation in the previous literature, but the non-fixed size of the memory module in the agentic system is a requirement. It is unclear why the paper suggests one is ok but the other is bad.
Q1: Can you comment on the use of growing memory in the agentic system's memory module, and why this would be more desirable than growing precision in the transformer Turing machine simulations from the literature?
Response:
We thank the reviewer for pointing out our imprecise characterization of previous literature, and highlighting the distinction between growing numerical precision and growing external memory. However, we argue that these are fundamentally different approaches, and we will clarify this distinction in the revised manuscript.
In fact, as discussed in our Introduction, this distinction is precisely one of the motivations for our work. In length-dependent constructions, one may obtain a family of Transformers FT,nn=1∞, where each model is designed to simulate a Turing machine T up to a given input length n. However, this does not establish the Turing completeness of a single fixed Transformer. In practice, we typically use one fixed model to process inputs of different lengths, rather than constructing a different Transformer for each input-length bound.
We further clarify the distinction between these two computational resources from the following two perspectives.
1. Practical Feasibility.
Our central argument is that growing external memory provides a more practically feasible approach to extending computational capabilities than dynamically increasing numerical precision. Although both approaches are mathematically valid, constructing or maintaining a family of Transformers with input-length-dependent numerical precision is difficult to implement in practical systems. In contrast, expanding external memory is a natural and readily implementable operation in existing Agent architectures.
In particular, in our construction of Theorem 5.1, the Transformer parameters, architecture, and numerical precision remain fixed throughout the computation, while only the external memory grows. By enabling information to be stored and accessed across repeated Transformer invocations, external memory and tools extend the computational capabilities of the overall system without modifying the underlying Transformer. Our work therefore focuses on this practically motivated approach and aims to provide a rigorous theoretical foundation for such Agent architectures, as also motivated by Cui et al. (2026).
2. Resource Consumption.
From the perspective of computational resources, increasing numerical precision itself requires additional storage for Transformer parameters and intermediate numerical values. Expanding external memory likewise requires additional storage, but allocates it outside the Transformer rather than increasing the precision of its internal computations. Thus, both approaches involve growing memory consumption, although the additional resources are allocated differently. We do not claim that their exact resource costs are identical.
Moreover, even a standalone Transformer processing increasingly long sequences requires growing computational storage, including input representations, intermediate activations, and potentially KV caches. In particular, processing a sequence of length N requires storage proportional to N for its input representation alone. Therefore, the comparison is not between a Transformer with fixed storage and an Agent with growing storage, but rather between different ways of allocating additional computational resources. Furthermore, Theorem 4.1 applies to every fixed finite precision q under our computational model. Increasing q to any larger but still fixed finite value does not remove the impossibility result.
In summary, expanding external memory offers a more practical approach to achieving Turing completeness without modifying the underlying Transformer. We believe this distinction makes our theoretical results particularly relevant to real-world Agent architectures.