Linguista

「人物志」高德纳(Donald Knuth)访谈2「LexFridman#219」

Donald Knuth: 编程、算法、难题与生命游戏 | Lex Fridman Podcast #219

访谈框架

├── 一、 引言 (0:00)
│   ├── 介绍 Donald Knuth
│   └── 简述两人之间的渊源
├── 二、 早期的编程经历 (0:48)
│   ├── 第一个程序 (1957年)
│   │   ├── 使用十进制机器语言在 IBM 650 上编写
│   │   ├── 功能：输入数字，输出其因子
│   │   ├── 调试过程：单步执行、设置断点
│   │   └── 目标：理解机器原理
│   ├── 第二个程序：二进制转十进制
│   └── 第三个程序 (井字棋)
│       ├── 引入机器学习
│       ├── 三个“大脑”：Brain 1 (随机), Brain 2 (最优策略), Brain 3 (学习)
│       ├── Brain 3 通过学习避免失败
│       └── 受到贝尔实验室井字棋机器的启发
├── 三、 编程风格与程序之美 (21:15)
│   ├── 编程风格
│   │   ├── 通过阅读程序判断作者能力
│   │   └── 风格体现在技术能力上
│   ├── 文学化编程 (Literate Programming)
│   │   ├── 结合英语和 C 语言
│   │   ├── 程序可运行，也可供人类阅读
│   │   └── 推荐书籍：《Physically Based Rendering》
│   └── 程序之美
│       ├── 美是多方面的
│       ├── 可读性、易理解性、优雅的思想、幽默感
│       ├── 幽默的作用：激发思考，增添乐趣
│       └── 《计算机程序设计艺术》中的笑话和密文
├── 四、 OpenAI 与自动化 (33:15)
│   ├── 介绍 OpenAI Codex 和 GitHub Copilot
│   ├── 对自动化的担忧
│   │   ├── 失去对机器行为的控制
│   │   ├── 难以追溯错误的根源
│   │   └── 过分依赖机器的判断
│   ├── 对自动化的乐观
│   │   └── 人类专注于更需要创造力和智慧的工作
│   ├── 对人工智能潜在威胁的谨慎态度
│   └── 对未来的展望
├── 五、 优化 (42:26)
│   ├── 过早优化是万恶之源
│   ├── 优化应基于对程序实际运行情况的分析
│   └── 延迟绑定（Laziness）的价值
├── 六、 意识 (48:31)
│   ├── 对意识的看法
│   │   ├── 意识是否等同于计算是一个无法回答的问题
│   │   ├── 对当前意识研究持保留态度
│   │   └── 意识可能与大脑中的“适者生存”竞争有关
│   └── 对宇宙的看法：有限宇宙如同加速的“生命游戏”
├── 七、 康威的生命游戏 (57:14)
│   ├── 生命游戏的意义
│   │   ├── 简单规则产生复杂结果
│   │   └── 决定论和自由意志的关系
│   └── 对约翰·康威的回忆
│       ├── 1967 年牛津会议初识
│       ├── 1972 年卡尔加里午餐与“超现实数”理论
│       ├── 《超现实数》的创作过程
│       └── 蒙特利尔会议与“稳定婚姻”问题的新定理
├── 八、 稳定婚姻问题 (1:10:01)
│   ├── 与妻子 Jill 的相识过程
│   └── 维持长久婚姻的建议：相互妥协，共同面对挑战
├── 九、 理查德·费曼 (1:13:21)
│   ├── 加州理工学院的交往
│   ├── 费曼在巴西的故事：批评应试教育
│   └── 物理与数学的区别
│       ├── 物理学家擅长直觉和波动思维
│       └── Knuth 擅长代数和离散思维
├── 十、 Knuth-Morris-Pratt 算法 (1:24:15)
│   ├── 问题描述：在文本中查找特定字符串
│   ├── 算法思想：避免重复比较
│   └── 算法的诞生
│       ├── Jim Morris 的独立发现及代码被删除
│       ├── Vaughan Pratt 的独立发现
│       └── 受 Steve Cook 栈自动机定理的启发
├── 十一、 最难的问题 (1:33:47)
│   ├── 问题描述：随机图演化中“巨分支”的诞生
│   ├── 问题背景：伯克利 Dick Karp 学生的观察
│   ├── 问题解决
│   │   ├── 观察结果并不完全准确，存在一个短暂的时间窗口
│   │   ├── 通过数学推导计算概率
│   │   └── “减缓”“大爆炸”
│   └── 与物理学中的玻色-爱因斯坦统计有关
├── 十二、 开源 (1:51:26)
│   ├── 将 TeX 开源的原因
│   │   ├── 专有权阻碍技术发展
│   │   └── 个人收入足够
│   └── 对开源软件的看法：非平凡软件应收费
├── 十三、 最喜欢的符号 (1:56:39)
│   ├── 《计算机程序设计艺术》索引最后的特殊符号，来自 Dr. Seuss
│   └── 最喜欢的符号是 π，以及在 Masyu 谜题和“优雅图”问题中的应用
├── 十四、 效率 (2:06:12)
│   ├── 工作原则：每周结束前完成最讨厌的任务
│   ├── 疫情期间效率降低
│   ├── 母亲教的另一个工作原则：看到需要做的事情就去做
│   └── 写作的乐趣：希望读者感受到快乐
└── 十五、 人生意义 (2:13:53)
    ├── 相信某种超越人类理解的存在
    ├── 努力去做“那个存在”希望做的事情
    └── 历史的重复与对未来的希望

访谈录

一、 引言

Lex: 大家好，欢迎来到 Lex Fridman 播客。今天，我们非常荣幸地邀请到了传奇计算机科学家 Donald Knuth 教授。这是他第二次来到我们的播客。Don 是图灵奖得主，被誉为“算法分析之父”，著有《计算机程序设计艺术》，同时也是 TeX 排版系统的创造者。他不仅在学术上成就斐然，而且是我认识的最友善、最迷人的人之一。很久以前，我给他写过一封信，他回复了我，从那以后，我们有过多次交流，每一次都让我感到愉快和深受启发。

二、 早期的编程经历

Lex: Don，您的第一个大型程序是在 1957 年夏天用 IBM 650 汇编语言编写的，对吗？

Don: 实际上，我当时是用十进制机器语言编写的。那时我还不知道汇编语言，直到一年后才接触到。那是 1957 年，很少有人听说过汇编语言。你得查阅用户手册才能知道怎么给这台机器写程序。手册上会写，比如“69”代表加载分配器，然后你需要给出要加载到分配器的数字的地址。昨天，我在计算机历史博物馆的朋友 Doug Spicer 给我发了一个链接，是 IBM 1956 年的进度报告，和 1957 年非常接近。1956 年，IBM 向斯坦福大学捐赠了一台 IBM 650，这是最早的一批。视频里展示了 IBM 650 的生产线，他们说这是第 500 台左右。我在那个视频里看到的 IBM 650 比我以前见过的都多。这个视频现在还能在 YouTube 上看到，里面还有一张斯坦福大学课堂的照片，一个老师正在教学生编程，黑板上写着“69 8000”，他正在教他们如何为这台 IBM 650 编写代码，而这台机器使用的是十进制数字。

Lex: 所以指令是由十个十进制数字组成的？

Don: 是的，两个数字表示操作码，另外四个数字表示操作数，再四个数字表示下一条指令的地址。有一本手册描述了每个数字的含义。如果那本手册写得好，我可能就不会进入计算机科学领域了。但它写得太糟糕了，我当时只是一个大一新生，却觉得我能写出一本更好的手册。

Lex: 您后来确实做到了。

Don: 是的，后来我开始在计算机中心工作，也确实写了一些手册。

Lex: 那么，您在1957年6月写的第一个程序是...

Don: 不是井字棋，那是第三个。第一个程序是因数分解。

Lex: 您是在这台大型机上拨动转盘来输入数字？

Don: 是的，你拨动转盘设置一个数字，然后机器会在卡片上打孔输出这个数字的因子。输入是一个数字，输出是它的因子。我当时写的程序，现在还保存着一份副本。

Lex: 您还记得大概有多少行代码吗？

Don: 一开始大约 20 行，但我不断地调试，代码行数就增加了。我第一次写程序时就发现了调试这回事。

Lex: 在只有数字的程序上，调试是什么样的？

Don: 我记不清当时是怎么把程序输入机器的了，可能是用卡片打孔。每张卡片可能存储一条或几条指令。我通常在晚上没人的时候使用机器。我拨动转盘输入数字，然后有一个开关可以单步执行指令，并显示结果。还有一个开关可以设置断点。我会观察程序执行，比如它会用输入的数字除以 2，如果没有余数，那么 2 就是一个因子。我会继续除以 3，直到找到所有的因子。如果发现一些奇怪的现象，那就是发现了 bug。

Lex: 比如说除以了 1 而不是 2，或者跳转到了错误的指令？

Don: 是的，这些都是常见的错误。可能我在寄存器中遗留了一些不应该留下的数据。第一个晚上我大概能算出 30 的因子：2，3 和 5。

Lex: 您当时经常熬夜编程？

Don: 是的，从大一到大二期间，我几乎不需要睡觉。我在高中的时候也经常熬夜。

Lex: Rodney Brooks 跟我讲过一个故事，说他在研究您开发的 TeX 时，好像把机器弄坏了，而您正等着他们修好机器，好继续熬夜工作。

Don: 哦，那种情况经常发生。当时斯坦福人工智能实验室的机器经常宕机，因为有很多优秀的程序员每天都在修改操作系统。

Lex: 您当时是不是经常让 Rodney 感到压力很大？

Don: 有趣的是，我们互相敬畏。

Lex: 回到您的第一个程序，您当时的目标是什么？是希望找到一个大的质数吗？

Don: 不是，我的目标是看到机器上的灯光闪烁，理解这台神奇的机器是如何完成那些手工计算需要很长时间才能完成的任务的。

Lex: 您的第二个程序是什么？

Don: 第二个程序是将数字从二进制转换为十进制，比第一个简单多了，也没那么多 bug。第三个程序是井字棋。

Lex: 井字棋程序很有意思，它还包含了一些机器学习的元素。

Don: 是的。井字棋的棋盘是一个 3x3 的网格，每个格子有三种状态：空、X 或 O。3 的 9 次方... 我应该能算出来...

Lex: 您现场计算的样子很有趣。

Don: 3 来自三种状态。而当时的 IBM 650 只有 2000 个十位数的存储空间。为了记录每种棋局，我需要 3 的 9 次方个位。虽然是十进制机器，不是二进制，但它有一个奇怪的指令，可以测试一个十位数是否每一位都是 8 或 9。我用一个数字来表示每个棋局的状态，0 表示不利，1 表示有利。如果赢了一局，就增加该棋局的数值，减少对手的数值。我需要用 20000 个数字来存储所有可能的棋局，还要包括程序代码、逻辑，以及如何与用户交互等。因为棋盘可以旋转和翻转，所以每个棋局大约等价于其他八个棋局。我需要找到一种有效的表示方法来利用这种对称性，否则无法进行学习。

Lex: 所以您设计了三种不同的“大脑”？

Don: 是的，Brain 1 随机落子，Brain 2 拥有已知的井字棋最优策略，Brain 3 则进行学习。我可以让它们互相比赛，也可以让用户与它们对战。两个 Brain 1 对战大约 600 局后，会收敛到一种安全的和局策略，因为它只学习如何避免失败，而不是如何获胜。让新手和熟练的玩家对战，新手也能学会如何下得更好。完成这个程序后，我感觉自己理解了编程。

Lex: 您为什么想让 Brain 3 学习呢？您对学习系统的兴趣是否一直持续？

Don: 这很自然，就像 Rodney Brooks 教各种小型设备学习一样。

Lex: 在那些年里，是否有人讨论过受图灵启发的关于计算本质的问题？

Don: 我当时没有想过那些问题，那太哲学了。我当时只是一个大一新生，更像是一台机器，沉迷于具体的编程，而不是思考重大的问题。

Lex: 您什么时候开始从更宏观的角度思考计算，比如通用图灵机？

Don: 我在大四的时候上过可计算性理论的课程，读过 Martin Davis 的书。虽然觉得很有趣，但我只是为了通过考试而学习，并没有自己去发明那些理论。

三、 编程风格与程序之美

Lex: 您曾经说过，通过阅读程序可以看出作者的变化。您是怎么做到的？程序员的独特风格体现在哪些方面？

Don: 就像海明威和詹姆斯·乔伊斯的写作风格不同，音乐家的风格也各不相同。我最近在疫情期间花了很多时间弹钢琴，发现了一首曲子，是把《洋基歌》改编成贝多芬、德彪西、肖邦和格什温等不同风格。我觉得这很巧妙，因为它展示了如何“逆向工程”不同作曲家的风格。具体到编程，我曾经读过一个编译器程序，它是由卡内基梅隆大学的一个团队编写的。我可以看出，在某些部分，作者不太擅长在寄存器之间高效地移动数据，原本可以用一条指令完成的操作，却用了三条或更多。这是一种非常明显的风格变化。当然，也有一些闪光点，可以用一条指令完成通常需要两条指令才能完成的操作，因为作者对机器的运作方式有深入的了解。

Lex: 所以更多的是思想的巧妙，而不是分号的使用或者长短句的选择？

Don: 是的，我能看出代码中的思想，以及不同风格的思考方式和经验。

Lex: 如果有人看您的代码，他们能看出这是一种独特的思维方式吗？您的代码有什么样的特点？

Don: 我现在使用的是文学化编程，所以代码是英语和 C 语言的结合。如果只看 C 语言部分，可能会注意到我比其他人更频繁地使用全局变量，更多地使用内联展开，等等。这是我使用的 C 语言的一个子集。

Lex: 所以有一点风格化的特点。能解释一下文学化编程吗？

Don: 文学化编程就是在代码中交替使用英语和 C 语言（或其他编程语言）。我认为这是 TeX 项目中最重要的成果。我意识到我的程序不仅要被计算机读取，还要被人阅读，而排版可以极大地增强可读性。Matt Pharr 等人写的《Physically Based Rendering》一书就是一个很好的例子，整本书就是一个文学化程序，它不仅告诉你如何实现电影中的各种图形效果，而且代码还可以运行。这是一种通过讲故事的方式来教授编程的方法，程序既可以运行，又可以被人类阅读，特别是被作者本人在一段时间后阅读。

Lex: 所以这是一个很好的测试，如果您自己能够轻松地理解自己一周或一年后写的代码。

Don: 是的，这真是自切面包片发明以来最伟大的事情——文学化编程！

Lex: 您曾经在一次采访中回避了一个问题，我想再问您一次：什么样的程序是美的？

Don: 我之所以没有回答，是因为这个问题的答案有很多很多。美的定义因人而异，因时而异，取决于你所寻求的标准。一个程序只要能正常工作，就可以说是美的；如果它易于理解，也是美的；如果是文学化编程，也是美的；如果它能让你发笑，也是美的。

Lex: 我同意您的观点，可读性、易理解性、优雅的思想，以及幽默感，都是程序之美的体现。我记得以前在 Stack Overflow 上讨论过在代码注释中加入幽默是否合适，我认为适当的幽默可以展现程序员的个性、智慧和趣味。

Don: 几天前，我收到了以前在 Addison-Wesley 的编辑送来的一份礼物。他在整理房子时，发现了一些公司内部关于《计算机程序设计艺术》的档案，是 1960 年代的。他原本打算保存这些档案，但现在觉得负担太重，就送给了我。里面有很多信件，有些是我写给他们的，但更多的是他们写给早期试读者的，询问他们是否应该出版这本书。其中，Bob Floyd 的意见非常重要，他是 60 年代我重要的合作者，可惜英年早逝。他对书中的幽默发表了意见，我们会讨论是否保留某个笑话。他们还进行了焦点小组访谈，询问人们对计算机编程书中加入幽默的看法。我的理念是，最好的幽默是让读者知道这里可能有一个笑话，只要你理解了就能明白，这是一种激励读者思考的方式。当然，幽默是很微妙的，不同的时代、不同的文化都有不同的幽默感。

Lex: 比如俄罗斯的黑色幽默。

Don: 是的，不同的经历会产生不同的幽默感。我在《计算机程序设计艺术》的第二卷中加入了一个密文，需要破解一个 RSA 密钥才能解密，这个密钥比现在已知的任何密钥都要长。随着计算机速度的不断提高，也许 100 年后会有人解开这个密文，并发现其中的笑话。

四、 OpenAI 与自动化

Lex: 我来给您介绍一下 OpenAI，您可能会感兴趣。OpenAI 是一家从事人工智能研究的公司，他们开发了一个名为 Codex 的语言模型，可以生成相当不错的代码。在这个基础上，他们与 GitHub 合作开发了一个名为 Copilot 的系统。它的工作方式是，当你开始编写代码时，它可以自动补全代码。例如，您可以写下第一行代码，并添加一些注释，说明代码的功能，然后它就可以为您生成整个函数。它的表现相当出色，虽然不能保证完全正确，但通常都能很好地完成代码补全的任务。

Don: 但是你怎么知道它做得好不好呢？

Lex: 你可以看到很多它做得很好的例子。它不是为你生成代码，而是给你提供建议，让你来修正，而不是从头开始写。您觉得这个想法有意思吗？

Don: 每年我们都会越来越多地失去对机器行为的控制。人们会说，“这似乎有效”。以前在加州理工学院的时候，有一个人非常擅长演讲，他可以发表非常鼓舞人心的演讲，但一个小时后，你会发现你根本不记得他讲了什么。他认为计算机是否得到正确答案并不重要，重要的是它是否让你开心。如果你的老板为此付钱，你就能保住工作，养家糊口，幸福比真理更重要。他不相信真理，但他是一位哲学家。现在，我们正在朝着这个方向发展，越来越多的事情被“这似乎有效”所取代。当存在利益冲突时，双方都不知道决策是如何做出的。我们现在意识到这是不好的，但想想看，五年、十年后，事情会变得更加脱节，每一件事都基于前一年的事情。

Lex: 自动化程度越高，就越难追溯错误的根源。

Don: 是的，而且是以指数级的速度增长。

Lex: 这是黑暗的一面。但积极的一面是，自动化程度越高，人类就越能专注于做人类最擅长的事情。

Don: 这是积极的一面，但它也伴随着黑暗。

Lex: 那么您是支持理解，而不是盲目追求自动化？

Don: 我支持理解。如果人工智能能帮助我们做出更好的医疗诊断，或者指导科学实验，或者治愈疾病，那当然是好事。但当它以一种严重的方式影响人们的生活时，就需要谨慎。如果只是为了满足极客的爱好，那当然没问题。

Lex: 所以需要非常小心。现在看起来只是有趣的小工具，可以帮助你编写一些 JavaScript 代码，但几年后，你会在它的基础上构建更多东西，然后突然间，你就会拥有基于人工智能的自主武器系统。

Don: 到那时，我们都死了，也就无所谓了。

Lex: 在宇宙热寂到来之前，最好还有某种意识存在，来见证这一切。

Don: 我希望能推迟宇宙热寂的到来。也许这种技术就是我们没有收到外星文明信号的原因，因为他们不想和我们有任何关系。

Lex: 所以您对人工智能和自动化带来的生存威胁，以及人类逐渐退出历史舞台感到担忧？

Don: 现在的人类比 100 年前拥有更大的破坏力。

Lex: 您对人类解决问题的能力感到乐观吗？

Don: 就像硬币的两面，有好有坏。

Lex: 您对人工智能的未来持乐观态度吗？

Don: 从某种角度来说，我是乐观的。想想那些因为文明而发生的变化，这些变化不会自然而然地发生。例如，我们房间里的每一样东西，铅笔、书、桌子、麦克风、衣服、食物，都是被发明出来的。我们继承了数百万种发明。这么多东西不可能没有问题，不可能每一个都没有负面影响。但令人惊讶的是，这么多东西都能正常运转，这非常了不起。

Lex: 这也是我对人工智能感到乐观的原因。我们使用各种各样的技术，却不知道它们是如何工作的，有成千上万的聪明人参与了这些技术的建造，而它们却很少出错。

Don: 我们可以识别出那些不起作用的东西，并试图改进它们，尽管通常是以次优的方式。

Lex: 您对人类的理性有信心吗？

Don: 我对人类理性的信心正在下降。

Lex: 虽然人类可能不理性，但他们很聪明，也有自己独特的美。我相信大多数人都有善良的愿望和能力，爱最终会获胜。

五、 优化

Lex: 在《计算机程序设计艺术》中，您写道：“程序员们在错误的地方和错误的时间，花了太多时间担心效率问题，过早优化是万恶之源，或者至少是大部分编程中的万恶之源。” 您能解释一下这个观点吗？什么是错误的时间和错误的地点？

Don: 首先，“优化”这个词，我刚开始写软件的时候，作为编译器作者，优化意味着改进翻译，使程序在机器上运行得更快。在 1960 年代初，我查阅了一本未删节版的词典，发现“优化”的含义是“乐观地看待”。现在，人们开始进行成本优化等各种优化，许多算法、经济学等领域的子领域都基于所谓的优化。但当我写下那句话时，“优化”指的是改变程序，使其更适应机器。我发现，当一个人编写程序时，他或她往往认为最难写的部分对计算机来说也是最难执行的。例如，我写了十页代码，但其中一页花了我一周的时间来写，我就会下意识地认为计算机执行到那一页时会变慢。

Lex: 这是一种拟人化的想法。

Don: 是的，这当然很愚蠢。但我们在编写代码时，并不知道计算机实际上会如何执行这段代码。人们对计算机的实际运行情况了解甚少。我曾经做过一个测试，我们研究了一个 Fortran 编译器，发现它 80% 以上的时间都花在了读取注释卡上。但作为程序员，我们真正关心的是它如何快速地处理一个包含多层括号的复杂表达式，并将其转换成某种形式，但这只占了不到 1% 的时间。如果我们优化了那部分，我们并不知道自己在做什么。但如果我们知道它 80% 的时间都花在了注释卡上，我们可以在十分钟内让编译器的运行速度提高一倍以上。而你只有在完成了程序之后，才能通过实证研究，或者某种性能分析工具，才能知道哪些部分是重要的。

Lex: 所以您认为这个原则具有普遍适用性？

Don: 我很高兴它具有普遍适用性，但我当时只是在有限的上下文中说的。

Lex: 这个观点引起了很多人的共鸣，因为程序员的思维中有一种喜欢优化的倾向，所以需要在“偷懒”和“延迟绑定”与优化之间进行权衡。

Don: 是的，优化的代码有一种美感。另一个关于优化的重要原则是“延迟绑定”，或者说“偷懒”，就是尽可能推迟做决定。我们现在已经从量化的角度理解了延迟绑定的价值。例如，在即时制造等领域，推迟决策可以提高系统的灵活性。在许多情况下，最优的策略是不提前做决定，而是设计一个灵活的系统，以便能够根据情况的变化而变化。

六、 意识

Lex: 我想问您一个奇怪的问题。Roger Penrose 曾经谈到过计算、计算机和意识，他提出人脑发现数学思想的方式是计算机无法做到的，通用图灵机无法做人脑能做的所有事情，包括发现数学思想和意识。您认识 Roger 吗？

Don: 我女儿的孩子和他的孩子在牛津一起玩过。

Lex: 您认为计算机存在这样的局限吗？您认为意识不仅仅是计算吗？您认为人脑的思维方式不仅仅是计算吗？

Don: 我可以回答“是”或“否”，但我没有任何理由...

Lex: 所以您认为没有必要在这方面有某种直觉？您认为这是一个无法回答的问题？

Don: 我认为这是一个无法回答的问题，我的意见并不比其他人更重要。

Lex: 您认为科学最终也无法解释意识？

Don: 就像天使可以在针尖上跳舞一样，我不知道。有很多事情是我们可以推测的，但我不想让别人说“这是 Knuth 说的，他很聪明，所以这一定是对的”。我认为这是我们永远不会知道的事情。

Lex: 这是一个很有趣的说法。我个人认为，人脑的运作方式并非无法用科学来解释。

Don: 我并不否认这种可能性。但目前，我没有一个很好的直觉。

Lex: 您认为图灵关于图灵测试的论文中提出的“机器能思考吗？”这个问题不重要？

Don: 我不认为这个问题重要，因为它属于那种“知道也很好，但可能超出了我们的认知范围”的问题。我对黎曼猜想更感兴趣。

Lex: 您说“超出认知范围”，是指这个问题还没有被很好地形式化，以至于无法提出一个清晰的问题？

Don: 是的，这就是为什么它超出了认知范围，但这并不意味着它最终不会被形式化。也许有一天我们会理解意识，但据我所知，这至少还需要 200 年。我 20 年前听过关于意识的讲座，当时的主讲人说，基本上所有关于意识的著述都是胡说八道。

Lex: 我不太同意这个观点。长期以来，意识仍然属于哲学的范畴，所以只是没有根据的空谈。但一旦你开始创造与人类互动的人工智能系统，它们拥有个性和身份，你就开始触及到意识的问题，不是从哲学的角度，而是从工程的角度。

Don: 我完全同意。20 年前的那次讲座上，就有神经学家指出，人类在意识到自己做出决定之前，就已经做出了决定。他们可以检测到信号在被意识到之前就已经发送到了手臂。现在，关于大脑的架构，也有一些新的模型。例如，Christos Papadimitriou 和另外两个人，一年前在美国科学院院刊上发表了一篇文章，提出了一个可以与意识实验结果相吻合的模型。他们甚至还有一种机器语言，可以用来编写代码和测试假设。所以，我们可能会有一个重大的突破。我个人认为，关于意识，我听过的最好的模型是，我们的大脑中持续进行着“适者生存”的竞争。当我说话的时候，所有可能的选项都在那里，进行着某种投票，其中一个胜出，并影响到下一句话。

Lex: 我喜欢这种“讲故事”的部分，对我们人类来说，感觉上有一个连贯的故事，就像文学化编程一样。我不知道内部的程序是什么，但我得到了一个关于发生了什么的好故事，感觉一切尽在掌握。但也可能内部的计算非常混乱，有很多相互竞争的想法，最后只是给你生成了一个连贯的故事让你相信。

Don: 是的，所以我更喜欢谈论我擅长的事情，而不是那些我只是旁观者的事情。

七、 康威的生命游戏

Lex: 您对元胞自动机和“生命游戏”有什么看法？您玩过这些游戏吗？

Don: 我认为“生命游戏”非常棒，它展示了很多关于事物如何在创造者不理解的情况下进化的东西，有点像学习的力量。对我来说，“生命游戏”最重要的意义在于，它让我思考了什么是自由意志。因为“生命游戏”显然是完全确定性的。

Lex: 是的。

Don: 另一方面，我很难相信任何有孩子的人会不相信自由意志。John Conway 曾经说过，他想知道在“生命游戏”进行到一个特别有趣的阶段时关掉计算机会不会不道德。

Lex: 对我来说，“生命游戏”的魅力在于，它清晰地展示了从简单的初始条件和规则出发，如何产生复杂的、看起来像是有生命力的模式。如果宇宙是有限的，我们都生活在一个被放慢了无数倍的“生命游戏”中。

Lex: 您认为分析算法的技术可以用来分析“生命游戏”吗？我们能理解它吗？还是说它太奇怪了？

Don: 我在《计算机程序设计艺术》第四卷的 Fascicle 6 中写了十几个关于“生命游戏”的练习题。Bill Gosper 提出了一个算法，可以让模拟“生命游戏”的速度提高成千上万倍。有一个网站叫 Golly，你可以去看看。

Lex: 您能谈谈 John Conway 吗？我正在读一本纪念他的专刊。您认识他吗？

Don: 我在他家过夜过几次。他一年前因为新冠去世了。

Lex: 您对他有什么印象深刻的回忆？他的工作是否在技术层面上启发了您？他本人是否在某种程度上启发了您？

Don: 是的，所有这些问题的答案都是肯定的。我第一次见到他是在 1967 年的牛津，当时我大概...

Lex: 您当时才 20 岁左右吧？

Don: 是的，1967 年。那次会议上，我做了一个关于现在被称为 Knuth-Bendix 算法的报告。他做了一个关于纽结的著名演讲，这个演讲后来衍生出了成千上万篇论文。他报告了他高中时做的一些研究，但他从未发表过。他在演讲的最后，用一些塑料棒组装了一些纽结，然后又把它们拆开，那是一场非常戏剧性的演讲。

Lex: 您当时在场？

Don: 是的，我在参加同一个会议。1972 年春天，我在卡尔加里，正好他也去那里访问，我们一起吃了午饭。他在餐巾纸上写下了关于他称之为“数”的理论的所有事实，他在餐巾纸上写满了关于他的“数”的概念的定理。这非常美妙。1972 年，我开始了学术休假，去了挪威。在 12 月的一个深夜，我突然想到，Conway 的“数”的理论可以作为一个很好的例子，教给学生如何进行研究，以及研究的乐趣。我还读过 Alfred Renyi 写的一本对话体的书，里面有两个角色像苏格拉底一样讨论数学。第二天早上，我叫醒了我的妻子 Jill，我说我想写一本关于 Conway 理论的书。

Lex: 尽管您当时应该在写《计算机程序设计艺术》。

Don: 是的，但我真的很想写这本书。我们制定了计划，我以为我可以在一周内完成。一月份，我在奥斯陆市中心的一家酒店租了一个房间，那一周我什么也没做，只是写 Conway 的理论。我把书名改成了《超现实数》。我们开玩笑说，Conway 也许会喜欢在酒店房间里发生一段风流韵事，所以我们计划让她在那一周来看我两次。那家酒店是由一个教会组织运营的，所以我们还得偷偷摸摸的。总之，那是疯狂的一周。但我弄丢了 Conway 写满理论的餐巾纸，我找不到了，所以我只好凭记忆重现他在卡尔加里午餐时告诉我的内容。在写书的过程中，我经历了书中角色所经历的一切。我从两个公理开始，一切都由此定义，但你需要去发现为什么。我犯的每一个错误，我的角色也会犯。那一周我工作得非常投入，那是我一生中最激动、最紧张的一周。

Lex: 您能解释一下为什么会发生那样神奇的一周吗？

Don: 我也不知道，就好像我被“附体”了一样。我把书稿寄给了 Conway，他说我把其中一个公理弄错了。“小于或等于”和“不大于”之间是有区别的。

Lex: 在逻辑理论中，这确实会有影响。

Don: 是的，我选择的方式比 John 最初的方式更难。四月份，我们去剑桥拜访了他，和他一起待了几天。他给我们看了很多我以前从未见过的谜题，还教了我们一种玩单人纸牌游戏的巧妙方法。夏天，我又花了一周时间，在挪威山区的一个地方，用正确的公理重写了这本书。这就是我与 Conway 最密切的一次合作。

Lex: 从一张餐巾纸开始的故事。

Don: 后来，我在蒙特利尔做一系列关于“稳定婚姻”问题的讲座，总共七次。他在我第六次和第七次讲座之间来到了蒙特利尔，我们在一个聚会上见面了。我开始向他介绍我正在研究的问题，他思考了一下，提出了一个漂亮的理论，证明了所有“稳定婚姻”的集合构成了一个格，并且有一种简单的方法可以找到两个“稳定婚姻”的最大下界和最小上界。我第二天就可以在我的讲座中使用这个理论，而他是在聚会期间想出这个定理的。

八、 稳定婚姻问题

Lex: 您提到了您的妻子 Jill，也提到了“稳定婚姻”。您能讲讲你们相识的故事吗？

Don: 上个月我们庆祝了结婚 60 周年。我们是在我大二，她大一的时候认识的。我当时正在和她的室友约会，我想向她征求一些策略上的建议，结果我发现我更喜欢她的建议，而不是她的室友。

Lex: 你们是同一个专业的吗？

Don: 不是，因为我读到过一些关于在研究生阶段在计算机上研究一个困难的计算机科学问题的内容。

Lex: 所以她是艺术家，而您是极客？

Don: 是的。

Lex: 她当时在读什么计算机科学的资料？是您写的手册吗？

Don: 她当时在上计算机科学的课程，读的是我写的手册。

Lex: 您是她的导师？

Don: 不是，不是。我们有过一些痛苦的时刻，因为她要学习一些概念。我从她那里学习艺术，我们偶尔会一起做一些设计项目。我们每年都会写一张圣诞卡片，我们都必须在美的概念上做出妥协。

Lex: 您是什么时候爱上她的？

Don: 就是我向她询问她室友的那一天。

Lex: 关于维持长久的婚姻，您有什么秘诀可以分享吗？“稳定婚姻”是一个术语...

Don: 是的，“稳定婚姻”是一个技术术语。不同的人需要学会如何妥协，如何共同努力，如何面对生活中的起起落落和危机。只要你不期望每时每刻都幸福，就很有希望保持稳定。但如果你认为婚姻中不应该有任何挫折...

Lex: 所以你们在写圣诞卡片的时候，需要在美的概念上做出妥协。

Don: 是的。

九、 理查德·费曼

Lex: 您说过理查德·费曼是您敬仰的人。你们在加州理工学院认识的吗？

Don: 是的，我们在加州理工学院认识。

Lex: 您是计算机科学领域的重要人物，而他是物理学领域的重要人物。您有没有从他那里获得过什么启发？

Don: 我们会去听对方的讲座。但如果我看到他坐在前排，我就会很紧张，我会说错几句话。我经常提到他在巴西的经历，他指出那里的物理教学方式是错误的，学生们只是学习如何通过考试，而不是学习真正的物理。他说，如果你想让我证明这一点，我可以翻到这本教科书的任意一页，告诉你这一页有什么问题。而那本教科书是他的东道主写的，这很尴尬，但他事先问过他的东道主是否应该说实话。这个故事体现了教育在各个领域都可能出现的问题，需要 periodically 地从“授予文凭”的过程回归到“传授知识”的过程。

Lex: 这种现象在很多地方仍然存在，教育机构太容易陷入“文凭主义”，而不是“启发主义”。

Don: 是的，这和我们之前谈到的“希望计算机给出正确答案”的问题很像。Bob Floyd 在 60 年代给我看过一个他很喜欢的卡通，画的是两个人站在一台大型计算机前，一个人对另一个人说：“这台机器在一秒钟内就能完成一百万人一百年才能完成的工作。” 另一个人说：“哦，那你怎么知道它是对的呢？”

Lex: 这句台词很经典。您觉得物理和数学之间有什么有趣的区别吗？您是否研究过物理学，就像您提到的费曼？物理学的思维方式、直觉，与计算机科学、理论计算机科学、数学科学有什么不同？它们之间有很大的差距吗？还是说它们有很多重叠之处？

Don: 我认为它们非常不同。我一开始是物理专业的，后来转到了数学专业。原因可能是我在物理考试中能得 A+，但我不知道自己是如何解出那些题的。但在数学方面，我知道老师为什么出那些题，我还能想到其他可以出的题。我认为这是一种非常不同的思维方式。这与你对“极客”的理解有关，我的一些计算机科学家朋友非常擅长物理，而另一些则不然。我擅长代数，但不擅长几何。

Lex: 所以数学也分不同的领域。

Don: 是的，物理学家用波动的方式思考问题，我也可以用波动的方式思考，但这就像狗用后腿走路一样。

Lex: 所以您更喜欢用离散的方式看待世界？

Don: 是的，我不确定图灵是否会成为一个伟大的物理学家，他可能是一位优秀的化学家。但我认为，计算机科学在很大程度上是由那些擅长与某些特定概念产生共鸣的人推动的。

Lex: 就像量子计算，它需要一种不同的思维方式。

Don: 是的，量子计算就像是计算机科学和物理学在大脑层面的交叉点，至少在目前是这样。但我认识的物理学家都有非常强大的直觉。统计力学，我研究过统计力学，随机过程与算法有很多关联。物理学有很多不同的分支，就像数学也有很多不同的分支。但问题是，当物理学家们交谈时，他们使用的语言与他们撰写说明性论文时使用的语言完全不同。我从《科学美国人》杂志上读到关于量子力学的文章，但完全看不懂。但当我读到他们之间如何用本征值和其他数学术语相互描述时，我就明白了。但霍金说过，你在书中每放一个公式，就会失去一半的读者，所以他没有在书中放任何公式，所以我完全看不懂他的书。

Lex: 费曼也以类似的方式说话，他以自己强大的直觉为傲，但同时也隐藏了他所做的真正深入的计算。

Don: 有一件事我一直没能和他一起研究，我希望我能有更多的时间和他一起研究，我可以给你描述一下。有一件事以我的名字命名，叫做 Knuth 箭头表示法，它是一种表示非常大的数字的表示法。后来我发现有人在 1830 年代就发明了它，它很容易理解。你从 x + x + x + x 开始，加 n 次，你可以把它写成 xn，这就是乘法。然后你做 x * x * x * x，乘 n 次，这就是幂运算，x 的 n 次方，我用一个箭头表示。

Lex: 所以 xn 没有箭头是乘法，x 箭头 n 是 x 的 n 次方？

Don: 是的。x * x * x，n 次，显然是 xn。x + x + x，n 次...

Lex: 哦，对。然后 xn，乘法，然后是 x 的 n 次方？

Don: 然后，箭头表示对指数进行同样的操作。一个箭头表示 x 的 n 次方。现在，我用两个箭头，就表示 x 的 x 的 x 的 x 次方，x 叠 n 次。例如，2 双箭头 3，就是 2 的 2 的 2 次方，也就是 2 的 4 次方，等于 16。这就是双箭头，然后你可以用三箭头，等等。我有一篇论文叫做《大数》，你可以用它来给你的朋友留下深刻印象，说出一个他们从未想过的数字。我给它起了一个特殊的名字，我们还设计了一个包含草书 k 的字体。但我认为它实际上是 10 四箭头 3 之类的，这个数字大到你无法理解。我和费曼谈到了这件事，他说：“我们只用双箭头，但我们不用整数，而是用复数。”

Lex: 好的。

Don: 所以你有 x 的 x 的 x 次方，但 x 双箭头 2.5 是什么？这不难计算，可以在这些值之间进行插值。但 x 双箭头 i 或 1 + i，或某个复数是什么？他声称不存在一个解析函数可以做到这一点，但我不知道他怎么能断言这是不正确的。他的下一个问题是，能不能有复数个箭头？

Lex: 哈哈，好吧。

Don: 好吧，这很有趣。您能描述一下 Knuth-Morris-Pratt 算法是做什么的吗？以及您是如何开发出它的？这是您众多以您的名字命名的成就之一。

十、 Knuth-Morris-Pratt 算法

Don: 实际上，它应该被称为 Morris-Pratt-Knuth 算法，但我们在发表论文时决定按字母顺序排列。这个问题是现在每个使用搜索引擎的人都知道的，你有一个很大的文本集合，你想知道“Knuth”这个词是否出现在文本中的任何地方，或者其他任何词。我们有一个很大的文本，它是一维的，第一个字母，第二个字母，等等。你想能够做到这一点，最显而易见的方法是，假设我们在寻找“Morris”，我们遍历文本，直到找到字母“m”，然后查看下一个字母，确实是“o”，然后是“r”，但哦，太可惜了，下一个字母是“e”，所以我们没有找到“Morris”。然后我们回过头去，重新开始寻找另一个“m”。这就是最显而易见的方法。

Lex: 对。

Don: Jim Morris 注意到有一种更聪明的方法可以做到这一点。显而易见的方法会在找到第 1000 个字符是“m”后，从第 1001 个字符开始。但他发现，我们已经读过了“o”和“r”，我们知道它们不是“m”，所以我们可以跳过它们，不需要再读一遍。当要查找的词不是“Morris”，而是像“abracadabra”这样在开头、中间有重复模式的词时，这就变得非常 জটিল。

Lex: 对，对，对。

Don: 所以他解决了这个问题，并把它放到了伯克利的系统软件中，我想是伯克利 Unix 的某个例程，用于在文本中查找模式。他没有解释这个算法，几个月后，有人看到这段代码，觉得不对劲，就把它删除了。所以他有这个算法，但它没有被保留下来，因为它没有被理解。当时没有人知道这个算法。Vaughan Pratt 在一两年后也独立发现了它，我忘记了他当时在研究什么问题了，可能是关于回文的某个技术问题，他并不是在研究文本搜索，而是在研究一个与之相关的抽象问题。当时，Steve Cook 是伯克利的一位教授，伯克利计算机科学系犯的最大错误就是没有给他终身教职，所以 Steve 去了多伦多。但我在 Steve 还在伯克利的时候就认识他，他提出了一个非常奇怪的关于“栈自动机”的定理。栈自动机是一种机器，它不能做图灵机能做的所有事情，它只能查看栈顶的东西，或者向栈中添加更多东西，或者从栈中取出东西。它不能记住一个很长的符号串，但它可以记住它们的逆序。如果你告诉一个栈自动机“abcde”，它可以告诉你“edcba”。除了这个它能看到的东西之外，它没有任何其他内存。Steve Cook 证明了一个惊人的结论：如果一个栈自动机可以用任意时间识别一个长度为 n 的字符串的语言，那么一台普通计算机可以用 n log n 的时间识别同一种语言。Steve 有一种方法可以将一个不断进行的计算，通过使用不同的数据结构，转换成你可以在普通计算机上快速完成的计算。栈自动机运行得很慢，但不知何故，它能做到这一点，就意味着一定存在一种快速的方法。我认为这是一个非常酷的定理，所以我在一个我知道栈自动机可以解决的问题上尝试了它。

Lex: 好的。

Don: 但我不知道如何在普通计算机上快速解决这个问题。我认为自己是一个相当不错的程序员，但我就是想不出任何有效识别这种语言的方法。我研究了 Steve Cook 的构造，我在黑板上写满了栈自动机所做的一切，然后我试图从中找出规律，以及他是如何将它转换成普通计算机上的程序的。最后，我终于明白了，我之前缺少的东西就是我应该在我的程序中做什么。现在我有一个高效的程序了。如果我没有 Steve 的定理，我永远也不会想到这样的方法，而他的定理是一个纯粹抽象的东西。

Lex: 实际上，您是试图直观地理解如何将栈自动机用于字符串匹配问题。

Don: 是的，我一开始研究的并不是字符串匹配问题，但后来我意识到字符串匹配问题也可以用栈自动机来解决。当我查看它告诉我的内容时，我就得到了一个解决字符串匹配问题的巧妙算法。它准确地告诉了我应该在遍历字符串的过程中记住什么。我把它写了下来，并写了一篇名为《自动机理论可以很有用》的小论文。因为这是我第一次，我读过很多关于自动机理论的论文，但它从未教会我如何改进我的日常编程。那是你在期刊上发表的东西，很有趣，但这里有一个问题，我不知道如何编写程序，我有一个自动机理论的定理，然后我就知道如何编写程序了。所以对我来说，这是一个人生的转折点，我开始思考也许我应该学习更多关于自动机的知识。我把这篇论文给 Vaughan Pratt 看，他说这和他正在研究的东西很相似。Jim Morris 当时也在伯克利，他后来有了一段辉煌的职业生涯。Vaughan 是我的同事，也是我的学生，但这是在 Vaughan 来斯坦福之前，他还是一个研究生。我们发现我们都在研究同一个问题，所以这是我们的算法，我们每个人都独立发现了它，但我们每个人都发现了这个“大象”的不同部分，所以我们可以把我们的发现结合起来。我负责撰写论文。

Lex: 是什么让这个“大象”活了起来？

Don: 因为我起草了这篇论文《自动机理论可以很有用》，Vaughan 和 Jim 看到了这篇论文，然后我们就进行了合作。也许他们也曾考虑过写一些关于这个问题的文章。

十一、 最难的问题

Lex: 我想问您一个有点“无厘头”的问题。上次我们谈话时，您告诉了我最美的算法是什么，是关于强连通图的。那么，对您个人来说，计算机科学中最难的问题、最难的想法是什么？您必须解决的最难的事情是什么？

Don: 哦，我不知道该如何回答这样的问题，但在这种情况下，答案很清楚，那就是“巨分支的诞生”。

Lex: 好的。

Don: 我来解释一下，因为这实际上也涉及到物理学，还涉及到玻色-爱因斯坦统计，但它有一些有趣的故事，也和伯克利有关。我们从随机图的概念开始，我们有 n 个完全不连通的点，没有任何几何结构，没有哪个点比其他点更远，所有的点都是完全一样的。假设我们有 100 个点，我们把它们从 00 到 99 编号。现在，我们用 π 的数字，每次取两个，所以我们有 31，41，59，26，我们一直取下去。我们取前两个数字 31 和 41，在点 31 和点 41 之间建立一条边。然后我们取 59 和 26，建立另一条边。随着我们不断添加边，图变得越来越大，连通性也越来越强。我们从 n 个点开始，添加 m 条边。每条边都是完全随机的，我们不考虑之前添加过的边，我们甚至可能得到一条从一个点到它自身的边。我们正在随机地演化一个图。当边的数量大约是 0.49n 时，会发生一件神奇的事情。

Lex: 好的。

Don: 例如，如果 n 是一百万，我有 49 万条边，那么几乎所有情况下，它都由一些孤立的树组成，甚至没有任何环。

Lex: 到目前为止，边的数量还很少，略少于 n 的一半。

Don: 是的，但如果我有 0.51n 条边，稍微多于 n 的一半，例如一百万个点，51 万条边，那么它很可能有一个比其他所有分支都大得多的分支，我们称之为“巨分支”。

Lex: 这种随机图有什么名字吗？超级酷的 π 随机图？

Don: 我把我的 π 图建立在 π 的二进制表示上，而不是十进制表示上。

Lex: 所以，不一定要用 π？

Don: 重点是每一步都完全随机地选择一个点，再完全随机地选择另一个点，将它们连接起来。这就是这个过程。

Lex: 所以 π 并没有什么特别之处？

Don: 我用 π 只是为了说明 π 是某种随机的，没有人知道其中的规律。我也可以用抽签或其他方式。这是 Erdős 和 Rényi 发明的一个概念，他们称之为“随机图的演化”。如果你从一个很大的 n 开始，重复这个过程，在大约 n/2 的时候会发生一个“大爆炸”。一开始可能有两个点连在一起，然后可能有三个，然后它们可能会稍微分支，但它们都是 বিচ্ছিন্ন的，直到我们达到 n/2。当我们超过 n/2 时，突然间就会出现一个很大的连接在一起的团块。

Lex: 这就像某种相变？

Don: 完全正确，这是一个相变，但实际上这是一个双相变，在这个相变点上同时发生了两件事，这非常了不起。许多最重要的算法都基于随机过程，所以我想理解随机过程。有一些数据结构就是以这种方式增长的。Dick Karp 是随机算法领域的主要专家之一，他在伯克利让他的学生们研究这个问题。学生们正在生成或模拟这种随机图的演化，并定期拍摄快照，观察图的状态。我们听到一个传言，说学生们发现了一些有趣的现象，他们在每次观察时，几乎总是只有一个连通分支包含环。他们做了上百万次实验，只有三四次看到了不止一个包含环的分支。

Lex: 他们一直观察，直到图完全连通？

Don: 是的，图从完全空开始，不断地添加边。一开始肯定会出现一个环，但不知何故，所有的环都与那一个分支相连，从来没有两个分支都有环。

Lex: 在实验中？

Don: 是的，这几乎总是成立的，当然不是永远成立，但概率非常高。所以我们在斯坦福听说了这个传言，我们想，如果这是真的，那么一定还有更多的事情也是真的，一定有一个我们从未想过的完整理论有待发现。所以我们仔细研究了一下，发现事实并非如此，但实际上它几乎是正确的。也就是说，只有一个非常短的时间窗口内它是成立的，如果你在那段时间内没有观察，你就会错过它。换句话说，会有一段时间，有两个或三个分支有环，但它们很快就会合并。

Lex: 所以，如果你没有一个快门速度非常快的相机，你就会错过那个瞬间？

Don: 是的，独立的环不会存在很长时间。我开始研究这个问题，试图量化它。最基本的问题是减缓“大爆炸”的速度，这样我就可以观察它的发生。实际上，我可以用相当初等的方式来解释它，甚至不用写一个公式，就像霍金那样。我们观察这个演化过程，起初，这些边只是在构建没有环的结构，我们称之为树。然后，突然间，第一个环出现了，这时我有一个包含环的分支。现在，我定义一个分支的“复杂度”为边的数量减去顶点的数量。如果我有一个长度为 5 的环，它有 5 条边和 5 个顶点。或者我可以在这个环上加一个“尾巴”，那就是另一条边和另一个顶点。所以，如果复杂度为 0，我们就有一个环，我称之为“循环分支”。一个循环分支看起来像一个轮子，上面连接着一些树，没有其他的环，只有一个环，其他所有的东西都连接到这个环上。它的复杂度为 0。但一棵树本身的复杂度为 -1，因为例如，它可能有 10 个顶点和 9 条边，9 - 10 = -1。所以复杂度为 -1 的是一棵树。

Lex: 它必须是连通的，这就是我所说的“分支”的意思。

Don: 是的，如果我有 10 个东西连在一起，我必须有 9 条边。

Lex: 您能解释一下为什么当复杂度增加时，它可以大于 0 吗？我有点...

Don: 好的，复杂度加 1 就是环的数量。如果复杂度为 0，我就有一个环。如果复杂度为 1，这意味着我比顶点多一条边，例如，我可能有 11 条边和 10 个顶点，我们称之为“双环”，因为它有两个环，它必须有两个环。

Lex: 为什么它不能是连接到环上的树呢？

Don: 那样的话，我需要的边会比顶点更多。

Lex: 好的，明白了。

Don: 所以，每次我得到另一个环，我就会多一条边。换句话说，我们开始的时候，当我有一个环的时候，我就有一个包含环的分支。根据传言，下一步几乎在所有图的演化过程中，都会从一个环变成一个双环。但事实上，有一定的概率，它会从一个环变成两个独立的环。我计算了这个概率，大约是 5/24，这个概率相当高。

Lex: 是的，很大。

Don: 但很快它们就会合并。然后它会再次分裂，下一步你要么有三个环，要么有两个，一个，或者一个，一个，一个。我计算了这些转移的概率，我计算了前五个转移的概率，我得到了一些奇怪的数字，比如 5/24。我熬夜到凌晨三点左右，我把这些数字计算出来了，我看着它们，其中一个分母是 23023，所以概率是某个数除以 23023。

Lex: 我不知道您是怎么算出来的。

Don: 我有一个公式可以计算这个概率，我可以找到当 n 趋于无穷大时的极限概率，结果就是这个数。但我看着分母，我说，等等，这个数可以因式分解，因为 1001 等于 7 乘以 11 乘以 13，这是我在我的第一个计算机程序中学到的。所以 23023 是 7 乘以 11 乘以 13 乘以 23。这不是一个随机数，这些小素数出现在分母中一定有原因。这突然让我想到，可以用另一种方式来看待这个问题，这样就会出现小素数因子。

Lex: 那会是什么呢？

Don: 我想，哦，我应该取这个公式的对数，它肯定会简化。我确实这么做了。我本来不会注意到这一点，除了这个因式分解。然后我去睡觉了，我想，这看起来我正在减缓“大爆炸”的速度，我可以弄清楚这里发生了什么。第二天，碰巧比尔·盖茨来斯坦福访问，他们试图说服他为新的计算机科学大楼捐款。他们安排我和比尔谈话，我在黑板上写下了这个演化图，从一到一个，到两个，5/24，所有这些。

Lex: 这太有趣了。

Don: 那天结束时，他和发展办公室的人讨论，他说：“我对 Knuth 教授关于这个巨分支的讲解印象深刻。”

Lex: 哈哈。

Don: 我喜欢这个故事，因为它表明理论计算机科学确实是有价值的。

Lex: 您有没有和比尔·盖茨谈过这件事？

Don: 是的，这是一个很酷的小插曲。但他碰巧在我发现这个规律的第二天来访，这让我能够解决这个问题，进一步发展这个理论，理解“大爆炸”中发生了什么，因为我现在可以写出明确的公式了。它不仅适用于前几步，还可以研究整个过程。我和另外两位作者一起研究，我们最终计算出传言为真的概率。换句话说，观察一个随机图从零条边到完全连通的演化过程，在每一个时间点，都只有一个包含环的分支的概率是多少？我们从这个传言开始，说只有一个包含环的分支。

Lex: 所以传言的概率是 100%？

Don: 实际上，这个数字大概是百分之几，我应该记住这个数字，但我现在记不清了。但这个数字和 π 有关，我们本来不可能做到这一点。这是我一生中遇到的最难的问题，就是证明这个概率是...

Lex: 这个问题被证明了？

Don: 是的，我证明了这个概率，这应该有助于理解关于随机图的其他问题，这是我们被问到的主要问题。

Lex: 太酷了。您之前提到的与物理学的联系是什么？

Don: 玻色-爱因斯坦统计是研究分子如何在没有几何结构、没有距离的情况下结合在一起的。

十二、 开源

Lex: 您创建了 TeX 排版系统，并将其开源发布。您为什么将它开源？您对开源的愿景是什么？

Don: 那时还没有“开源”这个词。我不想要它的专有权，因为我看到专有权在 50 年代末是如何阻碍事物发展的。IBM 的人开发了 Fortran 语言，他们本可以将其据为己有，说只有 IBM 才能使用这种语言，但他们没有。他们说，任何能够将 Fortran 翻译成自己机器语言的人，都可以制作 Fortran 编译器。另一方面，在印刷行业，我看到很多用于排版页面的语言，每个制造商都有自己的语言，这阻碍了整个行业的发展，因为人们被束缚在特定的制造商身上，而一年后又发明了新的设备，但印刷机需要 20 到 30 年才能收回成本。

Lex: 所以您不希望 TeX 重蹈覆辙？

Don: 我不需要这笔收入，我已经有了一份好工作，我的书也卖得不错，足以支付我孩子教育等方面的费用。我没有理由去追求更多的收入。收入就像一个阈值函数，如果你没有足够的收入，你就会挨饿，但如果你超过了阈值，你就会开始考虑慈善事业，或者试图把钱带走。总之，我的收入超过了阈值，所以我不需要保留它。我可以预见到让它对所有人开放的好处。

Lex: 您认为大多数软件都应该是开源的吗？

Don: 我认为人们应该为非平凡的软件付费，而不是为平凡的软件付费。

Lex: 您举了 Adobe Photoshop 和 Linux 上的某个软件的例子，Photoshop 很有价值。

Don: 是的，为 Photoshop 付费是值得的，它不断添加一些我和我妻子并不关心的新功能，但总有人需要。他们还内置了一个非常棒的撤销功能，你可以执行一千个复杂的图形操作步骤，它可以带你回到那个序列中的任何一个点。

Lex: 这很有趣，我没有想过它用了什么算法，一定是一种高效的表示方法。

Don: 是的，里面有很多非常巧妙的、诺贝尔奖级别的知识产权。

Lex: 专利的有效期是有限的，专利的意义在于你将其公开，而不是作为商业机密。您说过您目前在一台独立的笔记本电脑上使用 Ubuntu Linux，它没有连接到互联网，您偶尔会在它和您用于网络浏览和图形处理的 Mac 电脑之间传输闪存驱动器，但您只信任 Linux 来保管您的“传家宝”。您为什么喜欢 Linux？

Don: 我使用的 Linux 版本非常稳定，我实际上迟早要升级到更新版本的 Ubuntu，但我现在运行的版本不支持很多新软件。

Lex: 最后一个稳定的版本...

Don: 我不记得版本号了，可能是 14，总之，它已经很老了。我准备买一台新电脑，用固态硬盘代替机械硬盘。

十三、 最喜欢的符号

Lex: 回到 TeX 的话题，在思考美丽的排版时，您最喜欢的字母、数字或符号是什么？我知道这是一个有点“无厘头”的问题，但有没有...

Don: 我给您看一样东西，您看索引的最后一页，这是什么？

Lex: 这是什么？

Don: Dr. Seuss 写过一本书叫《On Beyond Zebra》，他给这个符号起了个名字。

Lex: 您说 Dr. Seuss 给它起了个名字？Dr. Seuss？是 S-E-U-S-S？他写了很多儿童读物...

Lex: 您是说写《戴帽子的猫》的 Dr. Seuss 吗？

Don: 是的。

Lex: 我很惊讶您提到了他。《On Beyond Zebra》有没有传到苏联？

Don: 哈哈，Dr. Seuss 没有传到苏联。

Lex: 但后来应该有，我们小时候读过一些。

Don: 可能是《戴帽子的猫》或《绿鸡蛋和火腿》被用来学习英语。

Lex: 哦，可能是通过这种方式传进来的。

Don: 我小时候非常喜欢《Bartholomew Cubbins》，我都能背下来。我们现在看到的这个符号是什么？看起来很复杂。

Don: 他在《On Beyond Zebra》的结尾给它起了个名字。

Lex: 这是他创造的吗？

Don: 是的。看起来像一堆藤蔓。顺便说一句，他在 50 年代初拍过一部电影，我不记得电影的名字了，你可以在网上找到。电影里有很多钢琴同时演奏，但所有的场景都是基于他书中的那种艺术风格，非常奇幻。我只看过一两次，但我很想再看一遍。

Lex: 您在这里提到了他，这很有趣。有没有一些您特别喜欢的、简洁优雅的符号？

Don: π，我经常在需要随机数的例子中使用 π，因为它没有任何已知的规律。

Lex: 好的。

Don: 例如，我这里没有，但我可以给你看看。你知道 Masyu 谜题吗？M-A-S-Y-U？

Lex: 不知道。

Don: 这是一种很棒的消遣，数独更容易理解，但 Masyu 更容易上瘾。你在棋盘上放置黑色和白色的棋子，就像围棋一样，你必须画一条路径，这条路径必须直穿过白色棋子，并在黑色棋子处转直角。这是一个非常好的谜题，因为它不涉及数字，而是视觉上的，玩起来很愉快。我想把它作为《计算机程序设计艺术》中的一个例子，我写了一个关于如何设计出色的 Masyu 谜题的练习题，你可以在维基百科上找到，M-A-S-Y-U。我决定用 π 的图像，它由像素组成，我在 π 这个希腊字母的形状中放置棋子。但问题是，如何将一些棋子变成白色，一些棋子变成黑色，使得这个 Masyu 谜题只有一个解？这是对我的 Masyu 谜题设计算法的一个很好的测试，因为我要求棋子必须放置在构成 π 这个字母形状的位置上。

Lex: 好的，这很酷。

Don: 结果发现只有一种方法可以做到这一点。所以 π 是一个很好的例子来源，我可以证明我不是从一个固定的模式开始的。最近，我在写关于“优雅图”的内容。“优雅图”是这样的：你有一个包含 m 条边的图，你给每个顶点分配一个数字，分配方式如下：每条边连接两个顶点，你取这两个数字的差，这个差必须能够告诉你这条边是什么。所以，有一条边连接的两个数字相差 1，另一条边连接的两个数字相差 2，以此类推。这是一个很好的计算机问题：你能找到一个图的“优雅”标记方法吗？我从一个有机的图开始，而不是一个数学上对称的图。我用了美国 49 个州，边从一个州到另一个州，例如，加利福尼亚州与俄勒冈州、内华达州和亚利桑那州接壤。我还包括了哥伦比亚特区，所以我总共有 49 个，我不能把阿拉斯加州和夏威夷州包括在内，因为它们不接壤，你必须能够从一个州开车到另一个州。那么，是否存在一种美国各州的“优雅”标记方法，每个州都有一个数字，如果加利福尼亚州是 30，俄勒冈州是 11，那么这条边的编号就是 19，是这两个数字的差。对所有州来说，是否存在一种方法可以做到这一点？我当时正在考虑举办一场竞赛，让人们尽可能地找到最“优雅”的标记方法。但我的朋友 Tamara Kiki 实际上解决了这个问题，他证明了... 或者更准确地说，我之前找到了一种标记方法，使得所有边的编号都在 1 到 117 之间，但其中有一些空缺，因为实际上应该从 1 到 105 或某个数字。我给了自己太多的空间，他没有留任何空缺就完成了，这是一个完美的“优雅”标记。所以我取消了竞赛，因为这个问题已经被解决了，从某种意义上说，它太简单了，因为 Tom 在一个下午就解决了。

Lex: 他是为美国这个特定的例子设计的算法吗？

Don: 是的，为美国。这个问题通常来说非常难，类似于着色问题，但我们很幸运，它对美国有效。我认为这个理论还很不完善。但几天后，Tom 不仅找到了一个“优雅”标记，而且华盛顿州的标记是 31，爱达荷州的标记是 41，按照 π 的数字排列。

Lex: 他是有意这样做的吗？

Don: 他仍然能够得到一个“优雅”标记，这太不可思议了。但我喜欢在我的书中使用 π，你看，条条大路通 π，它经常隐藏在最难的问题中。

十四、 效率

Lex: 我想问您关于效率的问题。您说过：“我的日程安排原则是在一周结束前完成我最讨厌的任务，到周末我就会非常高兴。” 您能解释一下这个提高效率的方法吗？

Don: 哦，我一直在权衡我想做什么和不想做什么，但我很高兴完成了所有那些不愉快的任务。

Lex: 您会建议其他人也这样做吗？

Don: 我不知道该怎么说。在疫情期间，我觉得我的效率实际上降低了一半，因为我必须通过写作来进行沟通，这很慢。我不喜欢发送一个糟糕的句子，所以我会反复阅读和修改我写的内容，所以所有的事情都需要更长的时间，当我通过文字信息进行沟通时，而不是和某人面对面交流。而且图书馆关闭了，这也让事情变慢了。关于日程安排，我从我母亲那里学到了另一件事，这与机器 人领域所说的“规划”不同。她的原则是：看到需要做的事情就去做。

Lex: 好的。

Don: 而不是说我要先做这个，再做那个，就是去做。

Lex: 在任何一个时刻，都有一系列您可以做的任务，您是说一个好的策略是去做您最不想做的那个？

Don: 是的，我没有充分的理由认为我以后会做得比现在更好。有些事情，我知道如果我先做其他事情，我就能把这件事做得更好。但有些事情会变得更难，因为我忘记了一些基础工作或者其他类似的事情。所以我刚刚完成了书中一个相当难的部分，现在我在做一些更有趣的部分。但另一方面，我在写书的时候，当然希望读者认为我一直都很开心，我保持乐观，我可以幽默，我可以说“这很酷”，我必须掩盖这个过程中的任何痛苦。

Lex: 通往兴奋的道路是痛苦的。

Don: 是的，充满了痛苦。

十五、 人生意义

Lex: 您以前给过人们一些建议，您能不能... 我给了您太多的赞誉，但这是我的...

Don: 我只是想说出我的想法，但我首先要说，我也相信其他人在很多方面都做得比我好得多，我只能告诉你我这方面的情况。

Lex: 我想请您给年轻人一些建议，给高中生、大学生，无论是“极客”还是其他人，关于如何过上让自己自豪的生活，如何拥有成功的事业，如何拥有成功的人生。

Don: 就像我以前说过的，不要因为某件事很时髦就去做，而是要做你个人觉得是你的使命的事情，而不是别人期望你做的事情。

Lex: 你怎么知道这是你的使命呢？

Don: 你去尝试，然后发现它可行，或者不可行。你会了解你自己，人生就像一个二分搜索，你尝试一些事情，然后发现，哦，我有这方面的背景，或者我再努力一点就能做到。但你也可能尝试了其他事情，然后发现，我真的没有这方面的直觉，这看起来不像是我的使命。

Lex: 一路上有没有人给过您关于您应该做什么和不应该做什么的建议？还是说您只是听从自己的内心？

Don: 我可能有点反应过度，当我看到其他人都在做某件事的时候，我可能会说，不要做太多。

Lex: 避免竞争？

Don: 是的，但我主要是做一些我觉得有趣的事情，后来我发现，哦，实际上我学到的最重要的事情是如何对几乎所有事情都感兴趣，而不是感到无聊。当我看到孩子们互相说“那很无聊”时，我会感到非常难过。一个人应该感到不安，如果他不得不承认他无法找到有趣的事情。

Lex: 所以...

Don: 他们说我还没有学会如何享受生活，我需要别人来娱乐我。

Lex: 这很有趣，这确实是一种技能。我很喜欢 David Foster Wallace 关于这个问题的说法，他说生活的关键在于“不无聊 (unborable)”。我真的很喜欢您说的这是一项技能，因为我认为这是一个非常好的建议。如果您觉得某件事很无聊，我不认为是因为它本身无聊，而是因为您还没有学会如何发现其中的美和乐趣。

Don: 是的，这是一个非常好的观点。有时候做到这一点比其他时候更难，但在疫情期间，有很多天我都没有见到其他人，但我仍然找到了其他的方式...

Lex: 仍然很有趣？

Don: 是的，仍然很有趣。我今天来早了几分钟，我在福斯特城 (Foster City) ঘুরে了一圈，我不知道这里有什么，我在几个街区外的 Home Depot 苗圃看到了一些漂亮的花。

Lex: 生活是美好的，生活中充满了像这样美好的事物。

Don: 是的，有时候我会坐在那里，盯着一棵树看。大自然很美。

Lex: 我想问您一个很大的、“无厘头”的问题，我不记得上次有没有问过您，这次我必须问一下，也许您有一个好的答案：生命的意义是什么？

Don: 哈哈。

Lex: 我们在这个地球上的存在，这一切的意义是什么？

Don: 哈哈哈哈。

Lex: 不，不，您不能逃避这个问题，您必须给出一个明确的答案，因为，当然，Don Knuth 一定知道答案。答案是什么？是 42 吗？

Don: 我不认为是数字。

Lex: 好的。

Don: 好吧，这只是我个人的看法，我相信上帝的存在，尽管我不知道那意味着什么，但我相信有一些东西超越了人类的能力。

Lex: 好的。

Don: 它可能是某种人工智能，但无论是什么，我相信有一些东西超越了人类理解的范畴，但我可以尝试更多地了解如何与那个“存在”产生共鸣，做它希望我做的事情。

Lex: 您认为您偶尔能瞥见那个“存在”吗？

Don: 我努力这样做，但我并不认为我能接近它。但这不是为了我自己，而是说我应该做什么那个“存在”希望我做的事情。这就是... 我试图去理解那个...

Lex: 那个“存在”希望您现在和我交谈吗？

Don: 是的，我就是这么认为的。

Lex: 谢谢您。

Don: 不客气。我想说的是，我并不是试图在所有可能的策略中选择一个，我试图想象我在遵循某个“存在”的意愿，尽管我不够聪明，不知道它是什么。

Lex: 但那个有趣的“小舞蹈”...

Don: 我的意思是，这个人工智能或者其他什么，它可能足够聪明，可以给我一些线索，让整个旅程充满乐趣。就像很多人说过的，重要的是旅程，而不是目的地。人们经历了危机，互相帮助，所有这些事情都会发生。历史总是在重复，你会试图说，在当今世界，有哪个政府是有效的吗？我读历史，我知道过去的情况在很多方面更糟糕，有很多不好的事情一直在发生。我阅读历史，观察事物，人们有好的想法，他们在做伟大的项目，但我知道它最终并没有成功。我最近读到的一本书给了我一个新的见解，是 Ken Follett 的《来自圣彼得堡的人》(The Man from St. Petersburg)，它讲述了第一次世界大战的前传。根据这本书，温斯顿·丘吉尔发现德国一直在耗尽其黄金储备，建立一支庞大的军队，毫无疑问，如果德国进攻英国，英国将被消灭。所以他希望俄国从另一边进攻德国，因为德国没有足够的军队来同时打两场战争。然后，俄国有一个无政府主义者，他认为战争是领导人发动的，但实际上是人民在送死，所以他想阻止英国和俄国结盟，因为那将意味着成千上万的俄国人会死去，否则他们不会死。所以他的人生目标是刺杀一位访问英国的俄国王子，因为那将意味着沙皇不会结盟。所以我们面临着一个关于政府应该做什么的问题，它是否应该做一些会导致... 战争是不可避免的吗？还是有办法实现和平？这让我意识到，如果我处于一个对人们的生命负责的职位上，在大多数情况下，我不会相信我的任何决定是好的，这些问题对任何人来说都太难了，当然对我来说也是如此。

Lex: 我认为，不确定决策是否正确，这是一个非常好的品质，再加上你必须做出决定并承担责任，最终，我对人类和伟大的领导者抱有信心，他们会挺身而出，帮助建设一个更美好的世界。这就是民主的希望。

Don: 用算法增强他们的能力。

Lex: 哈哈，说得好，Don。这真是一个巨大的荣誉，您一直是我的榜样，也是数百万人的榜样。感谢您再次抽出宝贵的时间和我交谈，这是一个巨大的荣誉，我真的很喜欢这次谈话。感谢大家收听 Don Knuth 的这次谈话，为了支持这个播客，请查看我们在描述中的赞助商。现在，让我用 Don Knuth 的一句话来结束：科学是我们能够向计算机解释清楚的东西，艺术则是我们所做的其他一切。感谢您的收听，希望下次再见。

内容要点

一、 引言 (0:00)

二、 早期的编程经历 (0:48)

三、 编程风格与程序之美 (21:15)

四、 OpenAI 与自动化 (33:15)

五、 优化 (42:26)

六、 意识 (48:31)

七、 康威的生命游戏 (57:14)

八、 稳定婚姻问题 (1:10:01)

九、 理查德·费曼 (1:13:21)

十、 Knuth-Morris-Pratt 算法 (1:24:15)

十一、 最难的问题 (1:33:47)

十二、 开源 (1:51:26)

十三、 最喜欢的符号 (1:56:39)

十四、 效率 (2:06:12)

十五、 人生意义 (2:13:53)

十六、 结语 (2:20:52)