[JMLR 2021] Attention is Turing Complete：深度解析 Transformer 的计算极限

TL;DR

Transformer 仅仅是强大的“概率拟合机”吗？这篇由 Jorge Pérez 等人发表在 JMLR 的重磅论文给出了否定答案。文章从数学上严格证明了：只要给予合适的“尺子”（位置编码）和“精准的目光”（硬注意力），Transformer 本身就是一个通用的计算机，即具备图灵完备性。

背景定位：这是从计算理论视角对 Transformer 进行深度“体检”的标杆级工作。它超越了简单的性能刷榜，将 Transformer 放在了与通用计算机等同的学术坐标系中。

痛点深挖：为什么 Transformer 曾经被认为“很弱”？

在直觉上，Transformer 似乎天生残疾：

1. 顺序迷失：如果没有位置编码，Transformer 处理 (a, b) 和 (b, a) 的结果完全一致（Order-invariant）。
2. 比例陷阱：作者发现其具有“比例不变性”，即模型无法区分 aabb 和 aaabbb。这导致它连简单的偶数校验（Even parity）都做不到。

这种局限性使得人们怀疑，Transformer 是否只能做语意联想，而不能进行真正的逻辑逻辑运算？

核心直觉：如何用注意力模拟图灵机？

为了赋予其“灵魂”，作者提出了三个关键支柱：

1. 由位置编码构成的“内存地址”：使用包含 $i,1/i,1/i^2$ 的向量，让模型能通过数学运算精确锁定纸带的任何位置。
2. Hard-attention（硬注意力）：不再像 Softmax 那样“雨露均沾”，而是通过 $arg\max$ 直接精确聚焦到某一个特定单元格。
3. 残差连接作为“寄存器”：利用 $z=O(a)+a$ 的结构，将前一步的状态像接力棒一样传递下去。

架构解析

作者构造了一个特殊的架构，如下图所示：

(注：原文 Figure 1 展示了 Decoder 如何通过三层结构分别计算：1. 下一步状态；2. 读写头位置；3. 读取纸带符号)

• 第一层 Decoder：实现 M 的转移函数 $\delta (q,s)$，计算出新的状态 $q^{\prime }$ 和写入符号 $v$。
• 第二层 Decoder：通过累加移动位移 $m(i)$ 计算读写头的绝对位置 $c(i+1)$。
• 第三层 Decoder：回溯历史，寻找上一次读写头停留在当前位置的时间点，从而获取该位置最新的“纸带符号”。

实验与理论洞察：精度是把双刃剑

论文通过严格的 $ϵ-\delta$ 逻辑证明了该模型的能力。但一个关键的暴论是：固定精度下的 Transformer 不是图灵完备的。

(注：该图应展示不同精度和位置编码对模型识别非正则语言能力的影响)

关键结论：

• 任意精度（Arbitrary Precision）：这是通往图灵完备的通行证。在线实操中，如果硬件限制了浮点数精度，模型在处理无限长序列时终会崩溃。
• 位置编码的形态：位置编码不仅是点缀，它是算法逻辑的骨架。

深度洞察：这对未来的 AI 意味着什么？

这份研究不仅是理论上的自嗨，它揭示了为什么 Transformer 难以泛化到没见过的长度（Out-of-distribution Length）：因为目前的训练方式（Softmax, 固定精度）实际上是在用一个“有限状态机”去逼近“图灵机”。

未来的启发：

• 如果我们要让 LLM 真正学会数学证明或执行代码，或许应该重新审视 Hard-attention 的价值，或者开发能够模拟无限精度的表征方式。
• 残差连接的重要性被再次拔高——它不仅是为了解决梯度消失，更是逻辑链条得以延续的物理基础。

总结与局限

虽然本文证明了“能做”，但没说“好练”。手动构造的权重在实际反向传播中几乎不可能学出来。此外，任意精度的假设在硅基芯片上仍是一个理想化的挑战。不过，明白“极限在哪里”，正是开发者打破极限的第一步。