Research map / Architectures and efficiency / Attention and transformers
Constant Bit-size Transformers Are Turing Complete
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 constant bit-size transformers with sufficiently long context windows are Turing complete by simulating Post machines, and that the expressive power with window length s(n) exactly equals SPACE[s(n)].
Problem
Whether transformers' Turing completeness requires the bit-size (precision or embedding dimension) to grow with input length; and what resource (time vs. space) governs the context window needed for expressiveness.
Approach
Simulate Turing machines via Post machines (queue automata) so that a transformer's sliding context window acts as the queue; each CoT step attends to exactly the token s(n) positions earlier via a fixed relative positional encoding, so the model has constant size and precision, and the window length only needs to scale with space.
Key results
- Constant bit-size transformer (fixed precision and dimension c+8) with context window O(s(n)) simulates any s(n)-space TM, giving WINDOW[s(n)] = SPACE[s(n)] for non-decreasing s(n) >= n.
- Consequently WINDOW[poly(n)] = PSPACE, so a single constant bit-size transformer with polynomial window covers all PSPACE problems.
- The simulation uses O(t(n)·s(n)) CoT steps, each attending to exactly one token at fixed offset s(n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Scale the context window to O(s(n)) while keeping bit-size constant | Constant bit-size transformer · SPACE[s(n)] | expressive power: \mathsf{WINDOW}[s(n)] = \mathsf{SPACE}[s(n)] | Helped |
| Simulate a TM through a Post machine using a context window of length O(s(n)) | Constant bit-size transformer · TM simulation | CoT steps: O(t(n)\cdot s(n)) | Mixed |
Surprising findings
- Context window length needs to scale only with space complexity rather than time complexity, despite CoT length being O(t(n)·s(n)).
Limitations
- Simulation requires O(t(n)·s(n)) CoT steps, potentially prohibitive in practice.
- Uses a nonstandard relative positional encoding that depends explicitly on the assumed space bound s(n).
- Purely expressiveness result; learnability by standard training is not addressed.
Experimental setup
Baselines: Pérez et al. (2021) transformer Turing completeness Merrill and Sabharwal CoT results PENCIL Lag system simulation
Builds on: Post machines Turing completeness of transformers with chain-of-thought PENCIL
Closest papers by meaning
- Fixed Universal Transformers (NeurIPS 2026 · similarity 0.88)
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.88)
- Ask, and it shall be given: On the Turing completeness of prompting (ICLR 2025 · similarity 0.87)
- Efficiently Representing Algorithms With Chain-of-Thought Transformers (NeurIPS 2026 · similarity 0.87)
- Universal Length Generalization with Turing Programs (ICML 2025 · similarity 0.87)
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · 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.