Full text · 原文
2,695 字
henry 发自 凹非寺<br>
量子位 | 公众号 QbitAI<br>
88岁的图灵奖得主、计算机科学奠基人Donald Knuth（高德纳）最近发文，惊呼Shock! Shock!。<br>
在他的短文《Claude’s Cycles》中，他记录了一件难以置信的事：<br>
一个他研究数周、甚至追溯到30年前的三维图论开放问题，被Claude Opus 4.6破解了。<br>
更关键的是，Claude不是靠暴力搜索，而是用“纤维分解”、“蛇形构造”等结构性思路——<br>
仅用1小时、31次探索，就推导出了适用于所有奇数m的通用构造算法。<br>
这直接让向来对生成式AI持保留态度的高德纳在文章最后写道：<br>
“为Claude脱帽致敬！”<br>
这是怎么一回事？<br>
1小时解决30年悬案<br>
高德纳在论文中提到，他最近几周一直在钻研这个问题，但根源可追溯到编写《计算机程序设计艺术》（The Art of Computer Programming）图论章节时的长期思考。<br>
具体来说，高德纳抛出的问题极具挑战性：<br>
在一个拥有m^3个顶点的三维网格图中，能否将所有的弧（arcs）完美拆解成三个互不重叠、且经过每个顶点恰好一次的长循环（即哈密顿循环）？<br>
对于m=2的情况，早在多年前已被证明是不可能的，而高德纳此前仅解出了m=3的特例。<br>
当高德纳的朋友Filip Stappers将此问题抛给Claude时，常规的暴力搜索（DFS）很快撞到了南墙——<br>
在m=3时搜索空间就已高达6^27，效率极低。然而，Claude展现出了惊人的逻辑演进能力。<br>
在第15次探索中，Claude引入了商映射，将顶点划分为不同的“纤维层”。它意识到，所有的弧实际上都是从层F_s指向F_s+1，这一步神来之笔，将复杂的三维路径寻找问题，降维简化成了层与层之间的规律跳转。<br>
在第21次探索中，Claude灵光一现。它利用凯莱图（Cayley Digraph）的性质，发现了一种它称为“蛇形”的构造方法：通过特定的步进逻辑），可以在局部生成极具规律的路径。<br>
虽然在第27次探索中，Claude发现简单的坐标旋转会导致在超平面上出现冲突，但它并未放弃。<br>
它在第30次探索中敏锐地察觉到：在某些纤维层，移动的选择可以仅取决于单个坐标。正是这个发现，踢出了通往终点临门一脚。<br>
基于这一发现，在第31次探索中，Claude编写了一个Python程序，给出了一个通用的构造算法。<br>
高德纳随后亲自将该程序简化为C语言版本，并验证m=3, 5, 7, 9, 11等情况，结果全部正确。<br>
Stappers甚至将其测试到了m=101，依然完美契合。<br>
更令高德纳震惊的是，Claude并没有像以往的AI那样只给出一个黑盒结果，而是清晰地展示了它如何从错误中学习、如何重新表述问题、如何利用凯莱图（Cayley Digraph）的群论性质进行推导。<br>
正如高德纳所说，Claude在这一个小时里完成了一次“自动演绎与创造性问题解决”的完美示。这不再是简单的概率预测，而是真正的、逻辑严密的数学发现。<br>
不过，在解决奇数情形后，当Claude继续挑战偶数情况时，它似乎陷入了僵局，连用于探索的程序都出现了报错。<br>
即便如此，但这恰恰证明了科学探索的真实性。AI捅破了最厚的那层窗户纸，而剩下的路，正是人类与AI协作的新起点。<br>
“高德纳”是谁<br>
如果你不了解高德纳，就难懂他的两声“Shock”为何震动计算机科学界。<br>
在计算机科学界，高德纳几乎是一个“活着的传奇”。<br>
1974年，年仅36岁的他便获得了图灵奖。凭借对算法分析体系的奠基性贡献，他也成为历史上最年轻的图灵奖得主之一。<br>
其中最绕不开的，就是那套神作《计算机程序设计艺术》（The Art of Computer Progamming，TAOCP）。<br>
该如何去形容这本书呢？有网友表示得十分贴切：<br>
书还没写完，人们就已经迫不及待把图灵奖颁给了他。<br>
这套书后来被《美国科学家》杂志将其列为20世纪最重要的12部物理科学著作之一，与爱因斯坦《相对论》并列。<br>
比尔·盖茨曾评价：<br>
如果你认为自己是一位非常优秀的程序员……那就读读《计算机程序设计艺术》……如果你能读完这本书，一定要给我发一份简历。<br>
高德纳从1962年开始写这套书。原计划三卷，后来不断扩展，如今已经规划为七卷。<br>
直到2026年，他仍在持续完善第四卷及其后续部分。<br>
正如网友所说，在《Claude’s Cycles》里有两个奇迹：一是Claude证明数学题；二是88岁高龄的高德纳仍在写书。<br>
有趣的是，当高德纳发现当时的计算机排版无法完美呈现数学公式时，他还曾暂停了TAOCP的编写，顺手开发了TeX排版系统。<br>
今天，全世界绝大多数数学、物理和计算机论文，几乎都在使用TeX（或基于它发展的 LaTeX）进行排版。<br>
高德纳甚至给TeX设计了一种极具个人风格的版本号：版本号会不断趋近π（3.14、3.141、3.1415……），象征无限接近完美。<br>
他还宣布自己的程序理论上没有Bug，并悬赏奖励发现Bug的人。<br>
事实上，这并不是他唯一一次为Bug付钱。<br>
最著名的是程序员圈里的高德纳支票。任何发现TAOCP书中错误的人，都可以收到一张由高德纳亲笔签名的奖金支票。<br>
奖金通常是2.56美元——因为256美分等于2⁸，在十六进制里刚好是1美元。<br>
对于程序员来说，拥有一张高德纳签名的支票是职业生涯的最高荣耀，绝大多数获奖者都会将其装裱起来而非兑现。<br>
为了专注研究，高德纳在1990年之后就彻底停用了电子邮件。<br>
他认为邮件会耗费他宝贵的思考时间。如果你想联系他，只能寄实体信件到斯坦福大学。<br>
这样一位仿佛停留在“信息时代前夜”的老派逻辑大师——对每一个字节、每一行公式都追求极致精确。<br>
而如今，正是这样的人，却被一个生成式AI深深震撼。<br>
这本身，就是一件极具冲击力的事。<br>
正如高德纳自己所说：<br>
这绝对是一个令人印象深刻的成功故事。如果香农在天之灵知道自己的名字如今与这样的进步联系在一起，大概也会感到自豪。<br>
向Claude脱帽致敬（Hats off to Claude）！<br>
而这，或许是计算机科学史上最完美的一个一语双关。<br>
高德纳口中的Claude，既是那个在1小时内攻克难题、逻辑缜密的AI推理模型；<br>
也是那位在80年前亲手定义了“比特”、开创了信息论时代的香农（Claude Shannon）。<br>
参考链接<br>
[1]https://x.com/i/trending/2028948713042002348<br>
[2]https://www-cs-faculty.stanford.edu/~knuth/