隨著大語言模型能力不斷演進，很多研究宣稱證明 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）資助。