acceptodds
Under review as a conference paper at ICLR 2027

On the Turing Completeness analysis of Transformers and Agents

Abstract

Transformers have emerged as the dominant architecture in sequence modeling, achieving remarkable success in natural language processing and reasoning tasks. While existing literature has established the Turing completeness of transformers under bounded input length, the reasoning power of a single transformer operating on inputs of unbounded length is not fully explored. In this paper, we theoretically investigate the reasoning limitations of a single transformer and the enhanced capabilities of agent systems. We show that a single fixed finite precision transformer cannot memorize certain Turing machines with inputs of arbitrary length, such as the arithmetic; and a single fixed infinite precision transformer trained with a random algorithm is not Turing complete with probability one under certain conditions. To overcome the limitation of a single transformer, we define a formal agent architecture consisting of decision, execution, and memory modules and show that for any Turing machine T, there exists an agent that can memorize T and is computationally the same as T. Thus, agents are Turing complete.

Primary area:
learning theory
Keywords:
TURING COMPLETENESS, TRANSFORMERS, AGENTS

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_8eAtOpenReview ↗
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
AuthorsOpenReview ↗

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∣)).O(t_T(x)+\operatorname{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∞\\{\mathbb{F}_{\mathbb{T},n}\\}_{n=1}^{\infty}, where each model is designed to simulate a Turing machine T\mathbb{T} up to a given input length nn. 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 NN requires storage proportional to NN 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 qq under our computational model. Increasing qq 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.

AuthorsOpenReview ↗

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."

AuthorsOpenReview ↗

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

O((ln⁡n)L−1n)O\left(\frac{(\ln n)^{L-1}}{n}\right)

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).

Reviewer_ioJtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2(+1)
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks whether one fixed transformer with chain of thought can simulate a Turing machine on inputs of unbounded length, noting that many positive results build a different transformer per length bound. It proves that a fixed finite-precision transformer cannot simulate "non-converging" machines (Theorem 4.1); that under infinite precision a one-token change moves the output by at most O(ln⁡L−1(n)/n)O(\ln^{L-1}(n)/n), a tight bound (Theorems 4.2, 4.4), so "non-tame" machines cannot be simulated with a fixed margin (Theorem 4.5); and that a transformer drawn from an absolutely continuous distribution memorizes such machines with probability zero (Theorem 4.6). An agent of finite-precision transformers with memory and linear-time tools is Turing complete (Theorem 5.1). An arithmetic experiment up to 30 operators favours a step-by-step agent (Figure 1).

Critical strengths

The question is well posed: the gap between a family of length-dependent transformers and one fixed transformer is real and clearly stated (Section 1), and Theorem 4.4's matching lower bound makes the sensitivity analysis sharp rather than an upper bound only. If the novelty relative to prior work were established, this would be a clean contribution.

Critical weaknesses

W1 (main concern). The infinite-precision limitations overlap with known results that are not cited. Hahn (TACL 2020) shows that under soft attention the influence of one input position decays with length, so such transformers cannot recognise languages like PARITY with confidence bounded away from chance. Theorems 4.2 and 4.5 are close to this, with a log factor per layer and a Turing-machine framing. Chiang and Cholak (ACL 2022) show layer normalization restores confidence; the architecture in Section 3.1 has none, and Appendix H already concedes that adding Heaviside activations and a ln⁡n\ln n scaling factor (Jiang et al., 2026) takes an architecture outside its results. Without a comparison, the delta over known work is unclear.

W2. The positive agent result comes from the tools. In Appendix G, vdv_d = fSearch extracts the symbols around the head marker and vrv_r, built on fReplace, rewrites memory, so the transformers only compute the finite transition function on a constant-size window. A finite controller with read-write access to an unbounded tape is a Turing machine by definition, so Theorem 5.1 is correct but nearly immediate, and the separation "a transformer is not Turing complete, an agent is" mostly reflects that the agent may overwrite memory while plain CoT can only append.

Questions for authors

Questions that could change my assessment:

Q1. What do Theorems 4.2 and 4.5 add beyond Hahn (2020), and do they hold if layer normalization is added to the Section 3.1 architecture (cf. Chiang and Cholak, 2022)?

Q2. How does Theorem 4.1 reconcile with Li and Wang (2025), which you cite as showing constant bit-size transformers are Turing complete? Which assumption differs?

Q3. If vdv_d and vrv_r could not locate or rewrite the head neighbourhood (e.g. append-only memory), would Theorem 5.1 still hold? This would show what the transformers contribute.

Suggestions for future work (not affecting my score):

Measure output sensitivity against input length in a real model and compare with the ln⁡L−1(n)/n\ln^{L-1}(n)/n rate. The single-model errors in Table 1 (GLM4.5-air over all 1,300 expressions of 1 to 30 operators) are ordinary ordering and arithmetic mistakes on short inputs, not evidence of the predicted dilution.

6 comments
AuthorsOpenReview ↗

Rebuttal for Weakness1 and Question1

Response to Reviewer

We thank the reviewer for their careful evaluation and constructive comments. We particularly appreciate the reviewer's recognition that "The question is well posed" and that Theorem 4.4 provides a matching lower bound. We agree that a clearer comparison with existing literature and a more precise explanation of the role of external tools would strengthen our paper. We address these concerns below.

W1 & Q1. Comparison with Hahn (2020) and LayerNorm

Response:

Regarding Hahn (2020).

We thank the reviewer for pointing out the closely related work of Hahn (2020), which we unfortunately overlooked. We apologize for this omission and will add the appropriate citation and discussion.

We acknowledge that the fundamental idea of sensitivity decay in soft-attention Transformers is not new. Hahn (2020) established limitations on the influence of individual input tokens and applied these observations to formal language recognition, 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, for the fixed-depth causal softmax Transformer architecture considered in our paper, Theorem 4.2 establishes the depth-dependent sensitivity upper bound

=O\left(\frac{(\ln n)^{L-1}}{n}\right).$$ Moreover, Theorem 4.4 constructs a matching lower bound, establishing that this rate is tight up to constant factors. **Second**, Theorem 4.5 applies this sensitivity bound to Turing machine memorization on inputs of unbounded length. It proves that a fixed Transformer cannot memorize a non-tame Turing machine with a uniform positive confidence margin, even when autoregressive CoT of arbitrary length is permitted. **Third**, using the sensitivity bound established in Theorem 4.2, Theorem 4.6 further removes the positive confidence requirement and establishes that the set of successful Transformer parameters has Lebesgue measure zero, under restrictions on the prescribed CoT rule family. This further implies a zero success probability for absolutely continuous parameter distributions. Therefore, our contribution is not the original observation of sensitivity decay, but its tight depth-dependent characterization within our model and its application to deterministic and measure-theoretic limitations on Turing machine memorization. **Regarding Chiang and Cholak (2022).** We distinguish between two cases according to the value of $\epsilon$ in LayerNorm. When LayerNorm uses a fixed $\epsilon>0$, it remains globally Lipschitz, with a Lipschitz constant independent of the input length. Consequently, the sensitivity analysis can be extended to fixed-depth Transformers with pre-norm LayerNorm, yielding the same asymptotic rate $$O\left(\frac{(\ln n)^{L-1}}{n}\right),$$ with a constant that additionally depends on $\epsilon$. In contrast, when $\epsilon=0$, LayerNorm is no longer globally Lipschitz and may amplify arbitrarily small differences. As demonstrated by Chiang and Cholak (2022), this mechanism can restore a fixed confidence margin in certain constructions. Therefore, our current sensitivity argument does not directly apply to this case, and Theorem 4.5 does not rule out the possibility of Turing machine memorization under such an architectural modification. Establishing such a positive result would, however, require an independent construction.
AuthorsOpenReview ↗

Rebuttal for Weakness1 and Question2

W1 & Q2. Comparison with Other Turing-Complete Transformer Architectures

Response:

Regarding Jiang et al. (2026).

Their construction also lies outside our architectural assumptions. The length-dependent ln⁡n\ln n attention scaling removes the uniform boundedness of attention logits required by our sensitivity analysis. In particular, this scaling allows softmax attention to exhibit hardmax-like selection behavior, thereby overcoming the attention dilution inherent in our model. Meanwhile, the Heaviside activation does not satisfy the Lipschitz condition. Therefore, their positive construction does not contradict our negative results.

Regarding Li and Wang (2025).

As discussed in our Introduction and Related Work, we have already cited Li and Wang (2025) as an existing Turing-completeness result. We thank the reviewer for highlighting the need to clarify why their positive result does not contradict our Theorem 4.1. The key distinction lies in the underlying Transformer architectures and computational assumptions.

Li and Wang (2025) employ hardmax attention, a sliding context window, and a specialized relative positional encoding to simulate a Post machine. In their construction, the sliding window acts as a queue: newly generated tokens enter the window while the oldest tokens are removed. Hardmax attention allows the model to select the oldest token exactly, while the feedforward network implements the finite-state transition.

Their positional encoding is designed to identify the oldest position in the window and depends on the window-length specification. Although the trainable parameters, width, and numerical precision remain fixed, this mechanism differs from the fixed softmax–RoPE architecture considered in our paper.

In contrast, Theorem 4.1 concerns Transformers with finite-precision softmax computation and RoPE under the explicit numerical model in Definition C.2. Its proof relies on the periodicity of finite-precision RoPE and the behavior of finite-precision attention normalization.

Thus, these results concern different computational models and are not contradictory. We will clarify these comparisons in the revised manuscript to better distinguish our contributions from prior work and explicitly state the architectural assumptions under which our theorems hold.

AuthorsOpenReview ↗

Rebuttal for Weakness2 and Question3

W2 & Q3. The Role of External Tools under Restricted Memory Operations

Question:

W2: The positive agent result comes from the tools. In Appendix G, vd=fSearchv_d=f_{\mathrm{Search}} extracts the symbols around the head marker and vrv_r, built on fReplacef_{\mathrm{Replace}}, rewrites memory, so the transformers only compute the finite transition function on a constant-size window. A finite controller with read-write access to an unbounded tape is a Turing machine by definition, so Theorem 5.1 is correct but nearly immediate, and the separation "a transformer is not Turing complete, an agent is" mostly reflects that the agent may overwrite memory while plain CoT can only append.

Q3: If vdv_d and vrv_r could not locate or rewrite the head neighbourhood (e.g. append-only memory), would Theorem 5.1 still hold? This would show what the transformers contribute.

Response:

We agree with the reviewer that external memory and tools play an essential role in establishing the Turing completeness of our Agent architecture. This is precisely the architectural distinction that our paper aims to investigate, with the broader goal of providing a rigorous theoretical foundation for practical Agent systems. In particular, external memory connects successive Transformer invocations and preserves computational states, allowing a fixed finite-precision Transformer to participate in computations of unbounded length.

However, the external tools in Theorem 5.1 perform only simple, general-purpose string operations. Specifically, the reading tool locates a local substring using special markers, while the writing tool replaces the corresponding substring in memory. These operations are independent of the target Turing machine's transition function δ\delta and can be implemented in linear time, as explicitly constructed in Appendix G. The fixed Transformer itself implements the state transitions. Thus, Theorem 5.1 provides a concrete realization of Turing completeness within a fixed Transformer–Agent architecture, together with explicit complexity bounds.

Furthermore, we show that these external tools can be further restricted while preserving Turing completeness. In our new construction, memory is strictly append-only, with

vr(M,z)=M⊕z,v_r(M,z)=M\oplus z,

and the reading tool only retrieves information from predetermined record positions, without searching for the tape head. The Agent constructs successive Turing machine configurations cell by cell: the reading tool retrieves three neighboring cells from the previous configuration, and the fixed Transformer computes the corresponding local transition. This construction requires

O((t+1)2)O((t+1)^2)

Transformer invocations and

O(∣x∣+(t+1)2log⁡(∣Q∣+2))O(|x|+(t+1)^2\log(|Q|+2))

memory for tt simulated steps. Therefore, head-marker search and in-place memory rewriting are not necessary for Turing completeness, at the cost of quadratic growth in Transformer invocations and memory usage with respect to the simulated running time.

A similar mechanism appears in previous CoT-based Turing-completeness constructions. For example, in Attention Is Turing Complete, attention tracks the tape-head position and retrieves the symbol most recently written at that position from the computation history, while the feedforward network implements the state transition. Although the generated sequence is append-only, the Transformer can still simulate modifications to previously visited tape cells. Thus, the main architectural difference lies in how memory access is implemented: internally through attention in previous constructions, or through simple external tools in our Agent architecture.

Reviewer_HvdjOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the computational power of a single fixed Transformer and Transformer based agents on inputs of unbounded length. Under its definition of finite precision, the paper proves that a single fixed Transformer cannot simulate a class of non-converging Turing machines. This class includes arithmetic tasks. For infinite precision models, the authors derive a tight sensitivity bound that decreases with input length. They then prove negative results under additional conditions. These include a uniform positive confidence margin, or an absolutely continuous parameter distribution together with a bound on the number of allowed CoTs. The authors also construct an agent with finite precision Transformers, external memory, and tools that run in linear time. It can simulate any target Turing machine with polynomial overhead. Arithmetic experiments show the potential benefits of repeated execution and external memory for longer computations.

Critical strengths
  1. The theoretical question is clear, and the results are substantial. The paper asks whether one fixed model can handle inputs of every length. It highlights whether the model structure or precision must change as the input grows. This gives a clearer account of the limits of a single model. In particular, the sensitivity upper bound and matching lower bound describe how local input changes propagate through attention layers.

  2. The assumptions behind the negative results have practical meaning. Finite precision and a fixed output margin are relevant to numerical computation and output stability. It is reasonable to ask a model to respond to input changes in a stable and distinguishable way. Limits on the number of CoTs can also describe structured reasoning with a fixed format or calculation order. These results can therefore help explain difficulties with long inputs. Still, the CoT growth condition and the parameter distribution assumption should be linked more clearly to specific settings.

  3. The agent setup is relevant to practical systems. Decision making, execution, external memory, and repeated model calls are common parts of agent workflows. The authors give bounds on precision, model size, and simulation overhead. The tools run in linear time and do not depend on the target Turing machine. They perform general operations such as searching, extracting data, and writing it back. The Transformer implements the target transition rules. The construction shows how the model and external components can form a more capable system.

  4. The theory offers useful guidance for system design. The paper suggests a useful approach: divide a long computation into local steps and maintain external state. The gains on longer arithmetic expressions support this idea. The finite experiments cannot establish Turing completeness, but they give the theoretical discussion some practical support.

Critical weaknesses
  1. Some definitions and notation need clarification. Corollary 4.3 does not specify the norm. The notation in Definition 4.4 is also ambiguous. Section 3.1 uses Fl for the l-th hidden layer, while Fk in the argmax formula refers to the k-th output component. Definition 4.7 would be easier to understand with an example. I could not find a definition of the fixed deterministic one step calculation rule in the main text before Corollary 4.7.

  2. The negative results could be explored further. Theorem 4.6 rules out simulation under restrictions on CoT. Theorem 4.5 does so under a confidence requirement. These conditions seem reasonable. Still, could the authors explore what happens without them? It would be useful to discuss whether an infinite precision Transformer can simulate a Turing machine when both restrictions are removed.

  3. The practical use of the agent needs more explanation. Section 5 does not explain whether the external programs vend, vd, vr, and vout are easy to construct. A clearer explanation would help readers assess how practical the proposed agent is.

  4. The experiments do not match the total computation budget. A single model response can generate up to 1,024 tokens. Each agent decision or execution call can generate up to 512 tokens, and the agent can make repeated calls. The agent thus has more calls and a potentially larger total generation budget. Some of the accuracy gain may come from this extra computation.

  5. Ablation studies are missing. The agent introduces task decomposition, external memory, context management, and repeated calls at the same time. The current experiments make it hard to tell which component contributes most.

Questions for authors

Could the authors extend the negative results by removing the restrictions on CoT and confidence? Please discuss whether an infinite precision Transformer can simulate a Turing machine without these restrictions.

3 comments
AuthorsOpenReview ↗

Rebuttal for Weakness1, 2, 3 and Question1

Response to Reviewer

We thank the reviewer for their thoughtful evaluation and constructive feedback. We particularly appreciate the reviewer's recognition of the strengths of our paper, including "The theoretical question is clear, and the results are substantial," "The assumptions behind the negative results have practical meaning," "The agent setup is relevant to practical systems," and "The theory offers useful guidance for system design."

We address the reviewer's concerns point by point below, hoping that our rebuttal addresses the concerns of the reviewer.

W1. Clarification of Definitions and Notation

Question (W1, excerpts):

Some definitions and notation need clarification. Corollary 4.3 does not specify the norm. The notation in Definition 4.4 is also ambiguous. Section 3.1 uses Fl for the l-th hidden layer, while Fk in the argmax formula refers to the k-th output component. Definition 4.7 would be easier to understand with an example. I could not find a definition of the fixed deterministic one step calculation rule in the main text before Corollary 4.7.

Response:

We thank the reviewer for pointing out these ambiguities. We agree that these definitions and notations could be clarified. We will revise Corollary 4.3 to specify the norm, clarify the confidence requirement in Definition 4.4, distinguish the notation for Transformer layers and output coordinates, and provide examples and explanations for Definition 4.7 and Corollary 4.7. We will address these issues in the revised manuscript.

W2 & Q. Infinite-Precision Transformers without CoT and Confidence Restrictions

Question:

W2: The negative results could be explored further. Theorem 4.6 rules out simulation under restrictions on CoT. Theorem 4.5 does so under a confidence requirement. These conditions seem reasonable. Still, could the authors explore what happens without them? It would be useful to discuss whether an infinite precision Transformer can simulate a Turing machine when both restrictions are removed.

Q: Could the authors extend the negative results by removing the restrictions on CoT and confidence? Please discuss whether an infinite precision Transformer can simulate a Turing machine without these restrictions.

Response:

We thank the reviewer for this important question. Theorems 4.5 and 4.6 investigate two complementary settings. Theorem 4.5 allows unrestricted autoregressive CoT but requires a uniform positive confidence margin, while Theorem 4.6 removes this confidence requirement at the cost of restricting the admissible CoT rule family, yielding a measure-zero result. Importantly, this result applies to any training algorithm, regardless of its optimization procedure, provided that the induced distribution over Transformer parameters is absolutely continuous with respect to Lebesgue measure. Under these conditions, the probability of obtaining a Transformer that memorizes the target Turing machine is zero.

The main difficulty in removing both restrictions lies in our sensitivity-based approach. Without a positive confidence margin, arbitrarily close logits may still produce different predictions. Without controlling the number of admissible CoT sequences, the measure-theoretic argument in Theorem 4.6 no longer directly applies.

Nevertheless, Corollary 4.7 suggests a possible direction: finding special input pairs with unique admissible CoT sequences may allow us to remove the CoT-count restriction in certain settings. Whether both restrictions can be removed simultaneously remains an open question, which we will clarify in the revised manuscript.

W3. Constructibility of External Programs

Question:

The practical use of the agent needs more explanation. Section 5 does not explain whether the external programs vend,vd,vr,voutv_{\mathrm{end}}, v_d, v_r, v_{\mathrm{out}} are easy to construct.

Response:

We thank the reviewer for this suggestion. In fact, Appendix G.1 already provides explicit constructions of the basic functions $ f_{\mathrm{Judge}}, f_{\mathrm{Search}}, f_{\mathrm{Replace}}, f_{\mathrm{Delete}}, $ all of which are computable in linear time. Appendix G.2 then combines these functions to construct $ v_{\mathrm{end}}, v_d, v_r, v_{\mathrm{out}}.$

We will add a brief explanation in Section 5 and refer readers to the detailed constructions in Appendix G.

AuthorsOpenReview ↗

Rebuttal for Weakness4 and 5

W4. Comparison of Total Computation Budgets

Question:

The experiments do not match the total computation budget. A single model response can generate up to 1,024 tokens. Each agent decision or execution call can generate up to 512 tokens, and the agent can make repeated calls. The agent thus has more calls and a potentially larger total generation budget. Some of the accuracy gain may come from this extra computation.

Response:

We thank the reviewer for pointing out this issue. To address this concern, we measured the total number of tokens generated across all Agent invocations and found that the observed totals were around 4,096 tokens in the evaluated runs. We therefore conducted additional experiments with a 4,096-token generation budget for the single-model baseline on Llama3.1-8B and Qwen3-8B.

The results show that the Agent continues to outperform the single model, particularly as the number of arithmetic operations increases. For expressions with 30 operators, the Agent achieves 37% accuracy compared with 0% for Llama3.1-8B, and 47% compared with 0% for Qwen3-8B.

Although this comparison does not strictly equalize total computational cost, it provides further evidence that the observed performance gap cannot be explained solely by the original 1,024-token generation limit.

Furthermore, our original GLM4.5-Air experiment provides additional evidence regarding the role of output truncation. Among the 352 single-model failures, only 11 were protocol failures (including output truncation and invalid formatting), while 341 were mathematical errors. This suggests that output truncation was not the dominant source of failure in that setting. We will report both the expanded-budget results and this error analysis in Appendix I of the revised manuscript.

W5. Missing Ablation Studies

Question:

Ablation studies are missing. The agent introduces task decomposition, external memory, context management, and repeated calls at the same time. The current experiments make it hard to tell which component contributes most.

Response:

We thank the reviewer for this suggestion. Our experiments aim to compare a standalone Transformer with the complete Agent architecture, rather than to evaluate the individual contributions of its components. In our framework, the decision, execution, memory, and read/write modules work together to implement the computational process. Directly removing an essential component would make the prescribed procedure undefined, rather than constitute a meaningful ablation. We will clarify this experimental scope and acknowledge that our current results do not isolate the contributions of individual components.

Dear Reviewer Hvdj,

Thank you for your time and effort in reviewing our paper. Your comments are valuable and have helped us improve the quality of our work.

As the author–reviewer discussion period is scheduled to close in about two days, we would be grateful if you could take a moment to review our rebuttal and let us know whether it addresses your concerns.

Thank you again for your time and consideration.

Best regards,
The authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.