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

• URL: http://arxiv.org/abs/2605.19514v2
• Date: Wed, 27 May 2026 14:00:24 GMT
• Title: Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management
• Abstract summary: We show that different context-management methods can yield sharply different computational power.<n>We argue that context management is a central component that critically determines the computational power of real-world autoregressive Transformers.
• Score: 37.13981898340341
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many works make the eye-catching claim that Transformers are Turing-complete. However, the literature often conflates two distinct settings: (i) a fixed Transformer system setting, in which a fixed autoregressive Transformer is coupled with a fixed context-management method to process inputs of different lengths step by step, and (ii) a scaling-family setting, in which a family of different models (with increasing context-window length or numerical precision) is used to handle different input lengths. Existing proofs of Transformer Turing-completeness are frequently established in setting (ii), whereas real-world LLM deployment and the standard notion of Turing-completeness correspond more naturally to setting (i). In this paper, we first formalize the fixed-system setting, thereby providing a concrete characterization of how real-world LLMs operate. We then argue that results proved in the scaling-family setting provide theoretically meaningful resource bounds but do not establish Turing-completeness, thereby clarifying a common misinterpretation of existing results. Finally, we show that different context-management methods can yield sharply different computational power, and we advocate the position that context management is a central component that critically determines the computational power of real-world autoregressive Transformers.

Related papers

• The Transformer Revolution, Part 1: Dynamic Processing through Output-Weight Interconnections [0.0]
  We argue that Transformers construct and apply prompt-dependent transformations whose parameters are generated during inference.<n>The Transformer is interpreted as a system that transforms concepts by means of concepts.<n>Because the human neural system possesses mechanisms similar to those required for SIDPP, we argue that a form of SIDPP may, in principle, be realized in the cerebral cortex.
  arXiv  Detail & Related papers  (2026-08-04T16:53:59Z)
• Revisiting LRP: Positional Attribution as the Missing Ingredient for Transformer Explainability [53.21677928601684]
  Layer-wise relevance propagation is one of the most promising approaches to explainability in deep learning.<n>We propose specialized theoretically-grounded LRP rules designed to propagate attributions across various positional encoding methods.<n>Our method significantly outperforms the state-of-the-art in both vision and NLP explainability tasks.
  arXiv  Detail & Related papers  (2025-06-02T18:07:55Z)
• Transformers Are Universally Consistent [14.904264782690639]
  We show that Transformers equipped with softmax-based nonlinear attention are uniformly consistent when tasked with executing Least Squares regression.<n>We derive upper bounds on the empirical error which, in the regime, decay at a provable rate of $mathcalO(t-1/2d)$, where $t$ denotes the number of input tokens and $d$ the embedding dimensionality.
  arXiv  Detail & Related papers  (2025-05-30T12:39:26Z)
• Learnable Multi-Scale Wavelet Transformer: A Novel Alternative to Self-Attention [0.0]
  Learnable Multi-Scale Wavelet Transformer (LMWT) is a novel architecture that replaces the standard dot-product self-attention.<n>We present the detailed mathematical formulation of the learnable Haar wavelet module and its integration into the transformer framework.<n>Our results indicate that the LMWT achieves competitive performance while offering substantial computational advantages.
  arXiv  Detail & Related papers  (2025-04-08T22:16:54Z)
• Ask, and it shall be given: On the Turing completeness of prompting [47.08833920586575]
  Large language models (LLMs) have been revolutionizing machine learning and initiated the so-called LLM prompting paradigm.<n>Here, we present the first theoretical study on the LLM prompting paradigm to the best of our knowledge.<n>We show that prompting is Turing-complete: there exists a finite-size Transformer such that for any computable function, there exists a corresponding prompt following which the Transformer computes the function.
  arXiv  Detail & Related papers  (2024-11-04T11:26:38Z)
• Transformers are Efficient Compilers, Provably [11.459397066286822]
  Transformer-based large language models (LLMs) have demonstrated surprisingly robust performance across a wide range of language-related tasks.<n>In this paper, we take the first steps towards a formal investigation of using transformers as compilers from an expressive power perspective.<n>We introduce a representative programming language, Mini-Husky, which encapsulates key features of modern C-like languages.
  arXiv  Detail & Related papers  (2024-10-07T20:31:13Z)
• CSformer: Bridging Convolution and Transformer for Compressive Sensing [65.22377493627687]
  This paper proposes a hybrid framework that integrates the advantages of leveraging detailed spatial information from CNN and the global context provided by transformer for enhanced representation learning. The proposed approach is an end-to-end compressive image sensing method, composed of adaptive sampling and recovery. The experimental results demonstrate the effectiveness of the dedicated transformer-based architecture for compressive sensing.
  arXiv  Detail & Related papers  (2021-12-31T04:37:11Z)
• Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations [51.77000472945441]
  Long Short-Term Memory (LSTM) and Transformers are two popular neural architectures used for natural language processing tasks. In practice, it is often observed that Transformer models have better representation power than LSTM. We study such practical differences between LSTM and Transformer and propose an explanation based on their latent space decomposition patterns.
  arXiv  Detail & Related papers  (2021-12-16T19:56:44Z)
• SML: a new Semantic Embedding Alignment Transformer for efficient cross-lingual Natural Language Inference [71.57324258813674]
  The ability of Transformers to perform with precision a variety of tasks such as question answering, Natural Language Inference (NLI) or summarising, have enable them to be ranked as one of the best paradigms to address this kind of tasks at present. NLI is one of the best scenarios to test these architectures, due to the knowledge required to understand complex sentences and established a relation between a hypothesis and a premise. In this paper, we propose a new architecture, siamese multilingual transformer, to efficiently align multilingual embeddings for Natural Language Inference.
  arXiv  Detail & Related papers  (2021-03-17T13:23:53Z)
• Bayesian Transformer Language Models for Speech Recognition [59.235405107295655]
  State-of-the-art neural language models (LMs) represented by Transformers are highly complex. This paper proposes a full Bayesian learning framework for Transformer LM estimation.
  arXiv  Detail & Related papers  (2021-02-09T10:55:27Z)
• Variational Transformers for Diverse Response Generation [71.53159402053392]
  Variational Transformer (VT) is a variational self-attentive feed-forward sequence model. VT combines the parallelizability and global receptive field computation of the Transformer with the variational nature of the CVAE. We explore two types of VT: 1) modeling the discourse-level diversity with a global latent variable; and 2) augmenting the Transformer decoder with a sequence of finegrained latent variables.
  arXiv  Detail & Related papers  (2020-03-28T07:48:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.