mlsanityData to 7 Oct 2026

On the Turing Completeness of Modern Neural Network Architectures

arXiv 1901.03429 ↗First posted 10 Jan 2019cs.LG cs.FL stat.MLcited by 129

Not on the map. Why?

Abstract (arXiv)

Alternatives to recurrent neural networks, in particular, architectures based on attention or convolutions, have been gaining momentum for processing input sequences. In spite of their relevance, the computational properties of these alternatives have not yet been fully explored. We study the computational power of two of the most paradigmatic architectures exemplifying these mechanisms: the Transformer (Vaswani et al., 2017) and the Neural GPU (Kaiser & Sutskever, 2016). We show both models to be Turing complete exclusively based on their capacity to compute and access internal dense representations of the data. In particular, neither the Transformer nor the Neural GPU requires access to an external memory to become Turing complete. Our study also reveals some minimal sets of elements needed to obtain these completeness results.

Key facts. Cited by 129 papers in the map (data through 7 Oct 2026). First posted on arXiv 10 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 18; 2022: 12; 2023: 27; 2024: 29; 2025: 22; 2026: 21.

129 papers.

Sort:

By area:

  1. 2021Transformers in Vision: A Surveycited by 1,009
  2. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  3. 2021Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depthcited by 411
  4. 2023Trained Transformers Learn Linear Models In-Contextcited by 331
  5. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  6. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
  7. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  8. 2023Looped Transformers as Programmable Computerscited by 224
  9. 2022Neural Networks and the Chomsky Hierarchycited by 214
  10. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  11. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  12. 2023Representational Strengths and Limitations of Transformerscited by 132
38 more
  1. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  2. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  3. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  4. 2023The Expressive Power of Low-Rank Adaptationcited by 100
  5. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  6. 2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 82
  7. 2025A Survey on Latent Reasoningcited by 71
  8. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  9. 2023Understanding In-Context Learning in Transformers and LLMs by Learning to Learn Discrete Functionscited by 62
  10. 2024Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning?cited by 60
  11. 2021Handcrafted Backdoors in Deep Neural Networkscited by 57
  12. 2022HYPRO: A Hybridly Normalized Probabilistic Model for Long-Horizon Prediction of Event Sequencescited by 57
  13. 2022Provably expressive temporal graph networkscited by 56
  14. 2022MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solverscited by 48
  15. 2023Memory Augmented Large Language Models are Computationally Universalcited by 45
  16. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 45
  17. 2021On the Expressive Power of Self-Attention Matricescited by 44
  18. 2023The Closeness of In-Context Learning and Weight Shifting for Softmax Regressioncited by 41
  19. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 39
  20. 2021Lipschitz Normalization for Self-Attention Layers with Application to Graph Neural Networkscited by 38
  21. 2021Vector Symbolic Architectures as a Computing Framework for Emerging Hardwarecited by 35
  22. 2023Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Inputcited by 32
  23. 2024Iteration Head: A Mechanistic Study of Chain-of-Thoughtcited by 31
  24. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  25. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  26. 2021Position, Padding and Predictions: A Deeper Look at Position Information in CNNscited by 26
  27. 2022Attention-based Neural Cellular Automatacited by 26
  28. 2024Universal Length Generalization with Turing Programscited by 25
  29. 2024How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMscited by 24
  30. 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 21
  31. 2024On the Complexity of Neural Computation in Superpositioncited by 21
  32. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  33. 2023How Powerful are Decoder-Only Transformer Neural Models?cited by 20
  34. 2024Do Efficient Transformers Really Save Computation?cited by 20
  35. 2023Dissecting Chain-of-Thought: Compositionality through In-Context Filtering and Learningcited by 19
  36. 2023Large Sequence Models for Sequential Decision-Making: A Surveycited by 19
  37. 2024Sample, estimate, aggregate: A recipe for causal discovery foundation modelscited by 19
  38. 2024Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theorycited by 19

50 most cited of 129 All 129 (JSON)