Transformers alone are limited but agents can simulate any computer
On the Turing Completeness of Transformers and Agents
Computational Complexity
Summary
This paper studies how well transformers, a popular AI model used for understanding sequences like text, can perform complex reasoning tasks. The authors find that a single transformer model with fixed precision has limitations when given very long inputs and cannot perfectly simulate all computations that a real computer can do. However, they show that by combining transformers into an agent system with separate memory and decision components, these agents can mimic any computer and perform any computation. This means agents are more powerful than single transformers for tasks requiring unlimited memory and complex reasoning.
What this means in practice
- •For ai system designers: Design agent architectures with memory and execution modules to achieve full computational power beyond single transformers.
- •For software engineers: Understand the computational limits of single transformers when building AI systems handling long or complex input sequences.
A theory result. No direct application yet.
Authors
Yimu Qiao, Lijia Yu, Ruichen Qiu, Xiao-Shan Gao
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.