mlsanityData to 7 Oct 2026

On the Computational Power of Transformers and its Implications in Sequence Modeling

arXiv 2006.09286 ↗First posted 16 Jun 2020cs.LG cs.CL stat.MLcited by 85

Not on the map. Why?

Abstract (arXiv)

Transformers are being used extensively across several sequence modeling tasks. Significant research effort has been devoted to experimentally probe the inner workings of Transformers. However, our conceptual and theoretical understanding of their power and inherent limitations is still nascent. In particular, the roles of various components in Transformers such as positional encodings, attention heads, residual connections, and feedforward networks, are not clear. In this paper, we take a step towards answering these questions. We analyze the computational power as captured by Turing-completeness. We first provide an alternate and simpler proof to show that vanilla Transformers are Turing-complete and then we prove that Transformers with only positional masking and without any positional encoding are also Turing-complete. We further analyze the necessity of each component for the Turing-completeness of the network; interestingly, we find that a particular type of residual connection is necessary. We demonstrate the practical implications of our results via experiments on machine translation and synthetic tasks.

Key facts. Cited by 85 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 5; 2023: 21; 2024: 19; 2025: 19; 2026: 14.

85 papers.

Sort:

By area:

  1. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  2. 2023Trained Transformers Learn Linear Models In-Contextcited by 331
  3. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  4. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
  5. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  6. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  7. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  8. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 110
  9. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  10. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  11. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 101
  12. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 85
38 more
  1. 2021Representing Numbers in NLP: a Survey and a Visioncited by 83
  2. 2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 82
  3. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  4. 2025Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thoughtcited by 73
  5. 2023JoMA: Demystifying Multilayer Transformers via JOint Dynamics of MLP and Attentioncited by 52
  6. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  7. 2023Memory Augmented Large Language Models are Computationally Universalcited by 45
  8. 2021On the Expressive Power of Self-Attention Matricescited by 44
  9. 2023The Closeness of In-Context Learning and Weight Shifting for Softmax Regressioncited by 41
  10. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 39
  11. 2023Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammarscited by 30
  12. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  13. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  14. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  15. 2024Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamicscited by 27
  16. 2024Universal Length Generalization with Turing Programscited by 25
  17. 2024DGR-MIL: Exploring Diverse Global Representation in Multiple Instance Learning for Whole Slide Image Classificationcited by 25
  18. 2023Latent Positional Information is in the Self-Attention Variance of Transformer Language Models Without Positional Embeddingscited by 23
  19. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  20. 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 21
  21. 2023How Powerful are Decoder-Only Transformer Neural Models?cited by 20
  22. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  23. 2024Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theorycited by 19
  24. 2025Constant Bit-size Transformers Are Turing Completecited by 19
  25. 2022AbductionRules: Training Transformers to Explain Unexpected Inputscited by 17
  26. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  27. 2024Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursioncited by 14
  28. 2024Autoregressive Large Language Models are Computationally Universalcited by 14
  29. 2025Sample Complexity and Representation Ability of Test-time Scaling Paradigmscited by 12
  30. 2023Transformers in Reinforcement Learning: A Surveycited by 11
  31. 2024Ask, and it shall be given: On the Turing completeness of promptingcited by 10
  32. 2021On the Regularity of Attentioncited by 9
  33. 2024Rethinking Transformers in Solving POMDPscited by 9
  34. 2025Softmax Transformers are Turing-Completecited by 9
  35. 2024Do Large Language Models Learn Human-Like Strategic Preferences?cited by 8
  36. 2025Sequential-Parallel Duality in Prefix Scannable Modelscited by 8
  37. 2024Models That Prove Their Own Correctnesscited by 6
  38. 2024Transformers As Approximations of Solomonoff Inductioncited by 6

50 most cited of 85 All 85 (JSON)