Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management

A new arXiv paper challenges the widespread claim that Transformers are Turing-complete, arguing that existing proofs conflate two distinct computational settings. The research clarifies that real-world LLM deployment operates under fixed-system constraints where context management critically determines actual computational power, rather than the idealized scaling-family setting used in most theoretical proofs.

This paper addresses a significant gap between theoretical computer science claims and practical AI system reality. The distinction between fixed-system and scaling-family settings resolves a fundamental ambiguity in how Transformer Turing-completeness is discussed across academic literature. Most published proofs assume a family of increasingly powerful models, whereas deployed LLMs operate with fixed architectural constraints and limited context windows.

The research builds on decades of computability theory work but applies it directly to modern autoregressive language models. Previous claims of Transformer Turing-completeness often glossed over implementation details, allowing for arbitrary precision arithmetic and infinite memory access—assumptions violated by practical systems. This work provides formal characterization of real-world constraints, establishing what computational tasks fixed Transformers can and cannot perform.

For AI developers and researchers, the findings reshape understanding of LLM capabilities and limitations. Context management emerges as a critical architectural component rather than a peripheral implementation detail. Different context strategies—such as sliding windows, retrieval-augmented generation, or hierarchical summarization—produce measurably different computational power. This has direct implications for system design choices and for predicting model behavior on complex reasoning tasks.

The paper's position advocates reframing how researchers discuss model capabilities. Rather than making broad Turing-completeness claims, the field should specify computational settings precisely and acknowledge practical constraints. This more rigorous approach helps AI engineers make informed decisions about architectural tradeoffs and helps researchers set realistic expectations for what fixed models can achieve without modification.

• →Existing Transformer Turing-completeness proofs often apply to scaling-family settings with multiple models, not the fixed-system setting of deployed LLMs.
• →Real-world autoregressive Transformers operate under fixed architectural constraints that fundamentally limit their computational power compared to theoretical ideals.
• →Context management method choice directly determines the actual computational capabilities of practical language models.
• →Most published Turing-completeness claims for Transformers conflate theoretical scalability with practical computational completeness, creating misleading implications.
• →Rigorous characterization of fixed-system constraints provides meaningful resource bounds and clarifies realistic capabilities of deployed LLM systems.