Research map / Large language models / Language, safety and interpretability
Ask, and it shall be given: On the Turing completeness of prompting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that prompting a single finite-size decoder-only Transformer is Turing-complete and nearly efficient, by encoding computable functions as prompts for a new model called 2-PTMs executed via chain-of-thought.
Problem
Theoretical understanding of the LLM prompting paradigm (one model, many tasks via prompts) is lacking; prior Transformer expressivity results are one-model-one-task.
Approach
Introduces two-tape Post–Turing machines (2-PTMs), an instruction-sequence model that can be encoded over a finite alphabet and is nearly as efficient as TMs; encodes any computable function's 2-PTM as a prompt, and constructs one fixed finite-size ReLU/layer-norm/hardmax-attention Transformer that executes prompts via CoT steps.
Key results
- A single finite-size decoder-only Transformer with a finite 23-token alphabet computes any computable function given a suitable prompt (Turing-completeness of prompting).
- Any TIME(t(n)) function is computed by the constructed Transformer within O(t(n) log t(n)) CoT steps; TIME_2(t(n)) within O(t(n)) CoT steps.
- Any TIME(t(n)) function is computed within O(log(n+t(n))) bits of precision; any P language is decidable with log precision.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use one finite-size Transformer with task-specific prompts instead of constructing a separate Transformer for each task | Prompting · All computable functions | Computability | Helped |
| Use a single prompted Transformer to compute TIME_2(t(n)) functions | Prompted Transformer Γ · TIME_2(t(n)) functions | CoT steps: O(t(n)) | Helped |
| Use a single prompted Transformer to compute general TIME(t(n)) functions | Prompted Transformer Γ · TIME(t(n)) functions | CoT steps: O(t(n)\log t(n)) | Helped |
| Use a single prompted Transformer to compute TIME(t(n)) functions | Prompted Transformer Γ · TIME(t(n)) functions | precision bits: O(\log(n+t(n))) | Helped |
| Use a single prompted Transformer to decide polynomial-time languages | Prompted Transformer Γ · P languages | precision bits: \log n | Helped |
| Simulate a general TM using a two-tape Post–Turing machine | 2-PTM · TIME(t(n)) functions | simulation steps: t(n)\log t(n) | Hurt |
Limitations
- Result is purely theoretical; no empirical evaluation with trained LLMs.
- Assumes exact arithmetic in the Transformer and hardmax attention abstraction of softmax.
- CoT complexity for general TMs is O(t(n) log t(n)), a logarithmic slowdown relative to all Transformers.
Experimental setup
Builds on: Wang machines Post-Turing machines Hennie-Stearns theorem Transformers with hardmax attention Turing-completeness results
Closest papers by meaning
- Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory (ICLR 2025 · similarity 0.87)
- Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiency (ICLR 2025 · similarity 0.87)
- Constant Bit-size Transformers Are Turing Complete (NeurIPS 2025 · similarity 0.87)
- Scaling Prompt Synthesis for Large Language Model Reasoning (ICML 2026 · similarity 0.87)
- Analyzing the Power of Chain of Thought through Memorization Capabilities (NeurIPS 2025 · similarity 0.86)
- Universal Length Generalization with Turing Programs (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.