mlsanityData to 7 Oct 2026

How Powerful are Decoder-Only Transformer Neural Models?

arXiv 2305.17026 ↗First posted 26 May 2023cs.CL cs.LGcited by 20

Not on the map. Why?

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.

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

Builds on

11 of 21 references.

References · 11

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2023GPT-4 Technical Reportcited by 18,132
  5. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  6. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  7. 2018Generating Wikipedia by Summarizing Long Sequencescited by 333
  8. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  9. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  10. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  11. 2023Memory Augmented Large Language Models are Computationally Universalcited by 45

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 8; 2025: 7; 2026: 5.

20 papers.

Sort:

By area:

  1. 2024Benchmark Data Contamination of Large Language Models: A Surveycited by 138
  2. 2024Ask, and it shall be given: On the Turing completeness of promptingcited by 10
  3. 2024Do Large Language Models Learn Human-Like Strategic Preferences?cited by 8
  4. 2025Optimal Control for Transformer Architectures: Enhancing Generalization, Robustness and Efficiencycited by 8
  5. 2024Large Language Model Recall Uncertainty is Modulated by the Fan Effectcited by 7
  6. 2025Cluster-Driven Expert Pruning for Mixture-of-Experts Large Language Modelscited by 6
  7. 2024Mitigating Sycophancy in Decoder-Only Transformer Architectures: Synthetic Data Interventioncited by 5
  8. 2024Investigating Expert-in-the-Loop LLM Discourse Patterns for Ancient Intertextual Analysiscited by 4
  9. 2026Large Language Model-Assisted UAV Operations and Communications: A Multifaceted Survey and Tutorialcited by 4
  10. 2024Foundation Models for Autonomous Robots in Unstructured Environmentscited by 3
  11. 2025Generative Large-Scale Pre-trained Models for Automated Ad Bidding Optimizationcited by 3
  12. 2025Large Language Model Integration with Reinforcement Learning to Augment Decision-Making in Autonomous Cyber Operationscited by 3
8 more
  1. 2025Unifying Two Types of Scaling Laws from the Perspective of Conditional Kolmogorov Complexitycited by 2
  2. 2025Investigating Human-Aligned Large Language Model Uncertaintycited by 2
  3. 2026Neural Weight Norm = Kolmogorov Complexitycited by 2
  4. 2024Revolutionizing Undergraduate Learning: CourseGPT and Its Generative AI Advancementscited by 1
  5. 2025LLMs as Agentic Cooperative Players in Multiplayer UNOcited by 0
  6. 2026Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Managementcited by 0
  7. 2026Leveraging BART to Assess CS1 C++ Programming Assignments using Rubric-based Criteriacited by 0
  8. 2026PANOPTICON: A PII-Based Assemblage of Naturalistic Output Tokens for Investigating Privacy Leakage Within LLM Context Windowcited by 0