mlsanityData to 7 Oct 2026

Ask, and it shall be given: On the Turing completeness of prompting

arXiv 2411.01992 ↗First posted 4 Nov 2024cs.LG cs.CCcited by 10

Not on the map. Why?

Abstract (arXiv)

Since the success of GPT, large language models (LLMs) have been revolutionizing machine learning and have initiated the so-called LLM prompting paradigm. In the era of LLMs, people train a single general-purpose LLM and provide the LLM with different prompts to perform different tasks. However, such empirical success largely lacks theoretical understanding. Here, we present the first theoretical study on the LLM prompting paradigm to the best of our knowledge. In this work, we show that prompting is in fact 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. Furthermore, we show that even though we use only a single finite-size Transformer, it can still achieve nearly the same complexity bounds as that of the class of all unbounded-size Transformers. Overall, our result reveals that prompting can enable a single finite-size Transformer to be efficiently universal, which establishes a theoretical underpinning for prompt engineering in practice.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 39 of its 64 references that are in the map. First posted on arXiv 4 Nov 2024.

Builds on

39 of 64 references.

References · 39

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  4. 2016Layer Normalizationcited by 5,579
  5. 2021Finetuned Language Models Are Zero-Shot Learnerscited by 3,747
  6. 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,175
  7. 2021Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processingcited by 2,222
  8. 2022Transformers learn in-context by gradient descentcited by 714
  9. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 671
  10. 2023Trained Transformers Learn Linear Models In-Contextcited by 331
  11. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  12. 2023Transformers learn to implement preconditioned gradient descent for in-context learningcited by 274
27 more
  1. 2022Transformers Learn Shortcuts to Automatacited by 260
  2. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 256
  3. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  4. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  5. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 127
  6. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  7. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  8. 2024Discrete-state Continuous-time Diffusion for Graph Generationcited by 73
  9. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  10. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  11. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 65
  12. 2024How Efficient is LLM-Generated Code? A Rigorous & High-Standard Benchmarkcited by 39
  13. 2023Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoderscited by 32
  14. 2023Class-Imbalanced Graph Learning without Class Rebalancingcited by 29
  15. 2024Learning Universal Predictorscited by 29
  16. 2024Linear Transformers are Versatile In-Context Learnerscited by 28
  17. 2023Ensuring User-side Fairness in Dynamic Recommender Systemscited by 27
  18. 2024Universal Length Generalization with Turing Programscited by 25
  19. 2023How Powerful are Decoder-Only Transformer Neural Models?cited by 20
  20. 2024Logic Query of Thoughts: Guiding Large Language Models to Answer Complex Logic Queries with Knowledge Graphscited by 20
  21. 2024BACKTIME: Backdoor Attacks on Multivariate Time Series Forecastingcited by 18
  22. 2023Reconstructing Graph Diffusion History from a Single Snapshotcited by 13
  23. 2024Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimizationcited by 12
  24. 2024WAPITI: A Watermark for Finetuned Open-Source LLMscited by 12
  25. 2024Fair Anomaly Detection For Imbalanced Groupscited by 10
  26. 2024AIM: Attributing, Interpreting, Mitigating Data Unfairnesscited by 9
  27. 2013Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toycited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 7; 2026: 3.

10 papers.

  1. 2025A Survey on Latent Reasoningcited by 71
  2. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  3. 2025SelfElicit: Your Language Model Secretly Knows Where is the Relevant Evidencecited by 18
  4. 2025Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Trackingcited by 17
  5. 2026Prune as You Generate: Online Rollout Pruning for Faster and Better RLVRcited by 8
  6. 2025The End of Transformers? On Challenging Attention and the Rise of Sub-Quadratic Architecturescited by 3
  7. 2026Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidthcited by 3
  8. 2025Assessing the Limits of In-Context Learning beyond Functions using Partially Ordered Relationcited by 1
  9. 2025Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphscited by 1
  10. 2026Identifiability and Order-Dimension Limits of In-Context Learning on Partial Orderscited by 0