新智元報導
編輯：Aeneas KingHZ
【新智元導讀】就在剛剛，Claude 獨立攻克了圖論猜想，寫《電腦程式設計藝術》的電腦泰斗高德納徹底震驚了！這一次，AI 在自動推理和解決創造性問題上，又達到了全新的里程碑。
震驚！震驚！
就在剛剛，Claude 僅用 31 步，就獨立攻克了未解的圖論猜想難題。
寫《電腦程式設計藝術》的演算法祖師爺高德納驚呼：「我不得不重新評估生成式 AI 在數學研究中的作用」。
在史丹佛大學的官網上，他本人發布了一篇原始論文。開頭兩個字，就是「Shock！Shock！」
論文位址：https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
高德納是誰？
他是寫出了《電腦程式設計藝術》（TAOCP）、發明 TeX 的圖靈獎得主，演算法界祖師爺。
《電腦程式設計藝術》是高德納一生中最重要的事業，他寫這本書的目的是「組織和總結所知道的電腦方法的相關知識，並打下堅實的數學、歷史基礎。
一個寫了 50 年演算法書的人，都開始認真看待 AI 的數學能力，那就說明：AI，正在進入人類最核心的智力領域。
被 Opus 4.6 攻克了
在論文開頭，高德納這樣講述道：
我昨天得知，一個我花了數週時間研究的未解問題，剛剛被 Claude Opus 4.6——Anthropic 公司在三週前發布的混合推理模型——解決了！
他直言：
看來我遲早得重新審視自己對「GenAI」的看法了。得知自己的猜想不僅有一個漂亮的解法，同時還能見證自動推理與創造性問題求解方面的這一戲劇性進步，真是令人欣喜不已。
故事是這樣的，《電腦程式設計藝術》這個系列，從上世紀 60 年代就開始寫，現在已經出了 5 本。
在 88 歲的高齡，這位演算法祖師爺還在繼續寫這套書。
他在書裡準備了一道關於有向哈密頓循環的題，和朋友們證明了這道題的特殊解，想把它推廣到一般情況時，卻解決不了了。
結果，這道題被 Claude Opus 4.6 解決了。
更嚴謹的說法是，AI 找到了一個漂亮的構造方法，而高德納隨後給出了嚴格的數學證明。
這篇論文也因此成為一個標誌性事件——生成式 AI，第一次被認真記錄在數學研究的故事裡。
這道題，是一道看起來簡單，但實際上非常複雜的圖論問題。
先想像一個三維網格空間，比如一個m×m×m 的立方體。
其中每個點都可以用 (i, j, k) 三個座標表示，每個座標都在 0 到 m-1 之間。所以，整個空間裡一共有m³個點。
接下來我們規定，從每個點都可以沿三個方向移動：i 增加 1，j 增加 1，k 增加 1。如果超過 m−1，就從 0 重新開始。這就形成了一個環形空間。
按照高德納在論文中的正式定義，就是從每個頂點有三條有向邊，分別指向三個方向的「下一個」頂點。
因此，整個圖有 m³個頂點，3m³條有向邊。
而哈密頓環，就是一條路徑經過所有頂點，每個頂點恰好一次，最後回到起點。這是一個經典的圖論問題。
而高德納提出的問題更難：不是找一條路線，而是要找到三條路線，並且滿足每條都是哈密頓環，每條長度都是 m³，三條環剛好覆蓋所有邊。
也就是說：每條邊只能屬於其中一條環。
原本，高德納就是準備把這個問題寫進《電腦程式設計藝術》的新章節。
為什麼這個問題如此困難？原因就在於，每個點都有三條出邊。如果要組成哈密頓環，就必須選擇其中一條。所以在每個點，都需要做一個選擇。
因此，問題規模達到了 3^(m³) 個！這幾乎無法通過暴力搜索完成，因此，必須找到某種規律性的構造方法。
此前，高德納已經解決了 m=3 的情況，他的朋友Filip Stappers又通過實驗找到了 4≤m≤16 的解。
這就說明：答案很可能存在！
那麼，能否找到一個通用公式？
Filip 把問題交給了 Claude Opus 4.6，而且制定了一個嚴格的規則——每次運行程式後，都必須記錄探索的進展。
有趣的是，Claude 並不是突然靈光一現，而是經歷了 31 次探索，過程非常像一個研究生在做研究。
第一步，它嘗試了簡單函數，試圖用一個函數 g(i,j,k) 決定每個點的方向。但是很快它發現，簡單線性函數不行。
第二步，它開啟了暴力搜索，嘗試用深度有限搜索（DFS），但搜索空間太大，效率太低。
第三步，是二維分析。Claude 發現，如果只看二維情況，可以找到一種「蛇形路徑」。於是，它試圖把二維思路推廣到三維。
隨後，它構造了一種類似 Gray code 的三維蛇形路徑，但刪除第一條路徑後，剩下的結構很難分解。
接下來的十幾次探索，Claude 基本都是在不斷試錯。
在第 15 次探索時，Claude 提出了一個關鍵想法：fiber decomposition（纖維分解）。
它注意到，如果定義 s = (i + j + k) mod m，那麼所有邊都會把頂點從 s 移動到 s+1，這就意味著：整個圖可以按 s 分成層結構。
這樣，每一層都像一個二維網格，這就把問題大大簡化了。
Claude 隨後嘗試了隨機搜索、模擬退火和回溯搜索，這些方法可以找到一些解，但仍然沒有發現通用規律。
於是 Claude 得出結論——需要純數學結構。
在第 31 次探索時，Claude 終於提出了一套簡單規則，核心仍然是 s = (i + j + k) mod m。
然後根據 s、i、j 的情況決定是否增加 i、增加 j、增加 k。論文中稱之為「bump」規則。
規則大致如下：如果 s=0，根據 j 的值決定移動方向。如果 0
這樣就生成一條完整的路徑。
Claude 用程式驗證了：對於 m=3,5,7,9,11，路徑都成立。而且三條路徑都是哈密頓環，所有邊都被使用。
當然，Claude 只是提出了構造方法，數學上還需要嚴格證明。
隨後，高德納證明，這條路徑確實訪問了所有 m²個具有相同 i 值的頂點，然後依次覆蓋所有 i，最終形成長度為 m³的完整環。
類似證明也適用於另外兩條環，於是整個問題被解決了。
而且，高德納還通過進一步研究發現，Claude 找到的並不是唯一解。
實際上存在760 種類似的分解方法，這些解都滿足同樣的結構。Claude 只是找到了其中一個。
另外，Claude 只解決了 m 為奇數的情況。
如果 m 是偶數，問題仍然沒有通用解，甚至 m=2 已經被證明不可能，所以這個研究仍然沒有完全結束。
如果說這件事真正有意義的地方，不只是解題，而是AI解題的方式。
在這個過程中，Claude 並不是猜答案，而是在重新表述問題，寫程式，發現規律。這一過程，和人類研究非常接近！
幾十年來，人們普遍認為，數學證明是 AI 最難進入的領域。
但這篇論文說明：AI 已經開始參與真正的數學探索，
未來也許會出現新的研究模式——人類提出問題，AI 探索結構，人類完成證明。
而這篇「Claude's Cycles」，也許會被視為一個起點。
高德納寫《電腦程式設計藝術》，已經超過半個世紀了，這套書記錄了人類演算法思想的發展。
而現在，AI 被寫進了演算法大師鼻祖的論文中。這，可能只是一個開始。
高德納，原名叫 Donald Ervin Knuth，1938 年 1 月 10 日出生於美國密爾瓦基。
Donald Knuth，美國電腦科學家，史丹佛大學名譽教授
高德納是公認為演算法分析「祖師爺」，現代電腦科學的先驅，在數個理論電腦科學的分支做出基石一般的貢獻。
憑藉對演算法分析和程式設計語言設計的重大貢獻，他斬獲 1974 年圖靈獎（電腦科學領域的「諾貝爾獎」）。
當時，他只有 36 歲，這個歷史記錄還沒有其他得主打破。
頒獎詞中特意強調：他所著的系列叢書《電腦程式設計藝術》（The Art of Computer Programming，TAOCP）為電腦程式設計藝術做出的傑出貢獻。
1999 年底，這本書被《美國科學家》（American Scientist）期刊列為 20 世紀最佳 12 部學術專著之一，愛因斯坦的「相對論」、羅素和懷海德的《數學原理》等科學史上的重要著作並列必讀經典。
1968 年出版第一卷第一版，至 1976 年，已賣出超過一百萬冊。
比爾蓋茲曾評價這套書：
如果你真自認為自己是一個好程式員，去讀《電腦程式設計藝術》吧。如果你讀完了這套書，你一定要把履歷發給我。
1977 年，他為了讓這本書的印刷更精美，決定開發排版系統。八年後，他帶著 TeX 回歸。
TeX 是全球學術排版的不二之選，尤其是處理複雜數學符號
截至 2025 年，已出版的卷冊包括第 1、2、3、4A 和 4B 卷，未來預計還將發布更多卷冊。
第 1 至 5 卷旨在闡述適用於順序機器的電腦程式設計核心內容；第 6 卷和第 7 卷的主題則更為專門，但仍具重要意義。
順便一提，他的中文名高德納，是在 1977 年訪問中國前，他的朋友清華姚班之父姚期智的夫人姚儲楓給他起了這個名字。
高德納為人風趣。比如，他會獎勵每一個找出他的著作中任何錯誤的人，就能得到 2.56 美元，因為「256 美分剛好是十六進位的一美元」（256 pennies is one hexadecimal dollar）。
水木有帖子匯總整理關於 Knuth 的 18 條八卦：
可以上下滾動的圖片，轉自：https://mp.weixin.qq.com/s/jmEhfkw_3w2sDuACQCwTOQ
對高德納而言，編程不僅是技術、科學，還是藝術。
日常生活大概就像編程。如果你熱愛一件事，就能把美感融入其中。
排版系統 TeX 讓他萌發了「文學編程」的概念——
文學編程範式不同於傳統的由電腦強加的編寫程式的方式和順序，而代之以讓程式員用他們自己思維內在的邏輯和流程所要求的順序開發程式。
對他來說，「文學編程確實是由 TeX 項目派生出來的最重要的東西」。
後來，高德納回憶道：
它不僅讓我前所未有地更快地寫和維護可靠性更高的程式，而且成為我自 20 世紀 80 年代以來的最大的快樂之源——它有時實際上是不可或缺的。
我做的其它一些大程式，比如 MMIX 元模擬器，用我見過的任何一種其它的方法論是無法寫出來的。其複雜性讓我有限的智能望而卻步。
沒有文學編程，我的整個事業規劃就會轟然倒塌。……文學編程是你更上一層楼的必要工具。
完全可以說，Vibe Coding 和文學編程一脈相承，不知道老爺子自己有沒有體驗過真正的 Vibe Coding。
自小，高德納就「聰敏絕頂」——
他 8 歲時，當時某糖果商舉辦了一項小學生益智趣味比賽，要求用「Ziegler's Giant Bar」（分別為糖果廠名和出產的棒棒糖名）裡的字母寫出盡可能多的單詞。
小高德納假裝胃疼宅家兩週，依靠一部大字典列出了 4500 個單詞，而裁判才掌握的 2000 個單詞！
這不僅使所在班級奪冠（獎品為一台電視机和每人一塊 Giant Bar），他個人人也贏得一付雪撬。
他在凱斯理工學院的數學研究表現極為出色，以至於在他完成本科學業時，學院授予了他數學碩士學位。
1963 年，他獲得加州理工學院數學博士學位。
1963-1968 年，他先後任加州理工學院助理教授、副教授。
1968-1992 年，任史丹佛大學一系列正教授及冠名教授職位。
1993 年至今，任史丹佛大學「電腦程式設計藝術」榮休教授（Emeritus）。
據統計，高德納一生榮獲 100 多項大小榮譽，包括：
https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf
https://valeman.substack.com/p/donald-knuths-30-year-problem-solved
https://mp.weixin.qq.com/s/jmEhfkw_3w2sDuACQCwTOQ
https://mp.weixin.qq.com/s/PkrJnuvtrL0OCJXzRPCxxA
https://mp.weixin.qq.com/s/XIcafYS9PbNgE2cMYHfQ5w