Transformer解决计算问题？人大团队指出上限取决于上下文管理

随着大语言模型能力不断演进，很多研究宣称证明 Transformer 具有解决任意可计算问题的能力。但这篇 ICML 2026 观点论文想先追问一个更基础的问题：这些研究里的 Transformer，是一个固定部署的模型，还是一族会随输入变长而变大的模型？在固定部署的模型里，系统的能力上限事实上取决于一个常被当成工程细节的部分：上下文管理（context management）。

过去一段时间，基于 Transformer 的大语言模型的能力飞速进化，再加上一系列宣称证明“Transformer 是图灵完备的”或者“Transformer 能模拟图灵机”的研究，“只要中间推理步骤足够多，Transformer 的计算能力就没有上限”这一说法在 AI 社区的讨论中被进一步放大。

近年宣称 Transformer 图灵完备或者能模拟图灵机的部分报道

近年宣称 Transformer 图灵完备或者能模拟图灵机的研究时间线

这个结论读起来很吸引人，仿佛我们天天用的大语言模型已经无所不能。但仔细检查这些文章会发现，“Transformer”一词其实并不总是指同一个对象。它可以指你此刻正在使用的 GPT、Claude、DeepSeek 这类模型，也就是那些上下文窗口长度固定、权重固定、数值精度固定的大语言模型；也可以指一个随输入长度增加而不断变大的理论模型族。

这个区别正是中国人民大学高瓴人工智能学院魏哲巍教授团队的一篇 ICML 2026 观点论文想要厘清的问题。

• 论文标题
• Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management
• 作者
• 崔冠宇（中国人民大学高瓴人工智能学院博士生）、魏哲巍*（中国人民大学高瓴人工智能学院教授）、何昆*（中国人民大学信息学院副教授）（*: 通讯作者）
• 论文地址
• https://arxiv.org/abs/2605.19514

这篇论文要区分的是下面这件事：

现有大量“Transformer 图灵完备”的证明，研究对象并非固定的 Transformer 模型。对于上下文窗口大小和数值精度都固定的模型，系统计算能力的上限，取决于一个长期被当作工程细节的部分——上下文管理。

现有研究的证明在各自设定下仍然成立；而问题是在传播或者解读时，具体的设定常常被省略了。论文要做的，是把这个被省略的前提重新摆到台面上。

大家说“图灵完备的 Transformer”，可能不是同一个东西

图灵机是一种抽象的计算模型。可以把它想象成一台按规则读写符号的机器。它有一条或多条纸带、一个或多个能左右移动的读写头、有限个内部状态，以及一套决定“读什么、写什么、往哪移动、切换到哪个状态”的规则。

图灵机示意图

图灵完备是计算理论中衡量计算模型能力的一把标尺。粗略地说，如果某一类模型足够强，能够模拟任意一台图灵机的运行，我们就称这类模型是图灵完备的。也就是说，它在计算能力上与图灵机等价，原则上可以计算任何可计算函数。

要谈一个对象是否图灵完备，绕不开它能处理任意长度输入这个前提。关键矛盾也正出在这里。真实的 Transformer 上下文窗口长度固定，数值精度也固定；在一次前向过程中，它天然只能“看到”有限长的内容。至于整个系统能否处理更长输入，还取决于外部的上下文管理方式。那么，已有的那些证明，是怎么得到“图灵完备”这个结论的？

论文认为，已有证明其实落在两种完全不同的设定里，对应着两种很不一样的“图灵完备”：

固定系统（fixed-system）：一个固定的预训练 Transformer，通过某种上下文管理方法处理不同长度的输入以及推理过程中的中间信息。这正是真实大语言模型的运作方式。

缩放族（scaling-family）：一族模型，其上下文窗口、数值精度或深度会随输入变长而变大。这类模型会用越来越长的上下文窗口、越来越高的数值精度去处理越来越长的输入。

很多被解读为“Transformer 图灵完备”的结果，其实是在第二种设定下证明的。而真正对应“（单个） LLM 是否图灵完备”这个问题的，是第一种。

证明“图灵完备”的两种设定：固定系统（左）vs 缩放族（右）

这个差别直接决定了结论能否对应真实 LLM。看上面这张动图，左边的固定系统设定中，输入再长，模型始终是同一个，靠上下文管理来周转，更接近真实部署中的 LLM；右边的缩放族设定中，输入每变长一截，就得换一个更大的模型，对应的是一族模型，不对应现实部署中的单个模型。因此，缩放族里证明出来的“通用性”，严格来说描述的是一整族模型的能力，并不能直接等同于某个固定模型的图灵完备性。

论文指出，缩放族的结果仍然有意义。它们回答的是资源需求问题，例如要解决某类问题，窗口要多长、精度要多高、网络要多深。但这和“我们正在用的某个固定模型是否能达到图灵完备”不是同一个问题。

真实 LLM 不是无限变大的模型族

要谈“真实模型能算什么”，先得把“真实模型”定义清楚。论文用三元组 (T, D, C) 来描述一个固定的 Transformer 系统：

T：固定的预训练 Transformer，上下文窗口长度、权重和数值精度都不变；

D：固定的解码规则，比如贪心解码；

C：上下文管理器（context manager），负责管理信息，包括在每一步决定把哪些 token 放进上下文窗口。

真实的大语言模型 = 一个固定的三元组 (T, D, C)

上下文管理器的重要性在于，当输入或当前中间信息的长度超过上下文窗口长度 N 时，模型不可能“一次看全”，这时必须有一个机制来决定窗口里装什么、旧信息怎么处理——这个机制就是 C。它平时藏在推理框架里，可能是 /compress、/compact 这样的命令，也可能是检索记忆等机制；总之，它们都是不同形式的 Harness。

在三元组 (T, D, C) 里，当 Transformer T 被锁定时，能改变整个系统“能算什么”的，主要是上下文管理机制 C。接下来要问的就是，换一种上下文管理，系统的计算能力会不会真的不一样？

会。只换上下文管理，系统能力就可能跨过好几个计算复杂度层级。

只换上下文管理，能力层级直接跃迁

论文分析了几种有代表性的上下文管理方式，并给出了对应的计算能力刻画。结论可以用下面这张“计算能力图”来概括：

不同上下文管理方式的计算能力

T 不变，只换 C，系统能力就会变。下面逐一来看这几种上下文管理方式。

① 摘要式上下文管理——常数空间

摘要式上下文管理是目前最常见的方式之一。当上下文快满时，让 Transformer 把窗口里的历史内容压缩成一个简短摘要，从而腾出空间。这正是 Gemini CLI、Claude Code、OpenAI Codex CLI 里 /compress、/compact 命令背后的思路。

图 1 展示的是摘要式上下文管理。当初始输入能全部放入上下文窗口时，模型按照正常的自回归方式解码新 token，并将其放入窗口；当上下文窗口即将填满时，系统加入一段压缩指令（通常是一段 prompt；为简化展示画成一个 token），将当前上下文压缩为短摘要。（若一开始的输入不能全部放入上下文窗口则将前缀压缩，再与后续内容拼接，此处省略。）

图 1 | 摘要式上下文管理：历史信息被压缩成摘要

论文中证明，这类采用摘要式上下文管理的系统，计算能力不超过常数空间图灵机。换句话说，无论输入多长，它的有效记忆至多只是固定窗口大小的常数倍。从形式语言的角度来看，它至多只能识别正则语言（REG），甚至无法可靠地判断长度足够长的两段字符串是否相同、识别回文、完成二进制加法。历史被反复压扁成一小段摘要，能力的天花板也就被锁死了。

② 追加式上下文管理——线性空间

所谓追加式上下文管理，是指把解码出的 token 放到整条待处理序列的末尾，同时把上下文窗口看作一个滑动窗口。

图 2 展示的是滑动窗口版本。新 token 追加到末尾；窗口满后，系统先移除最前面的 token，再把窗口外队列中第一个 token 放入上下文窗口。

图 2 | 追加式上下文管理：解码出的 token 追加到末尾，窗口满时向右滑动

论文中证明，这类采用追加式上下文管理的系统，计算能力等价于线性空间图灵机。从形式语言的角度来看，它能识别的语言恰好对应确定型上下文相关语言（DCSL）。

③ 外部存储与检索——图灵完备

当前很多大语言模型系统都会接入数据库、记忆模块等外部存储。它们在固定上下文窗口之外，再接一块无界的、可读写的外部存储，并在需要时把重要信息写入存储，或者把检索到的相关信息读回上下文。

图 3 是外部存储与检索工作方式的动画示意。某时刻触发了写过程，上下文管理器将部分 token 写入外部存储，然后继续自回归过程；随后触发检索过程，上下文管理器进行检索，并将结果放入上下文窗口。

图 3 | 外部存储与检索：窗口之外接一块可读写的无界存储

论文引用 Schuurmans（2023）的证明指出，如果自回归 Transformer 能对一块无界存储自由读写，它就达到了图灵完备。上下文窗口大小固定并不妨碍整体系统拥有图灵机的全部能力。

④ 工具调用——图灵完备

近期很多基于 Transformer 的 Agent 系统开始通过函数调用机制调用外部工具。它们一般是让模型生成一次工具调用，然后把计算外包给外部工具，再把结果回填进上下文。ToolFormer，以及 GPT、Claude、Gemini 中的 function calling 机制，都属于此类。

图 4 是这种上下文管理方式的动画示意。某时刻 Transformer 生成了一个函数调用，上下文管理器根据生成的参数调用工具，然后将结果放入上下文窗口。

图 4 | 工具调用：把计算外包给外部工具

论文点明，如果 C 被允许调用一个本身就图灵完备的工具（比如执行任意 Python 程序），那么整个系统都会平凡地达到图灵完备。

⑤ 多 token 解码 + 追加式上下文管理——图灵完备

第五种方式，是在追加式上下文管理的基础上，再放宽解码接口。Schuurmans 等人（2024）放宽了通常的一步一 token 设定，允许系统每一步最多生成 K 个 token，然后把这些 token 追加到序列末尾。

为了便于形式化，“每步最多生成 K 个 token”也可以改写成“每步固定生成 K 个位置”。其中，有些位置可以是特殊的空 token（用 ε 表示）。上下文管理器遇到 ε 时会直接跳过，不把它追加到序列末尾；这样一来，实际追加的 token 数量仍然可以在 0 到 K 之间变化。

图 5 展示了这个过程。三轮解码分别得到 (ε, ε)、(k, l)、(m, ε)。其中 ε 被丢弃，k、l、m 被追加到序列末尾。

图 5 | 多 token 解码：三轮分别解码 (ε, ε)、(k, l)、(m, ε)

论文引用 Schuurmans 等人（2024）的证明指出，当 K = 1 时，所得系统的计算能力与线性空间图灵机等价；而当 K ≥ 2 时，所得系统是图灵完备的。这说明，真正改变系统能力的未必是 Transformer 权重本身，也可能是“每步能生成几个 token”这样的解码接口。

把这五种方式放回那张谱系图就能看得更清楚。同一个固定的 Transformer T，配上摘要式上下文管理器，至多只有常数空间图灵机的能力；配上追加式上下文管理器，等价于线性空间图灵机；配上外部存储、工具调用或多 token 解码与追加式上下文管理，就成了图灵完备的系统。T 没有变，变的是 C，或 C 与 D 的组合，计算能力却跨越了三个复杂度层级。这也正是论文标题所说的，真实 Transformer 的图灵完备性高度依赖上下文管理。

那些刷屏证明，到底默认了什么？

用这个区分回看已有工作，论文梳理的多数“Transformer 图灵完备”、“Transformer 模拟图灵机”或“Transformer 通用性”的证明，都依赖两类缩放族假设。

缩放上下文窗口：假设任意长的输入以及中间结果都能放进上下文窗口，并参与自注意力计算；

缩放数值精度：假设内部表示的精度可以随输入长度增长，甚至直接使用无界精度的实数 / 有理数。

只要采用了其中任意一条，研究对象就已经从“一个固定模型”，悄悄滑向了“一族不断变大的模型”。表 1 总结了这些落在缩放族设定下的研究所做的上下文窗口长度与数值精度的假设。

表 1 | 落在缩放族设定下“图灵完备”证明所依赖的前提假设

那篇刷屏的“推理 token 够多就能解决任意问题”的 CoT 工作（Li et al., 2024），正落在这张表里——它同时用到了缩放窗口和缩放精度。这并不意味着它错了。问题在于，它证明的是缩放族意义下的能力，不能直接推出你手上那个固定 LLM 本身就是图灵完备的。

另外，论文还梳理了固定模型设定下的研究，并将这篇论文的新结果也放入其中做对比，形成了下面的表 2。

表 2 | 固定系统设定下不同上下文管理方式对应的计算能力

从单一模型到模型系统

论文最后强调，理论分析需要从 Transformer 权重本身，转向由权重、解码规则和上下文管理共同组成的系统 (T, D, C)。上下文管理这类 Harness，乃至把能力沉淀、复用为可调用单元的 skill，都是模型系统的一种实现方式。沿着这个视角，论文最后给出三点建议：

第一，谈论 Transformer 图灵完备时，请明确说明计算设定与假设。缩放族的结果对理解资源需求（上下文长度、精度、深度）很有价值，但不应被解读为某个固定真实模型的图灵完备性。

第二，理论研究应把“固定 Transformer + 不同上下文管理”组成的整体系统当作主要研究对象。既然真实部署的 LLM 就是固定窗口、固定精度的 Transformer，加上某种上下文管理方式，那么系统层面的能力刻画，理应得到更多关注。

第三，社区不应止步于基于理想化假设的定性图灵完备性分析，而应进一步以明确的资源预算和可学习性标准来补充对模型能力的刻画。图灵完备性只说明在某种编码下某个函数是否可计算，并不等于已经回答了模型是否能够习得、泛化并稳健地使用相应解法。

过去很多理论结果把注意力放在模型本体上，而这篇论文把上下文管理、工具调用、外部存储等系统组件放到计算模型里一起分析。这样看，同一个 Transformer 配上不同的 C，能力边界会完全不同，弱则连回文都判断不了，强则可以走到图灵完备。

资助信息：本成果受到国家自然科学基金（L2524018, U2241212, 92470128, 62472430）资助。