🎓 Research ScientistID:
rs-expressive-power-turing-completenessTransformer Expressive Power & Turing Limit
Transformer 表达能力与图灵完备界
🎯Core Definition
The Expressive Power, Circuit Complexity & Turing Completeness of Transformers ( & RASP formalisms) establishes the mathematical boundaries of what self-attention can and cannot compute; the foundational theoretical landscape establishes: 1) Constant-Depth Transformer Circuit Limits: fixed-depth Transformers belong to the $TC^0$ complexity class (constant-depth threshold circuits), meaning they are theoretically incapable of solving non-$TC^0$ problems (e.g. Parity checks, graph connectivity, long-horizon dynamic programming) in a single feed-forward pass; 2) Turing Completeness via CoT: when augmented with Chain-of-Thought (autoregressively emitting unbounded reasoning tokens that act as external Turing tape memory), Transformer expressivity jumps to universal Turing Completeness; 3) RASP programming language formalizes attention as relational sequence primitives.
💡Use Cases
AI research scientist theoretical expressivity rounds, proving the mathematical necessity of Chain-of-Thought, and circuit complexity lower bounds.
⚡Key Problems Solved
Formally proves why single-pass next-token generation hits hard computational barriers and why Chain-of-Thought is mathematically necessary to unlock universal computation.
🎯5 High-Frequency Exam Points
1
Prove why fixed-depth Transformers are contained in and cannot compute -bit Parity in a single forward pass without CoT?
2
Prove that autoregressive Transformers with variable-length Chain-of-Thought generation are Turing Complete?
3
Contrast Hard vs Soft Attention in formal language theory across Regular Languages (DFA) and Context-Free Grammars (PDA)?
4
Explain the theoretical equivalence between Self-Attention and fully connected Graph Neural Network Message Passing with dynamic adjacency kernels?
5
Compare State Space Models (Mamba) vs Transformers in theoretical associative recall capacity limits?
🔗Foundational Prerequisite Cards (Click to Review)
📖 In-depth Guide:📄 rs-core-cheatsheet →
Updated 2026-08-14🎯
🚀 Start Card Practice ➔Test Your Knowledge: Practice Questions for "Transformer Expressive Power & Turing Limit"
Single choice pitfall questions with instant feedback and mistake tracking.
← Previous CardInference-Time Compute & Search ScalingNext Card →Sample Complexity & Rademacher Bounds