# How Powerful are Decoder-Only Transformer Neural Models?

arXiv: https://arxiv.org/abs/2305.17026 · HTML: https://mlsanity.com/paper/2305.17026/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 21 references that are in the map.
- First posted on arXiv 26 May 2023.

## Builds on (most cited first, 11 of 11)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Are Transformers universal approximators of sequence-to-sequence functions?](https://mlsanity.com/paper/1912.10077/) (2019)
- [Generating Wikipedia by Summarizing Long Sequences](https://mlsanity.com/paper/1801.10198/) (2018)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [Memory Augmented Large Language Models are Computationally Universal](https://mlsanity.com/paper/2301.04589/) (2023)

## Built on by (most cited first, 20 of 20)

- [Benchmark Data Contamination of Large Language Models: A Survey](https://mlsanity.com/paper/2406.04244/) (2024)
- [Ask, and it shall be given: On the Turing completeness of prompting](https://mlsanity.com/paper/2411.01992/) (2024)
- [Do Large Language Models Learn Human-Like Strategic Preferences?](https://mlsanity.com/paper/2404.08710/) (2024)
- [Optimal Control for Transformer Architectures: Enhancing Generalization, Robustness and Efficiency](https://mlsanity.com/paper/2505.13499/) (2025)
- [Large Language Model Recall Uncertainty is Modulated by the Fan Effect](https://mlsanity.com/paper/2407.06349/) (2024)
- [Cluster-Driven Expert Pruning for Mixture-of-Experts Large Language Models](https://mlsanity.com/paper/2504.07807/) (2025)
- [Mitigating Sycophancy in Decoder-Only Transformer Architectures: Synthetic Data Intervention](https://mlsanity.com/paper/2411.10156/) (2024)
- [Investigating Expert-in-the-Loop LLM Discourse Patterns for Ancient Intertextual Analysis](https://mlsanity.com/paper/2409.01882/) (2024)
- [Large Language Model Integration with Reinforcement Learning to Augment Decision-Making in Autonomous Cyber Operations](https://mlsanity.com/paper/2509.05311/) (2025)
- [Large Language Model-Assisted UAV Operations and Communications: A Multifaceted Survey and Tutorial](https://mlsanity.com/paper/2602.19534/) (2026)
- [Foundation Models for Autonomous Robots in Unstructured Environments](https://mlsanity.com/paper/2407.14296/) (2024)
- [Generative Large-Scale Pre-trained Models for Automated Ad Bidding Optimization](https://mlsanity.com/paper/2508.02002/) (2025)
- [Unifying Two Types of Scaling Laws from the Perspective of Conditional Kolmogorov Complexity](https://mlsanity.com/paper/2501.06802/) (2025)
- [Investigating Human-Aligned Large Language Model Uncertainty](https://mlsanity.com/paper/2503.12528/) (2025)
- [Neural Weight Norm = Kolmogorov Complexity](https://mlsanity.com/paper/2605.10878/) (2026)
- [Revolutionizing Undergraduate Learning: CourseGPT and Its Generative AI Advancements](https://mlsanity.com/paper/2407.18310/) (2024)
- [LLMs as Agentic Cooperative Players in Multiplayer UNO](https://mlsanity.com/paper/2509.09867/) (2025)
- [Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management](https://mlsanity.com/paper/2605.19514/) (2026)
- [Leveraging BART to Assess CS1 C++ Programming Assignments using Rubric-based Criteria](https://mlsanity.com/paper/2606.03814/) (2026)
- [PANOPTICON: A PII-Based Assemblage of Naturalistic Output Tokens for Investigating Privacy Leakage Within LLM Context Window](https://mlsanity.com/paper/2607.22695/) (2026)

## Abstract (arXiv)

In this article we prove that the general transformer neural model undergirding modern large language models (LLMs) is Turing complete under reasonable assumptions. This is the first work to directly address the Turing completeness of the underlying technology employed in GPT-x as past work has focused on the more expressive, full auto-encoder transformer architecture. From this theoretical analysis, we show that the sparsity/compressibility of the word embedding is an important consideration for Turing completeness to hold. We also show that Transformers are are a variant of B machines studied by Hao Wang.