Transformer 表达能力与图灵完备界

Transformer 表达能力上限、计算复杂性分类与图灵完备性理论边界 (Expressive Power, Circuit Complexity & Turing Completeness of Transformers / RASP & $TC^0$ 理论) 是理论计算机科学与大模型基础理论中证明自注意力模型“能算什么、不能算什么”的核心理论基石；三大核心理论定理：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 是突破 $TC^0$ 表达瓶颈、实现通用计算能力的充要条件。

从电路复杂性理论 (Circuit Complexity) 证明为什么固定深度的 Transformer 属于 $TC^0$ 类，因而无法在一步前向内求解 $N$ 位的奇偶校验 (Parity Problem)？

数学证明为什么当允许 Transformer 生成长度为 $O(N)$ 或 $O(N^2)$ 的思维链 Token 时，它能够模拟任意图灵机状态转移函数？

硬注意力 (Hard Attention) 与软注意力 (Soft Attention) 在状态机识别（正则语言 DFA vs 上下文无关文法 CFL）表达能力上的分界？

自注意力机制与图神经网络 (GNN / Message Passing) 的理论等价性：全连接自注意力如何被视作带动态边权重的完全图消息传递？

状态空间模型 (SSM / Mamba) 与线性注意力在表达复杂状态追踪（如 Associative Recall 关联记忆）上的理论容量界限与 Transformer 的对比？