Research map / Architectures and efficiency / Attention and transformers
Softmax Transformers are Turing-Complete
Hongjian Jiang, Michael Hahn, Georg Zetzsche, Anthony Widjaja Lin
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| remove relative positional encodings for binary inputs (ablation) | SMAT binary · five arithmetic languages, test1/test2 (longer lengths) | exact-match accuracy: 100 -> 0.40 (Prime test1), 100 -> 0.00 (test2) | Hurt |
| remove relative positional encodings for binary inputs (ablation) | SMAT binary · in-distribution test0 | exact-match accuracy: 100 -> 95.00 (Prime), 100 -> 64.40 (Multiplication) | Hurt |
| unary representation with no positional encoding (NoPE) | SMAT · five arithmetic languages | length-generalization accuracy: 99.70-100 on test2 | Improved |
| add relative positional encodings for binary representation (ablation) | SMAT binary · five arithmetic languages | exact-match accuracy: 0.00 -> 100 (Multiplication test2) | Improved |
Closest papers by meaning
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.90)
- Universal Length Generalization with Turing Programs (ICML 2025 · similarity 0.88)
- Analyzing the Power of Chain of Thought through Memorization Capabilities (NeurIPS 2025 · similarity 0.88)
- Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers (ICML 2025 · similarity 0.88)
- Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages (NeurIPS 2024 · similarity 0.88)
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.87)
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.
