🎓 RS 算法研究员ID:
rs-expressive-power-turing-completenessTransformer 表达能力与图灵完备界
Transformer Expressive Power & Turing Limit
🎯核心定义
Transformer 表达能力上限、计算复杂性分类与图灵完备性理论边界 (Expressive Power, Circuit Complexity & Turing Completeness of Transformers / RASP & 理论) 是理论计算机科学与大模型基础理论中证明自注意力模型“能算什么、不能算什么”的核心理论基石；三大核心理论定理：1) 固定精度/固定层数 Transformer 的电路复杂性局限：标准恒定深度的 Transformer 本质上属于 $TC^0$ 复杂性类（由恒定深度、多项式大小的带阈值门电路组成），理论证明它无法解决非 $TC^0$ 问题（例如无法在恒定前向步内求解奇偶校验 Parity 判定、图连通性、动态规划或深层递归）；2) 思维链 (CoT) 的图灵完备性跃迁：当引入 Chain-of-Thought（自回归生成动态长度的思考 Token 作为外挂工作记忆纸带）并配合循环机制时，Transformer 的计算能力严格跃升为图灵完备 (Turing Complete)，等价于通用图灵机；3) RASP (Restricted Access Sequence Processing) 形式化语言为注意力计算提供了形式化原语抽象。
💡使用场景
大模型理论能力极限分析、为什么自回归思考链必不可少的理论证明、算法复杂度证明。
⚡解决的核心痛点
澄清了为什么单一前向传播绝对无法解决复杂的算法问题，在数学层面证明了 Chain-of-Thought 是突破 表达瓶颈、实现通用计算能力的充要条件。
🎯5 个高频面试考点 (Exam Points)
1
从电路复杂性理论 (Circuit Complexity) 证明为什么固定深度的 Transformer 属于 类，因而无法在一步前向内求解 位的奇偶校验 (Parity Problem)？
2
数学证明为什么当允许 Transformer 生成长度为 或 的思维链 Token 时，它能够模拟任意图灵机状态转移函数？
3
硬注意力 (Hard Attention) 与软注意力 (Soft Attention) 在状态机识别（正则语言 DFA vs 上下文无关文法 CFL）表达能力上的分界？
4
自注意力机制与图神经网络 (GNN / Message Passing) 的理论等价性：全连接自注意力如何被视作带动态边权重的完全图消息传递？
5
状态空间模型 (SSM / Mamba) 与线性注意力在表达复杂状态追踪（如 Associative Recall 关联记忆）上的理论容量界限与 Transformer 的对比？
🔗核心前置底层技术卡片 (点击穿透复习)
📖 关联深度指南:📄 rs-core-cheatsheet →
更新于 2026-08-14🎯
🚀 开始本考点专项刷题 ➔检验攻克程度：针对「Transformer 表达能力与图灵完备界」专属刷题排雷
做单选排雷题、推导选项机制，答错自动收录进专属错题本。