Transformer解決計(jì)算問(wèn)題？人大團(tuán)隊(duì)指出上限取決于上下文管理

隨著大語(yǔ)言模型能力不斷演進(jìn)，很多研究宣稱(chēng)證明 Transformer 具有解決任意可計(jì)算問(wèn)題的能力。但這篇 ICML 2026 觀點(diǎn)論文想先追問(wèn)一個(gè)更基礎(chǔ)的問(wèn)題：這些研究里的 Transformer，是一個(gè)固定部署的模型，還是一族會(huì)隨輸入變長(zhǎng)而變大的模型？在固定部署的模型里，系統(tǒng)的能力上限事實(shí)上取決于一個(gè)常被當(dāng)成工程細(xì)節(jié)的部分：上下文管理（context management）。

過(guò)去一段時(shí)間，基于 Transformer 的大語(yǔ)言模型的能力飛速進(jìn)化，再加上一系列宣稱(chēng)證明“Transformer 是圖靈完備的”或者“Transformer 能模擬圖靈機(jī)”的研究，“只要中間推理步驟足夠多，Transformer 的計(jì)算能力就沒(méi)有上限”這一說(shuō)法在 AI 社區(qū)的討論中被進(jìn)一步放大。

近年宣稱(chēng) Transformer 圖靈完備或者能模擬圖靈機(jī)的部分報(bào)道

近年宣稱(chēng) Transformer 圖靈完備或者能模擬圖靈機(jī)的研究時(shí)間線

這個(gè)結(jié)論讀起來(lái)很吸引人，仿佛我們天天用的大語(yǔ)言模型已經(jīng)無(wú)所不能。但仔細(xì)檢查這些文章會(huì)發(fā)現(xiàn)，“Transformer”一詞其實(shí)并不總是指同一個(gè)對(duì)象。它可以指你此刻正在使用的 GPT、Claude、DeepSeek 這類(lèi)模型，也就是那些上下文窗口長(zhǎng)度固定、權(quán)重固定、數(shù)值精度固定的大語(yǔ)言模型；也可以指一個(gè)隨輸入長(zhǎng)度增加而不斷變大的理論模型族。

這個(gè)區(qū)別正是中國(guó)人民大學(xué)高瓴人工智能學(xué)院魏哲巍教授團(tuán)隊(duì)的一篇 ICML 2026 觀點(diǎn)論文想要厘清的問(wèn)題。

• 論文標(biāo)題
• Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management
• 作者
• 崔冠宇（中國(guó)人民大學(xué)高瓴人工智能學(xué)院博士生）、魏哲巍*（中國(guó)人民大學(xué)高瓴人工智能學(xué)院教授）、何昆*（中國(guó)人民大學(xué)信息學(xué)院副教授）（*: 通訊作者）
• 論文地址
• https://arxiv.org/abs/2605.19514

這篇論文要區(qū)分的是下面這件事：

現(xiàn)有大量“Transformer 圖靈完備”的證明，研究對(duì)象并非固定的 Transformer 模型。對(duì)于上下文窗口大小和數(shù)值精度都固定的模型，系統(tǒng)計(jì)算能力的上限，取決于一個(gè)長(zhǎng)期被當(dāng)作工程細(xì)節(jié)的部分——上下文管理。

現(xiàn)有研究的證明在各自設(shè)定下仍然成立；而問(wèn)題是在傳播或者解讀時(shí)，具體的設(shè)定常常被省略了。論文要做的，是把這個(gè)被省略的前提重新擺到臺(tái)面上。

大家說(shuō)“圖靈完備的 Transformer”，可能不是同一個(gè)東西

圖靈機(jī)是一種抽象的計(jì)算模型。可以把它想象成一臺(tái)按規(guī)則讀寫(xiě)符號(hào)的機(jī)器。它有一條或多條紙帶、一個(gè)或多個(gè)能左右移動(dòng)的讀寫(xiě)頭、有限個(gè)內(nèi)部狀態(tài)，以及一套決定“讀什么、寫(xiě)什么、往哪移動(dòng)、切換到哪個(gè)狀態(tài)”的規(guī)則。

圖靈機(jī)示意圖

圖靈完備是計(jì)算理論中衡量計(jì)算模型能力的一把標(biāo)尺。粗略地說(shuō)，如果某一類(lèi)模型足夠強(qiáng)，能夠模擬任意一臺(tái)圖靈機(jī)的運(yùn)行，我們就稱(chēng)這類(lèi)模型是圖靈完備的。也就是說(shuō)，它在計(jì)算能力上與圖靈機(jī)等價(jià)，原則上可以計(jì)算任何可計(jì)算函數(shù)。

要談一個(gè)對(duì)象是否圖靈完備，繞不開(kāi)它能處理任意長(zhǎng)度輸入這個(gè)前提。關(guān)鍵矛盾也正出在這里。真實(shí)的 Transformer 上下文窗口長(zhǎng)度固定，數(shù)值精度也固定；在一次前向過(guò)程中，它天然只能“看到”有限長(zhǎng)的內(nèi)容。至于整個(gè)系統(tǒng)能否處理更長(zhǎng)輸入，還取決于外部的上下文管理方式。那么，已有的那些證明，是怎么得到“圖靈完備”這個(gè)結(jié)論的？

論文認(rèn)為，已有證明其實(shí)落在兩種完全不同的設(shè)定里，對(duì)應(yīng)著兩種很不一樣的“圖靈完備”：

固定系統(tǒng)（fixed-system）：一個(gè)固定的預(yù)訓(xùn)練 Transformer，通過(guò)某種上下文管理方法處理不同長(zhǎng)度的輸入以及推理過(guò)程中的中間信息。這正是真實(shí)大語(yǔ)言模型的運(yùn)作方式。

縮放族（scaling-family）：一族模型，其上下文窗口、數(shù)值精度或深度會(huì)隨輸入變長(zhǎng)而變大。這類(lèi)模型會(huì)用越來(lái)越長(zhǎng)的上下文窗口、越來(lái)越高的數(shù)值精度去處理越來(lái)越長(zhǎng)的輸入。

很多被解讀為“Transformer 圖靈完備”的結(jié)果，其實(shí)是在第二種設(shè)定下證明的。而真正對(duì)應(yīng)“（單個(gè)） LLM 是否圖靈完備”這個(gè)問(wèn)題的，是第一種。

證明“圖靈完備”的兩種設(shè)定：固定系統(tǒng)（左）vs 縮放族（右）

這個(gè)差別直接決定了結(jié)論能否對(duì)應(yīng)真實(shí) LLM。看上面這張動(dòng)圖，左邊的固定系統(tǒng)設(shè)定中，輸入再長(zhǎng)，模型始終是同一個(gè)，靠上下文管理來(lái)周轉(zhuǎn)，更接近真實(shí)部署中的 LLM；右邊的縮放族設(shè)定中，輸入每變長(zhǎng)一截，就得換一個(gè)更大的模型，對(duì)應(yīng)的是一族模型，不對(duì)應(yīng)現(xiàn)實(shí)部署中的單個(gè)模型。因此，縮放族里證明出來(lái)的“通用性”，嚴(yán)格來(lái)說(shuō)描述的是一整族模型的能力，并不能直接等同于某個(gè)固定模型的圖靈完備性。

論文指出，縮放族的結(jié)果仍然有意義。它們回答的是資源需求問(wèn)題，例如要解決某類(lèi)問(wèn)題，窗口要多長(zhǎng)、精度要多高、網(wǎng)絡(luò)要多深。但這和“我們正在用的某個(gè)固定模型是否能達(dá)到圖靈完備”不是同一個(gè)問(wèn)題。

真實(shí) LLM 不是無(wú)限變大的模型族

要談“真實(shí)模型能算什么”，先得把“真實(shí)模型”定義清楚。論文用三元組 (T, D, C) 來(lái)描述一個(gè)固定的 Transformer 系統(tǒng)：

T：固定的預(yù)訓(xùn)練 Transformer，上下文窗口長(zhǎng)度、權(quán)重和數(shù)值精度都不變；

D：固定的解碼規(guī)則，比如貪心解碼；

C：上下文管理器（context manager），負(fù)責(zé)管理信息，包括在每一步?jīng)Q定把哪些 token 放進(jìn)上下文窗口。

真實(shí)的大語(yǔ)言模型 = 一個(gè)固定的三元組 (T, D, C)

上下文管理器的重要性在于，當(dāng)輸入或當(dāng)前中間信息的長(zhǎng)度超過(guò)上下文窗口長(zhǎng)度 N 時(shí)，模型不可能“一次看全”，這時(shí)必須有一個(gè)機(jī)制來(lái)決定窗口里裝什么、舊信息怎么處理——這個(gè)機(jī)制就是 C。它平時(shí)藏在推理框架里，可能是 /compress、/compact 這樣的命令，也可能是檢索記憶等機(jī)制；總之，它們都是不同形式的 Harness。

在三元組 (T, D, C) 里，當(dāng) Transformer T 被鎖定時(shí)，能改變整個(gè)系統(tǒng)“能算什么”的，主要是上下文管理機(jī)制 C。接下來(lái)要問(wèn)的就是，換一種上下文管理，系統(tǒng)的計(jì)算能力會(huì)不會(huì)真的不一樣？

會(huì)。只換上下文管理，系統(tǒng)能力就可能跨過(guò)好幾個(gè)計(jì)算復(fù)雜度層級(jí)。

只換上下文管理，能力層級(jí)直接躍遷

論文分析了幾種有代表性的上下文管理方式，并給出了對(duì)應(yīng)的計(jì)算能力刻畫(huà)。結(jié)論可以用下面這張“計(jì)算能力圖”來(lái)概括：

不同上下文管理方式的計(jì)算能力

T 不變，只換 C，系統(tǒng)能力就會(huì)變。下面逐一來(lái)看這幾種上下文管理方式。

① 摘要式上下文管理——常數(shù)空間

摘要式上下文管理是目前最常見(jiàn)的方式之一。當(dāng)上下文快滿(mǎn)時(shí)，讓 Transformer 把窗口里的歷史內(nèi)容壓縮成一個(gè)簡(jiǎn)短摘要，從而騰出空間。這正是 Gemini CLI、Claude Code、OpenAI Codex CLI 里 /compress、/compact 命令背后的思路。

圖 1 展示的是摘要式上下文管理。當(dāng)初始輸入能全部放入上下文窗口時(shí)，模型按照正常的自回歸方式解碼新 token，并將其放入窗口；當(dāng)上下文窗口即將填滿(mǎn)時(shí)，系統(tǒng)加入一段壓縮指令（通常是一段 prompt；為簡(jiǎn)化展示畫(huà)成一個(gè) token），將當(dāng)前上下文壓縮為短摘要。（若一開(kāi)始的輸入不能全部放入上下文窗口則將前綴壓縮，再與后續(xù)內(nèi)容拼接，此處省略。）

圖 1 | 摘要式上下文管理：歷史信息被壓縮成摘要

論文中證明，這類(lèi)采用摘要式上下文管理的系統(tǒng)，計(jì)算能力不超過(guò)常數(shù)空間圖靈機(jī)。換句話說(shuō)，無(wú)論輸入多長(zhǎng)，它的有效記憶至多只是固定窗口大小的常數(shù)倍。從形式語(yǔ)言的角度來(lái)看，它至多只能識(shí)別正則語(yǔ)言（REG），甚至無(wú)法可靠地判斷長(zhǎng)度足夠長(zhǎng)的兩段字符串是否相同、識(shí)別回文、完成二進(jìn)制加法。歷史被反復(fù)壓扁成一小段摘要，能力的天花板也就被鎖死了。

② 追加式上下文管理——線性空間

所謂追加式上下文管理，是指把解碼出的 token 放到整條待處理序列的末尾，同時(shí)把上下文窗口看作一個(gè)滑動(dòng)窗口。

圖 2 展示的是滑動(dòng)窗口版本。新 token 追加到末尾；窗口滿(mǎn)后，系統(tǒng)先移除最前面的 token，再把窗口外隊(duì)列中第一個(gè) token 放入上下文窗口。

圖 2 | 追加式上下文管理：解碼出的 token 追加到末尾，窗口滿(mǎn)時(shí)向右滑動(dòng)

論文中證明，這類(lèi)采用追加式上下文管理的系統(tǒng)，計(jì)算能力等價(jià)于線性空間圖靈機(jī)。從形式語(yǔ)言的角度來(lái)看，它能識(shí)別的語(yǔ)言恰好對(duì)應(yīng)確定型上下文相關(guān)語(yǔ)言（DCSL）。

③ 外部存儲(chǔ)與檢索——圖靈完備

當(dāng)前很多大語(yǔ)言模型系統(tǒng)都會(huì)接入數(shù)據(jù)庫(kù)、記憶模塊等外部存儲(chǔ)。它們?cè)诠潭ㄉ舷挛拇翱谥猓俳右粔K無(wú)界的、可讀寫(xiě)的外部存儲(chǔ)，并在需要時(shí)把重要信息寫(xiě)入存儲(chǔ)，或者把檢索到的相關(guān)信息讀回上下文。

圖 3 是外部存儲(chǔ)與檢索工作方式的動(dòng)畫(huà)示意。某時(shí)刻觸發(fā)了寫(xiě)過(guò)程，上下文管理器將部分 token 寫(xiě)入外部存儲(chǔ)，然后繼續(xù)自回歸過(guò)程；隨后觸發(fā)檢索過(guò)程，上下文管理器進(jìn)行檢索，并將結(jié)果放入上下文窗口。

圖 3 | 外部存儲(chǔ)與檢索：窗口之外接一塊可讀寫(xiě)的無(wú)界存儲(chǔ)

論文引用 Schuurmans（2023）的證明指出，如果自回歸 Transformer 能對(duì)一塊無(wú)界存儲(chǔ)自由讀寫(xiě)，它就達(dá)到了圖靈完備。上下文窗口大小固定并不妨礙整體系統(tǒng)擁有圖靈機(jī)的全部能力。

④ 工具調(diào)用——圖靈完備

近期很多基于 Transformer 的 Agent 系統(tǒng)開(kāi)始通過(guò)函數(shù)調(diào)用機(jī)制調(diào)用外部工具。它們一般是讓模型生成一次工具調(diào)用，然后把計(jì)算外包給外部工具，再把結(jié)果回填進(jìn)上下文。ToolFormer，以及 GPT、Claude、Gemini 中的 function calling 機(jī)制，都屬于此類(lèi)。

圖 4 是這種上下文管理方式的動(dòng)畫(huà)示意。某時(shí)刻 Transformer 生成了一個(gè)函數(shù)調(diào)用，上下文管理器根據(jù)生成的參數(shù)調(diào)用工具，然后將結(jié)果放入上下文窗口。

圖 4 | 工具調(diào)用：把計(jì)算外包給外部工具

論文點(diǎn)明，如果 C 被允許調(diào)用一個(gè)本身就圖靈完備的工具（比如執(zhí)行任意 Python 程序），那么整個(gè)系統(tǒng)都會(huì)平凡地達(dá)到圖靈完備。

⑤ 多 token 解碼 + 追加式上下文管理——圖靈完備

第五種方式，是在追加式上下文管理的基礎(chǔ)上，再放寬解碼接口。Schuurmans 等人（2024）放寬了通常的一步一 token 設(shè)定，允許系統(tǒng)每一步最多生成 K 個(gè) token，然后把這些 token 追加到序列末尾。

為了便于形式化，“每步最多生成 K 個(gè) token”也可以改寫(xiě)成“每步固定生成 K 個(gè)位置”。其中，有些位置可以是特殊的空 token（用 ε 表示）。上下文管理器遇到 ε 時(shí)會(huì)直接跳過(guò)，不把它追加到序列末尾；這樣一來(lái)，實(shí)際追加的 token 數(shù)量仍然可以在 0 到 K 之間變化。

圖 5 展示了這個(gè)過(guò)程。三輪解碼分別得到 (ε, ε)、(k, l)、(m, ε)。其中 ε 被丟棄，k、l、m 被追加到序列末尾。

圖 5 | 多 token 解碼：三輪分別解碼 (ε, ε)、(k, l)、(m, ε)

論文引用 Schuurmans 等人（2024）的證明指出，當(dāng) K = 1 時(shí)，所得系統(tǒng)的計(jì)算能力與線性空間圖靈機(jī)等價(jià)；而當(dāng) K ≥ 2 時(shí)，所得系統(tǒng)是圖靈完備的。這說(shuō)明，真正改變系統(tǒng)能力的未必是 Transformer 權(quán)重本身，也可能是“每步能生成幾個(gè) token”這樣的解碼接口。

把這五種方式放回那張譜系圖就能看得更清楚。同一個(gè)固定的 Transformer T，配上摘要式上下文管理器，至多只有常數(shù)空間圖靈機(jī)的能力；配上追加式上下文管理器，等價(jià)于線性空間圖靈機(jī)；配上外部存儲(chǔ)、工具調(diào)用或多 token 解碼與追加式上下文管理，就成了圖靈完備的系統(tǒng)。T 沒(méi)有變，變的是 C，或 C 與 D 的組合，計(jì)算能力卻跨越了三個(gè)復(fù)雜度層級(jí)。這也正是論文標(biāo)題所說(shuō)的，真實(shí) Transformer 的圖靈完備性高度依賴(lài)上下文管理。

那些刷屏證明，到底默認(rèn)了什么？

用這個(gè)區(qū)分回看已有工作，論文梳理的多數(shù)“Transformer 圖靈完備”、“Transformer 模擬圖靈機(jī)”或“Transformer 通用性”的證明，都依賴(lài)兩類(lèi)縮放族假設(shè)。

縮放上下文窗口：假設(shè)任意長(zhǎng)的輸入以及中間結(jié)果都能放進(jìn)上下文窗口，并參與自注意力計(jì)算；

縮放數(shù)值精度：假設(shè)內(nèi)部表示的精度可以隨輸入長(zhǎng)度增長(zhǎng)，甚至直接使用無(wú)界精度的實(shí)數(shù) / 有理數(shù)。

只要采用了其中任意一條，研究對(duì)象就已經(jīng)從“一個(gè)固定模型”，悄悄滑向了“一族不斷變大的模型”。表 1 總結(jié)了這些落在縮放族設(shè)定下的研究所做的上下文窗口長(zhǎng)度與數(shù)值精度的假設(shè)。

表 1 | 落在縮放族設(shè)定下“圖靈完備”證明所依賴(lài)的前提假設(shè)

那篇刷屏的“推理 token 夠多就能解決任意問(wèn)題”的 CoT 工作（Li et al., 2024），正落在這張表里——它同時(shí)用到了縮放窗口和縮放精度。這并不意味著它錯(cuò)了。問(wèn)題在于，它證明的是縮放族意義下的能力，不能直接推出你手上那個(gè)固定 LLM 本身就是圖靈完備的。

另外，論文還梳理了固定模型設(shè)定下的研究，并將這篇論文的新結(jié)果也放入其中做對(duì)比，形成了下面的表 2。

表 2 | 固定系統(tǒng)設(shè)定下不同上下文管理方式對(duì)應(yīng)的計(jì)算能力

從單一模型到模型系統(tǒng)

論文最后強(qiáng)調(diào)，理論分析需要從 Transformer 權(quán)重本身，轉(zhuǎn)向由權(quán)重、解碼規(guī)則和上下文管理共同組成的系統(tǒng) (T, D, C)。上下文管理這類(lèi) Harness，乃至把能力沉淀、復(fù)用為可調(diào)用單元的 skill，都是模型系統(tǒng)的一種實(shí)現(xiàn)方式。沿著這個(gè)視角，論文最后給出三點(diǎn)建議：

第一，談?wù)?Transformer 圖靈完備時(shí)，請(qǐng)明確說(shuō)明計(jì)算設(shè)定與假設(shè)。縮放族的結(jié)果對(duì)理解資源需求（上下文長(zhǎng)度、精度、深度）很有價(jià)值，但不應(yīng)被解讀為某個(gè)固定真實(shí)模型的圖靈完備性。

第二，理論研究應(yīng)把“固定 Transformer + 不同上下文管理”組成的整體系統(tǒng)當(dāng)作主要研究對(duì)象。既然真實(shí)部署的 LLM 就是固定窗口、固定精度的 Transformer，加上某種上下文管理方式，那么系統(tǒng)層面的能力刻畫(huà)，理應(yīng)得到更多關(guān)注。

第三，社區(qū)不應(yīng)止步于基于理想化假設(shè)的定性圖靈完備性分析，而應(yīng)進(jìn)一步以明確的資源預(yù)算和可學(xué)習(xí)性標(biāo)準(zhǔn)來(lái)補(bǔ)充對(duì)模型能力的刻畫(huà)。圖靈完備性只說(shuō)明在某種編碼下某個(gè)函數(shù)是否可計(jì)算，并不等于已經(jīng)回答了模型是否能夠習(xí)得、泛化并穩(wěn)健地使用相應(yīng)解法。

過(guò)去很多理論結(jié)果把注意力放在模型本體上，而這篇論文把上下文管理、工具調(diào)用、外部存儲(chǔ)等系統(tǒng)組件放到計(jì)算模型里一起分析。這樣看，同一個(gè) Transformer 配上不同的 C，能力邊界會(huì)完全不同，弱則連回文都判斷不了，強(qiáng)則可以走到圖靈完備。

資助信息：本成果受到國(guó)家自然科學(xué)基金（L2524018, U2241212, 92470128, 62472430）資助。