On the Turing Completeness of Transformers and Agents

Yimu Qiao, Lijia Yu, Ruichen Qiu, Xiao-Shan GaoarXiv 2026 · arXiv

TL;DR

This paper proves that a single, fixed transformer—even with infinite precision or Chain-of-Thought (CoT) reasoning—is fundamentally limited and cannot achieve Turing completeness when processing inputs of arbitrary length. However, by organizing finite-precision transformers into an agent architecture featuring external memory and basic tools, the system overcomes these limitations to achieve true Turing completeness.

What Problem Does This Paper Address?

While transformers have revolutionized AI reasoning, their theoretical boundaries are still being mapped. Existing literature shows that transformers are Turing complete under bounded input lengths or when using a family of different-sized transformers tailored to specific input lengths.

However, in practice, we deploy a single, fixed-size transformer to handle tasks of varying and unpredictable lengths. This paper addresses a critical gap: Can a single, fixed transformer process inputs of unbounded length successfully? Furthermore, do LLM-based agent workflows (which combine models with tools and memory loops) fundamentally expand the computational power of the underlying transformer?

Methods

The authors tackle these questions using a combination of rigorous mathematical proofs and empirical validation:

  1. Theoretical Analysis of Single Transformers:
  2. Finite-Precision: The authors analyze transformers where parameters and calculations are bounded by $q$ decimal places. They prove that precision loss causes Rotary Position Embeddings (RoPE) to become cyclic and causes attention mechanisms to suffer from numerical underflow.
  3. Infinite-Precision: For unbounded precision, they derive a tight sensitivity bound showing how much a transformer's output can change if a single input token is altered. They prove that as input length grows, the influence of any single token dilutes dramatically.
  4. Formal Agent Architecture Definition: The authors mathematically define an agent system consisting of:
  5. A Decision Module (a transformer acting as a planner).
  6. An Execution Module (a transformer acting as a worker).
  7. A Memory Module (to store state sequences).
  8. Linear-time tools (for string manipulation, stop-checking, and memory writing).
  9. Experimental Validation: They evaluate three modern LLMs (Llama3.1-8B, Qwen3-8B, and GLM4.5-air) in two setups: a "Single Model" setup (one-shot generation with CoT) and an "Agent" setup (the formalized iterative loop).

Datasets

The authors used a synthetic arithmetic benchmark called Arith to evaluate the models.

  • Composition: It contains 1,300 mathematical expressions.
  • Variability: The expressions scale from 1 to 30 arithmetic operators, covering addition, subtraction, multiplication, division, and mixed operations.
  • Purpose: This dataset allows precise control over computation length and provides unambiguous ground-truth answers (integers or reduced fractions) to measure exactly where single models break down compared to agents.

Key Insights and Ideas

  • The "Attention Dilution" Effect: For infinite-precision transformers, the paper proves that local perturbations dilute at a rate of $\frac{\ln^{L-1}(n)}{n}$ (where $L$ is depth and $n$ is length). As sequences grow longer, attention weights tend to become uniform, meaning the model literally "forgets" or fails to register the specific impact of distant tokens.
  • The Agent Escape Hatch: You do not need infinite precision or infinitely large models to achieve universal computation. Universal computation (Turing completeness) can be offloaded to the architecture (the agent loop) rather than residing entirely within the neural network weights.
  • Why CoT Fails on Long Inputs: Chain-of-Thought helps transformers solve complex serial problems, but standard CoT still forces the model to process everything within a single context window. On arbitrarily long inputs, the single transformer's internal mechanics eventually collapse due to precision limits or attention dilution.

Key Results

Theoretical Results

  • Theorem 4.1 & 4.5: A single fixed finite-precision transformer is not Turing complete, and an infinite-precision transformer cannot memorize non-tame tasks with positive confidence.
  • Theorem 5.1: An agent built using finite-precision transformers, a memory module, and linear-time tools is fully Turing complete and computationally equivalent to a Turing machine.

Empirical Results

When testing the Arith benchmark, single models suffered severe performance degradation as the number of operators scaled up, eventually collapsing toward zero accuracy. The agent architecture maintained significantly higher reliability.

  • At 30 operators, the Agent setup outperformed the Single Model setup by massive margins:
  • GLM4.5-air: +35 percentage points higher accuracy.
  • Llama3.1-8B: +23 percentage points higher accuracy.
  • Qwen3-8B: +18 percentage points higher accuracy.
Accuracy at 30 Operators:
Single Model: █ Near 0%
Agent (GLM):  █████████████ 83.38% (overall average)

Limitations and Future Work

  • Unassumed Infinite Precision: One remaining theoretical open question is whether an infinite-precision transformer can be proven Turing complete without making any assumptions regarding output confidence thresholds or randomized training algorithms.
  • Optimal Agent Design: The paper proves that an agent architecture is Turing complete, but it does not explore how to design the most efficient or optimal agent structure when the sizes of the internal transformers are strictly fixed.
  • Scale of Evaluation: The experiments serve as a theoretical proof-of-concept on arithmetic tasks rather than a massive, diverse agent benchmark.

Summary updated

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 reasonable 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 $\mathbb{T}$, there exists an agent that can memorize $\mathbb{T}$ and is computationally the same as $\mathbb{T}$. Thus, agents are Turing complete.
BibTeX
@misc{qiao2026turing,
  author = {Yimu Qiao and Lijia Yu and Ruichen Qiu and Xiao-Shan Gao},
  title = {{On the Turing Completeness of Transformers and Agents}},
  year = {2026},
  eprint = {2609.20335},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.20335},
}
Figure