Metraipolis › archive › dc_1a680cf56fac

On the Turing Completeness of Transformers and Agents — arXiv:2609.20335

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.20335
License (as archived)
CC0-1.0
Archived
2026-10-10T05:45:26.526Z
SHA-256 of the archived text
43f6aac8b4a4a3032bbede20d9af56fe40fb588bcb81fc84faf500fd5d98348f
Stable URL of this page
https://metraipolis.com/documento/dc_1a680cf56fac

How to cite

On the Turing Completeness of Transformers and Agents — arXiv:2609.20335 — arXiv (en), https://arxiv.org/abs/2609.20335 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1a680cf56fac (Metraipolis archive dc_1a680cf56fac, sha256 43f6aac8b4a4a3032bbede20d9af56fe40fb588bcb81fc84faf500fd5d98348f)
BibTeX
@misc{dc1a680cf56fac,
  title = {On the Turing Completeness of Transformers and Agents — arXiv:2609.20335},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.20335},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1a680cf56fac; sha256 43f6aac8b4a4a3032bbede20d9af56fe40fb588bcb81fc84faf500fd5d98348f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20335. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.20335 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T05:12:38.406Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).