88歲圖靈獎(jiǎng)得主，用Claude一小時(shí)破解30年數(shù)學(xué)懸案

henry 發(fā)自 凹非寺
量子位 | 公眾號 QbitAI

88歲的圖靈獎(jiǎng)得主、計(jì)算機(jī)科學(xué)奠基人Donald Knuth（高德納）最近發(fā)文，驚呼Shock! Shock!。

在他的短文《Claude’s Cycles》中，他記錄了一件難以置信的事：

一個(gè)他研究數(shù)周、甚至追溯到30年前的三維圖論開放問題，被Claude Opus 4.6破解了。

更關(guān)鍵的是，Claude不是靠暴力搜索，而是用“纖維分解”、“蛇形構(gòu)造”等結(jié)構(gòu)性思路——

僅用1小時(shí)、31次探索，就推導(dǎo)出了適用于所有奇數(shù)m的通用構(gòu)造算法。

這直接讓向來對生成式AI持保留態(tài)度的高德納在文章最后寫道：

“為Claude脫帽致敬！”

這是怎么一回事？

1小時(shí)解決30年懸案

高德納在論文中提到，他最近幾周一直在鉆研這個(gè)問題，但根源可追溯到編寫《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》（The Art of Computer Programming）圖論章節(jié)時(shí)的長期思考。

具體來說，高德納拋出的問題極具挑戰(zhàn)性：

• 在一個(gè)擁有m^3個(gè)頂點(diǎn)的三維網(wǎng)格圖中，能否將所有的弧（arcs）完美拆解成三個(gè)互不重疊、且經(jīng)過每個(gè)頂點(diǎn)恰好一次的長循環(huán)（即哈密頓循環(huán)）？

對于m=2的情況，早在多年前已被證明是不可能的，而高德納此前僅解出了m=3的特例。

當(dāng)高德納的朋友Filip Stappers將此問題拋給Claude時(shí)，常規(guī)的暴力搜索（DFS）很快撞到了南墻——

在m=3時(shí)搜索空間就已高達(dá)6^27，效率極低。然而，Claude展現(xiàn)出了驚人的邏輯演進(jìn)能力。

• 在第15次探索中，Claude引入了商映射，將頂點(diǎn)劃分為不同的“纖維層”。它意識到，所有的弧實(shí)際上都是從層F_s指向F_s+1，這一步神來之筆，將復(fù)雜的三維路徑尋找問題，降維簡化成了層與層之間的規(guī)律跳轉(zhuǎn)。
• 在第21次探索中，Claude靈光一現(xiàn)。它利用凱萊圖（Cayley Digraph）的性質(zhì)，發(fā)現(xiàn)了一種它稱為“蛇形”的構(gòu)造方法：通過特定的步進(jìn)邏輯），可以在局部生成極具規(guī)律的路徑。
• 雖然在第27次探索中，Claude發(fā)現(xiàn)簡單的坐標(biāo)旋轉(zhuǎn)會導(dǎo)致在超平面上出現(xiàn)沖突，但它并未放棄。
• 它在第30次探索中敏銳地察覺到：在某些纖維層，移動的選擇可以僅取決于單個(gè)坐標(biāo)。正是這個(gè)發(fā)現(xiàn)，踢出了通往終點(diǎn)臨門一腳。

基于這一發(fā)現(xiàn)，在第31次探索中，Claude編寫了一個(gè)Python程序，給出了一個(gè)通用的構(gòu)造算法。

高德納隨后親自將該程序簡化為C語言版本，并驗(yàn)證m=3, 5, 7, 9, 11等情況，結(jié)果全部正確。

Stappers甚至將其測試到了m=101，依然完美契合。

更令高德納震驚的是，Claude并沒有像以往的AI那樣只給出一個(gè)黑盒結(jié)果，而是清晰地展示了它如何從錯(cuò)誤中學(xué)習(xí)、如何重新表述問題、如何利用凱萊圖（Cayley Digraph）的群論性質(zhì)進(jìn)行推導(dǎo)。

正如高德納所說，Claude在這一個(gè)小時(shí)里完成了一次“自動演繹與創(chuàng)造性問題解決”的完美示。這不再是簡單的概率預(yù)測，而是真正的、邏輯嚴(yán)密的數(shù)學(xué)發(fā)現(xiàn)。

不過，在解決奇數(shù)情形后，當(dāng)Claude繼續(xù)挑戰(zhàn)偶數(shù)情況時(shí)，它似乎陷入了僵局，連用于探索的程序都出現(xiàn)了報(bào)錯(cuò)。

即便如此，但這恰恰證明了科學(xué)探索的真實(shí)性。AI捅破了最厚的那層窗戶紙，而剩下的路，正是人類與AI協(xié)作的新起點(diǎn)。

“高德納”是誰

如果你不了解高德納，就難懂他的兩聲“Shock”為何震動計(jì)算機(jī)科學(xué)界。

在計(jì)算機(jī)科學(xué)界，高德納幾乎是一個(gè)“活著的傳奇”。

1974年，年僅36歲的他便獲得了圖靈獎(jiǎng)。憑借對算法分析體系的奠基性貢獻(xiàn)，他也成為歷史上最年輕的圖靈獎(jiǎng)得主之一。

其中最繞不開的，就是那套神作《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》（The Art of Computer Progamming，TAOCP）

該如何去形容這本書呢？有網(wǎng)友表示得十分貼切：

• 書還沒寫完，人們就已經(jīng)迫不及待把圖靈獎(jiǎng)?lì)C給了他。

這套書后來被《美國科學(xué)家》雜志將其列為20世紀(jì)最重要的12部物理科學(xué)著作之一，與愛因斯坦《相對論》并列。

比爾·蓋茨曾評價(jià)：

• 如果你認(rèn)為自己是一位非常優(yōu)秀的程序員……那就讀讀《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》……如果你能讀完這本書，一定要給我發(fā)一份簡歷。

高德納從1962年開始寫這套書。原計(jì)劃三卷，后來不斷擴(kuò)展，如今已經(jīng)規(guī)劃為七卷。

直到2026年，他仍在持續(xù)完善第四卷及其后續(xù)部分。

正如網(wǎng)友所說，在《Claude’s Cycles》里有兩個(gè)奇跡：一是Claude證明數(shù)學(xué)題；二是88歲高齡的高德納仍在寫書。

有趣的是，當(dāng)高德納發(fā)現(xiàn)當(dāng)時(shí)的計(jì)算機(jī)排版無法完美呈現(xiàn)數(shù)學(xué)公式時(shí)，他還曾暫停了TAOCP的編寫，順手開發(fā)了TeX排版系統(tǒng)

今天，全世界絕大多數(shù)數(shù)學(xué)、物理和計(jì)算機(jī)論文，幾乎都在使用TeX（或基于它發(fā)展的 LaTeX）進(jìn)行排版。

高德納甚至給TeX設(shè)計(jì)了一種極具個(gè)人風(fēng)格的版本號：版本號會不斷趨近π（3.14、3.141、3.1415……），象征無限接近完美。

他還宣布自己的程序理論上沒有Bug，并懸賞獎(jiǎng)勵(lì)發(fā)現(xiàn)Bug的人。

事實(shí)上，這并不是他唯一一次為Bug付錢。

最著名的是程序員圈里的高德納支票。任何發(fā)現(xiàn)TAOCP書中錯(cuò)誤的人，都可以收到一張由高德納親筆簽名的獎(jiǎng)金支票。

獎(jiǎng)金通常是2.56美元——因?yàn)?56美分等于2?，在十六進(jìn)制里剛好是1美元。

對于程序員來說，擁有一張高德納簽名的支票是職業(yè)生涯的最高榮耀，絕大多數(shù)獲獎(jiǎng)?wù)叨紩⑵溲b裱起來而非兌現(xiàn)。

為了專注研究，高德納在1990年之后就徹底停用了電子郵件。

他認(rèn)為郵件會耗費(fèi)他寶貴的思考時(shí)間。如果你想聯(lián)系他，只能寄實(shí)體信件到斯坦福大學(xué)。

這樣一位仿佛停留在“信息時(shí)代前夜”的老派邏輯大師——對每一個(gè)字節(jié)、每一行公式都追求極致精確。

而如今，正是這樣的人，卻被一個(gè)生成式AI深深震撼。

這本身，就是一件極具沖擊力的事。

正如高德納自己所說：

這絕對是一個(gè)令人印象深刻的成功故事。如果香農(nóng)在天之靈知道自己的名字如今與這樣的進(jìn)步聯(lián)系在一起，大概也會感到自豪。

向Claude脫帽致敬（Hats off to Claude）！

而這，或許是計(jì)算機(jī)科學(xué)史上最完美的一個(gè)一語雙關(guān)

高德納口中的Claude，既是那個(gè)在1小時(shí)內(nèi)攻克難題、邏輯縝密的AI推理模型；

也是那位在80年前親手定義了“比特”、開創(chuàng)了信息論時(shí)代的香農(nóng)（Claude Shannon）。

[1]https://x.com/i/trending/2028948713042002348
[2]https://www-cs-faculty.stanford.edu/~knuth/