高德納：「震驚！震驚！」Claude破解《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》難題

編輯｜Panda

「震驚！震驚！」

是什么讓著名計(jì)算機(jī)科學(xué)家和數(shù)學(xué)家、《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》作者、圖靈獎(jiǎng)得主高德納（Donald Knuth）發(fā)出了如此驚呼？

圖片由 AI 生成

你沒(méi)有猜錯(cuò)，正是AI

在他近期在斯坦福大學(xué)官網(wǎng)上公布的一篇論文《Claude’s Cycles》中，開篇的「Shock! Shock!」非常直白地表達(dá)了他對(duì)于 AI 強(qiáng)大能力的震驚。

論文地址：https://cs.stanford.edu/~knuth/papers/claude-cycles.pdf

緊接著他便寫到：「我昨天得知，我已經(jīng)研究了幾周的一個(gè)開放性問(wèn)題剛剛被 Claude Opus 4.6——Anthropic 公司三周前發(fā)布的混合推理模型 —— 解決了！看來(lái)我得在某個(gè)時(shí)候重新審視我對(duì)『生成式 AI』的看法了。不僅我的猜想有了一個(gè)不錯(cuò)的解決方案，而且這標(biāo)志著自動(dòng)推理和創(chuàng)造性問(wèn)題解決領(lǐng)域的巨大進(jìn)步，這真是一件令人高興的事。我會(huì)在這篇短文中簡(jiǎn)要講述這個(gè)過(guò)程。」

此事引發(fā)了廣泛關(guān)注，網(wǎng)友們紛紛點(diǎn)評(píng)，感嘆新時(shí)代的到來(lái)。

這是 Hacker News 用戶 Ian Danforth 給出的太長(zhǎng)不讀版本：高德納提出一個(gè)問(wèn)題，他的朋友借助 Claude 進(jìn)行了 30 多次探索，在人類的仔細(xì)指導(dǎo)下，Claude 最終編寫了一個(gè) Python 程序，能夠?yàn)樗衅鏀?shù)找到解。高德納隨后為該方法撰寫了證明，并對(duì) Claude 的貢獻(xiàn)感到非常滿意。偶數(shù)情況仍是未解之謎（Claude 在這方面未能取得太大進(jìn)展）。

困擾算法泰斗的圖論難題

高德納在為《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》未來(lái)卷撰寫關(guān)于有向哈密頓環(huán)的內(nèi)容時(shí)，遇到了一個(gè)棘手的開放性問(wèn)題。

具體而言，需要考慮一個(gè)具有 m3 個(gè)頂點(diǎn)的有向圖，頂點(diǎn)坐標(biāo)記為 ijk，其中 0≦ i, j, k

2 的情況。

高德納此前已經(jīng)解決了 m=3 的基礎(chǔ)情況，并將其作為書中的一道練習(xí)題。他的朋友 Filip Stappers 隨后通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)了 4≦ m≦16 的解，這使得所需分解法存在的可能性極高。為了尋找通解，Stappers 將這個(gè)問(wèn)題原封不動(dòng)地交給了 Claude 處理。

31 步探索：AI 的解題邏輯

在交互過(guò)程中，Stappers 對(duì) Claude 設(shè)定了嚴(yán)格的規(guī)則指令：

• 在運(yùn)行完任何探測(cè)代碼后，必須立即更新 plan.md 文件。
• 在記錄完成之前，絕對(duì)不允許開始下一步的探索。

Claude 采取了多種數(shù)學(xué)工具進(jìn)行嘗試。它最初嘗試了簡(jiǎn)單的線性與二次函數(shù)，但均未奏效。接著，它嘗試使用暴力深度優(yōu)先搜索，最終因?yàn)樗阉骺臻g過(guò)大而放棄。隨后，它引入了「2D 蛇形分析」，并準(zhǔn)確識(shí)別出該有向圖是一個(gè)帶有兩個(gè)生成元的凱萊圖（Cayley digraph）。

問(wèn)題的突破發(fā)生在后半程的探索中：

• 在第 15 次探索時(shí)，Claude 引入了「纖維分解」框架，將問(wèn)題轉(zhuǎn)化為在坐標(biāo)上選擇算子的排列組合。
• 在第 25 次探索后，它自主得出結(jié)論，認(rèn)為模擬退火算法雖然能找到解，卻無(wú)法給出通用構(gòu)造，此時(shí)需要純粹的數(shù)學(xué)推導(dǎo)。
• 最終在第 31 次探索時(shí)，Claude 注意到每個(gè)纖維的選擇僅依賴于單個(gè)坐標(biāo)，并據(jù)此給出了一個(gè)具體的 Python 構(gòu)造程序，成功得出了 m=3, 5, 7, 9, 11 的完美分解方案。

簡(jiǎn)化版的 Python 程序，用 C 語(yǔ)言形式寫的

嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明與偶數(shù)域的挑戰(zhàn)

得出構(gòu)造代碼僅僅是第一步。Stappers 驗(yàn)證了 3 到 101 之間所有奇數(shù) m 的情況，均獲得了完美的分解方案。隨后，高德納接手進(jìn)行了嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)證明。他詳細(xì)推導(dǎo)了生成的第一個(gè)環(huán)包含所有具備相同特征的 m2 個(gè)頂點(diǎn)，從而證實(shí)其長(zhǎng)度確為 m3，是一個(gè)真正的哈密頓環(huán)。

高德納進(jìn)一步研究發(fā)現(xiàn)，在所有類似 Claude 生成邏輯的分解法中，恰好有 760 種對(duì)所有奇數(shù) m>1 均有效的解。Claude 憑借自身推導(dǎo)準(zhǔn)確找到了其中的一種。

目前，偶數(shù) m 的情況依然懸而未決。

• Claude 在探索中曾找到 m=4, 6, 8 的解，但未能發(fā)現(xiàn)其中的通用規(guī)律。
• 當(dāng)被要求繼續(xù)攻克偶數(shù)情況時(shí)，Claude 陷入了困境，后續(xù)甚至無(wú)法正確編寫探索程序。
• 另一位研究者 Ho Boon Suan 借助 gpt-5.3-codex 生成了處理大于 8 的偶數(shù) m 的代碼，并在高達(dá) m=2000 的規(guī)模下測(cè)試成功。
• 但由于其模式過(guò)于復(fù)雜，目前人工證明其正確性的難度極大。

在 Hacker News 和 Reddit 等技術(shù)社區(qū)中，開發(fā)者們普遍認(rèn)為這次事件的核心意義在于，AI 在數(shù)學(xué)輔助證明中展現(xiàn)出了自主更換探索工具、排查無(wú)效路徑的能力。

正如高德納在文末所感嘆的那樣，克勞德?香農(nóng)（Claude Shannon）在天之靈若能知曉他的名字與此類進(jìn)步聯(lián)系在一起，定會(huì)感到驕傲。

Hats off to Claude!

AI 進(jìn)軍數(shù)學(xué)殿堂：從競(jìng)賽奪金到前沿探索

高德納的驚嘆并非孤例。事實(shí)上，在過(guò)去的一年多時(shí)間里， AI 在解決復(fù)雜數(shù)學(xué)和邏輯問(wèn)題上已經(jīng)取得了多個(gè)具有實(shí)質(zhì)性意義的突破。

• 國(guó)際奧數(shù)突破：2025 年 7 月，Google DeepMind 發(fā)布的 Gemini（Deep Think 模式）在 IMO 試題評(píng)測(cè)中達(dá)到金牌標(biāo)準(zhǔn)成績(jī)，取得 35 分，并能在接近正式考試條件下輸出完整自然語(yǔ)言證明。與此同時(shí)，OpenAI 也披露其內(nèi)部模型達(dá)到了類似水平，但官方認(rèn)證與評(píng)測(cè)細(xì)節(jié)相對(duì)有限。
• 編程競(jìng)賽能力躍升：2025 年 9 月，OpenAI 和 Gemini 都聲稱達(dá)到了 ICPC 金牌水平，能夠在嚴(yán)格時(shí)間限制內(nèi)解決高難度算法問(wèn)題。不過(guò)，這些成績(jī)主要來(lái)自平行測(cè)試或基準(zhǔn)評(píng)估，并非以正式參賽身份在 International Collegiate Programming Contest 中獲得官方金牌。
• 從解題到科研協(xié)作：如今，AI 在科研中的角色顯著增強(qiáng)。模型開始借助外部工具參與數(shù)學(xué)研究與問(wèn)題驗(yàn)證，在復(fù)雜猜想與定理探索中發(fā)揮輔助作用。例如， GPT-5.2 借助外部工具，協(xié)助數(shù)學(xué)家解決了數(shù)個(gè)懸而未決的 Erd?s 猜想，并得到了著名數(shù)學(xué)家陶哲軒的驗(yàn)證。部分系統(tǒng)已展示出生成研究草稿與進(jìn)行結(jié)構(gòu)化推理的能力。

驅(qū)動(dòng)這些突破的核心機(jī)制也發(fā)生了改變。 AI 開始減少對(duì)單次快速生成的依賴。現(xiàn)在的模型普遍采用「測(cè)試時(shí)計(jì)算擴(kuò)展」或「慢思考」策略。通過(guò)在推理階段投入更多算力，模型能夠并行探索多條解題路徑并進(jìn)行嚴(yán)格的自我驗(yàn)證。

展望未來(lái)， AI 與數(shù)學(xué)的結(jié)合將突破封閉環(huán)境下的標(biāo)準(zhǔn)化考題。隨著自然語(yǔ)言理解力與形式化邏輯的深度融合，AI 將成為數(shù)學(xué)家與工程師身邊得力的合作者，幫助人類共同攻克那些停滯多年的科學(xué)難題。