Scott Aaronson - 量子计算、复杂性与创造力
Scott Aaronson - Quantum Computing, Complexity, and Creativity
全文文稿 · 按对话顺序保留完整内容，深入理解上下文。
§01文稿 - 00:00
要成为整个领域的专家，可能需要好几年甚至几十年，而你离那一步可能还很远；但要成为某一个特定的小问题上的世界级专家，其实并不需要多久。所以，试着在某件事上成为世界级专家吧，哪怕是非常非常窄的一件事。
Aaronson 教授，能跟我们讲讲您早年的经历吗？您是个少年天才，15 岁就高中毕业，22 岁拿到博士学位。能说说这段经历吗？嗯，其实我 15 岁时并没有真正从高中毕业。我拿的是纽约州的 GED（同等学力证书）。当时我在高中过得不开心，有好几个原因，比如在社交上，
在学业上，我都想离开那里。我的处境有点奇怪：我在美国上的是公立学校，读初中，其实是在宾夕法尼亚州，后来我父母搬去了香港，我在香港住了一年，
因为我爸爸在那里工作。我在那边上的是一所美国国际学校，但由于美国和香港两边教学安排不一致，我没法学到合适程度的数学。我一直算是数学上比较超前的，而解决办法只能是让我跳一级，
然后直接去读高中。这件事一做完，我心里好像有什么东西翻转了：我真的可以做到这种事，我可以离开这样的环境。我真正想去的地方是大学。我想待在这样一个地方，当然，我对
大学的看法多少有些理想化，但那是一个思想比受欢迎程度更重要的地方，你可以自己选择学什么、按自己的节奏前进，还有所有这些美好的东西。于是我从香港回到美国，在公立高中读了一年。
就像我说的，我不喜欢那里。然后我把能修的数学课都修完了，我上过 AP 微积分。于是我父母基本上向学校提议：那为什么不让他在线学习呢，比如学微分方程之类的，
斯坦福有个叫 EPGY 的项目，可以让你学这些东西。我父母说他们愿意出这笔钱，学校却说不行。于是我就把这当成了借口。我好像刚好看到一本宣传册，介绍纽约州北部一个叫 Clarkson School 的地方，它隶属于 Clarkson 大学，
你可以在那里住一年，修大学课程，不过它是面向高中生的。于是我说，虽然我对这个几乎一无所知，但我想试一试，我父母也同意让我去。我们把车都装好了，准备开车过去，就在我们
即将出发的时候，我原来高中里有一位非常优秀的数学老师，他一直在为我争取，他说：好了，你猜怎么着，我刚刚帮 Scott 争取到了可以上 EPGY 项目的名额。我们说：太晚了，抱歉。于是我去了 Clarkson，总体上我在那里的体验很好，
我的意思是，社交方面存在很多和高中一样的问题，但至少我能修有趣得多的课程，能接触教授，并开始做研究。这个项目的设想是，在 Clarkson 项目读完一年之后，你
再以新生的身份申请大学，但手里已经有一年的大学学分。我就这么做了。当时的结果让我非常失望，因为我申请的大学几乎都拒绝了我，我的背景很奇怪。不过我很幸运，Cornell 和 Carnegie Mellon 好心地录取了我，于是我决定去 Cornell。
但随后出现了一个问题：他们要求入学前必须有高中毕业证书，而我没有。所以我们发现我需要一张 GED。通常，原来的高中在你去过 Clarkson 之后，会直接给你发一张毕业证书，但我的高中不肯，他们说我缺体育课学分，我得花一个暑假去补体育课。
于是纽约州说：我们不能给他发 GED，因为拿 GED 必须年满 17 岁，而他才 15 岁。最后我妈妈说服了他们破例，给了我一张 GED。就这样我去了 Cornell。我还遇到过一些在家上学的人，他们做的事比我做的更激进。我是提前了三年，
仅此而已。进了大学之后，我就没有再继续提前了，因为我觉得自己已经待在想待的环境里了，从那以后，主要的限制都来自内部，不再是外部的了。和比您大三四岁的人一起上课，会让您感到有压力吗？实话说，我想大多数人甚至不知道我比他们小。就算知道，
大概也只是觉得有点稀奇，但他们并不太在意。毕竟我又不是十岁的小孩，我入学 Cornell 的时候已经 16 岁了。所以我觉得在学业上没有问题，主要的问题
是社交上的。我父母曾经警告过我：跳级会彻底毁掉你的社交生活，会让约会变得极其困难，等等等等。我当时把这些全都抛在了一边。当然，这些后来都应验了。我拿到了
博士学位，而那时我基本上还没学会开车，也还没学会拥有任何像样的社交生活，或者说任何像样的约会生活。所以我做事的顺序有点怪，可以这么说，这确实给我带来了巨大的压力。但我当时的主要论点是，我在高中时就已经在社交上不快乐了，
我那时就已经很痛苦了，哪怕没有跳级也是如此。所以我觉得，既然反正在社交上都会痛苦，至少当时看起来是这样，那我至少可以学到东西，至少学业上会更好一些。是的。就学业而言，这么早就专精于某个方向，有哪些好处和坏处？嗯，我没法把我的
人生重来几遍再做比较，但我觉得，最主要的是我很感激自己有机会去学自己感兴趣的东西。而且并不是说我只想学数学和计算机科学，别的什么都不学，不是那样的。我在
§02文稿 - 00:10
大学里也修了很多人文课程。但我想要有一定的自由，自己选择要学什么。你看，在高中，人文课就意味着五段式作文，意味着你基本上必须复述老师想要你说的东西，而如果你
试着按自己的方式去写，你反而会不及格。这是我的亲身经历，不是什么理论。所以，就连人文学科，我在大学里也比在高中时快乐得多。所以这不只是专精化的问题，不过在一定程度上确实是。我想到了
16 岁左右的时候，我已经知道自己的热情所在：计算的基本原理，也就是理解计算机能做什么、不能做什么。我已经准备好去学习它、研究它。我认为，整个“青少年期”的概念，也就是说从 12 岁到
18 岁，或者现在甚至到 20 岁左右，我们仍然基本上被当作孩子，我觉得这在很大程度上是现代才有的建构。如果回到几百年前，一个人到了十几岁，就已经是学徒了，他们可以一边工作一边学习，可以学习自己所选择的行当。所以我认为，那其实
是很自然的。我不觉得自己在这方面有多特别，在某些方面也许不同寻常，但在想要从 15 或 16 岁就开始投入生活这一点上并不特别。是的，我在播客里请过 Tyler Cowen，他基本上在十几岁出头就知道自己想当经济学教授，并且从那时起就一直为此阅读和准备。经济学教授通常不是人们会想到的那种孩子或青少年所立志成为的职业，
但就 Tyler Cowen 的情况而言，我完全可以相信。早早学习自己将要进入的那个领域的基础知识，除了多了几年来积累知识之外，在童年早期学习它是否还有某种特殊的优势？我不确定。是的，这是个非常有意思的问题。可以设想，在一个人的大脑还在发育的时候，接触某些东西是有好处的。
我们确实知道类似的例子，一个明显的例子就是学习语言：有一个时间窗口，孩子可以像海绵一样吸收语言，过了这个窗口，当然你还是可以学一门语言，但那会是一个艰难的智力难题，而且你永远不可能说得
像土生土长的五岁孩子那样好。所以它可能是这样；但也可能是，我们的大脑根本就不是为学习这些东西而适应的。比如说，当我们学到理论物理、理论计算机科学等等的时候，这一切都
像是在学一门我们并非天生就会说的语言。按这种模型，那就只是看你能为此花多少时间，谁先起步谁占便宜。我很希望有人去研究这个问题，因为我不知道答案。我听说过，嗯，您也知道，量子力学中的许多重要发现都是由当时非常年轻的人做出的，这是个有趣的事实：不仅他们很早就学了那些东西，而且很早就做出了那些贡献。
是的，但这不只是量子力学，数学和物理学里到处都是这样。比如牛顿大约 22 岁的时候迎来了他的“奇迹年”，发明了微积分，发现了力学定律。嗯，我是说，按那个标准，我已经老了，
想想这一点挺奇怪的。不过也有许多伟大贡献是由四五十岁、六十多岁的人做出的。所以这是另一个我很好奇的经验性问题：是人的大脑随着年龄增长真的会变慢，还是仅仅因为他们动力变少了，或者空闲
时间变少了？就我自己来说，有了两个孩子，显然让我做研究的时间大大减少了。而在有些情况下，比如我出差、离开孩子一个星期的时候，我又能工作了，突然间感觉和我二十多岁时非常像。
嗯，是的，然后还有动力的问题。在我成名之前，我对自己的整个认知、我对人生的所有目标，都与在研究上取得成功绑在一起，为此我愿意不惜一切代价；而现在，我有各种其他的牵挂，
我还要顾及自己的学生、我的博士后，当然还有我的孩子、我的博客、我写的那些科普文章，而研究只是我做的又一件事而已，我的身份认同不再那么紧紧系在它上面。所以我也可能变笨了，这当然有可能，只是很难把它和那些其他因素分开。是的，您是第三个，我
保证我们最终会谈到技术问题，但您是我在播客上要问这个问题的第三个人，因为它让我着迷：奇迹年。正如您提到的，不只是人们在年轻时做出了非常重要的发现，而且他们在年轻时做出了许多看似不相关的重要发现。比如爱因斯坦做了布朗运动、狭义相对论，还有第三个是什么？应该有三个，嗯，还有光电效应。对，没错。这几项至少表面上看起来互不相关，却恰好发生在同一年，您认为是什么解释了这种现象？
就爱因斯坦的情况而言……您是要我来解释爱因斯坦的奇迹年，这可真是个高难度的要求。我们可以说一些事情，比如可以说，20 世纪初的物理学已经成熟到足以出现
这些相互关联的革命，也就是相对论和量子力学。如果不是爱因斯坦，不久之后也会有别人做出这些。唯独广义相对论，爱因斯坦又花了十年，这是唯一一件如果没有爱因斯坦，我们很可能要再等几十年才会有人做出来的事。但是，他在
1905 年做的那些东西，都是物理学当时已经成熟、等着被人发现的，也许只是需要一个人以足够不同的方式去看待事物。我并不真的确定。不过也可能是，所有这些成果汇聚在一起，正是我们把爱因斯坦视为爱因斯坦的部分原因。同一时期还有
许多其他伟大的物理学家，他们或许也做出了一两项那种分量的成就，但只有爱因斯坦一个人做出了那三四项。我很高兴您提到了想法已经“在空气中”、等着被摘取这个话题，因为这直接引出了我的下一个问题。我重读了您量子信息科学课程的讲义，其中有一讲是关于量子隐形传态的，您在回答
人们是怎么想出这类东西的，您说值得指出的是，量子力学是在 1926 年被发现的，而量子隐形传态直到 90 年代才被发现，还有量子计算，我很欣赏 David Deutsch，他是在 80 年代发现或者说想到它的。这些想法似乎在量子力学刚发展出来时就已经可以摘取了，为什么过了这么久才被人摘取？是的，这是一个极其有趣的问题。
§03文稿 - 00:20
我的意思是，思考量子纠缠这整个想法，不是把它看作形而上学上古怪的或者说“鬼魅般”的东西，不是想怎么把它解释掉、怎么摆脱它，而是想怎么利用它，怎么用它来改进信息处理，
据我所知，这种观点真正开始于 20 世纪 60 年代的 John Bell。Bell 有一个了不起的洞见：可以做一个实验来检验纠缠的预言，并把它与任何涉及局域隐变量的可能理论区分开来。然后
稍晚一点，Stephen Wiesner 提出了量子货币的想法，也就是把不确定性原理用于密码学，不过他同样直到 80 年代才得以发表。在这里我可以说几点：第一点是，当量子力学在 20 年代被发现时，发现它的那些人完全不清楚
这是否就是物理定律最终会采取的形式。他们认为……有一大批人认为，这是一个代表我们当前知识的方案，但显然必须对它加以改进。这很大程度上就是爱因斯坦的观点，
我想也是薛定谔的观点。而 Bohr 和 Heisenberg 则坚决反对去寻找超越量子力学的东西，但他们并不是以一种激励人们进一步研究量子力学能做什么的方式来反对的，
他们只是希望所有人闭嘴，别再问这些问题了。所以你可以说，尽管在局域隐变量的问题上 Bohr 是对的、爱因斯坦是错的，但在更深的意义上，爱因斯坦才是更正确的那个，他指出了这里有某种我们尚未理解、而且需要理解的东西。确实，抱歉，确实，那
东西直到 60 年代发现 Bell 不等式之后才真正被理解。另一个问题是，当量子力学在 30 年代被发现时，有太多事情要做，比如弄清化学是如何运作的，也就是把量子力学应用于理解我们周围的真实世界。你可以说
另一方面，在计算机科学里，天哪，通用计算机的整个概念当时才刚刚诞生，整个经典计算领域才刚刚诞生。所以双方手头要做的事情都太多了，对任何人来说，把两者结合起来可能都显得极其过早。然后当然是第二次世界大战
介入了，做基础科学的人中，有很多去了曼哈顿计划或 Bletchley Park 工作。再往后，我认为理论物理学家都专注于不断发现的那一大堆新粒子，以及构建量子场论。在接下来的几十年里，去思考量子力学本身的基础问题，是非常
不合潮流的。与此同时，人们终于开始建造、商业化经典计算机，并摸索它们的用途，那本身也是一个非常年轻的领域。而整个计算复杂性理论，也就是量子计算在智识上的一个先决条件，
到 20 世纪 60 年代才发展起来，然后 P 与 NP 以及 NP 完全性的理论，是到 70 年代才出现的。所以如果我们想想有哪些人本来可以把这些领域结合起来，我会想到 John von Neumann，这是个显而易见的可能人选，因为他当然是计算机
科学和量子力学两方面的伟大先驱之一。实际上，他发明了量子态熵的概念。但他手头还有很多别的事，而且他英年早逝，50 年代就去世了。还有 Alan Turing，当然也是计算机科学的奠基人，他同样对量子力学的基础充满热情，
从他写给朋友的信中我们可以看到这一点。他去世时才 42 岁。所以不管怎样，我觉得量子力学和计算理论在 20 世纪 30 年代就都已就位，但人们手头还有许多别的事情；把纠缠看作一种资源的想法，要到 60 年代才开始，
计算复杂性要到 60 年代和 70 年代才开始，然后大约再过十年，人们才开始思考量子计算。有意思。我还听过另外两种理论，想看看您怎么看。第一种，我可能引述得不准确，但我想 David Deutsch 在某个时候说过，他之所以能认真思考量子计算，是因为他认真对待多世界诠释，而在他之前的人没有认真对待多世界，所以没能做出贡献。抱歉，您请说，您说。
好的，也许我可以回应一下这个，好。对 Deutsch 来说，这绝对是真的，我对 Deutsch 相当了解。他实际上是在这里，也就是 UT Austin，作为学生时成为多世界诠释的坚定信徒的，他听过 Hugh Everett 本人讲这个。Bryce DeWitt 是
多世界诠释早期的主要支持者之一，当时也在 UT Austin，对 Deutsch 影响很大。Deutsch 当时在思考怎样才能让人们警醒，怎样才能让他们意识到量子力学是普遍有效的，适用于所有尺度。如果你能造出一台计算机，它可以对不同的计算做叠加，
然后你能看到它们之间干涉的结果，那么在概念上，这几乎就像对一个能思考不同想法的大脑做叠加。如果能做到这一点，那么观察者仅仅因为是观察者就能让波函数坍缩这种想法，就不再那么站得住脚了。不过有个问题，Richard Feynman
几乎与 Deutsch 同时有了量子计算的想法。Feynman 当然知道多世界诠释，也知道 Everett，但那不是他思考量子计算的动机。他和往常一样，要实际得多，他在想怎样用计算机模拟物理，怎样模拟自然，而如果用经典计算机，我们就会遭遇
指数级的减速。所以能不能造出一种新型计算机来解决这个问题，给我们一台通用量子模拟器？当时在 70 年代和 80 年代还有一整个思潮，在思考计算的物理学，包括计算的热力学，能不能让计算本质上可逆，
以及各种其他问题，这些问题与指数级加速无关，但它也是直接通向量子计算的思想脉络之一。所以我认为您说的对 Deutsch 来说非常正确，但除了 Deutsch 之外，还有别人也在思考这些事情。Feynman 只是其中之一，还有其他人，我想有 Benioff，还有好几位。而且，这个领域里很少有人像 Deutsch 对多世界诠释那样
§04文稿 - 00:30
带有近乎布道般的狂热。有意思的是，仔细想想，Deutsch 和 Turing 在提出各自的计算模型时，至少部分上都是在试图解决另一个哲学问题。好，我听到的第二种理论是，自 20 世纪 70 年代以来，学术界对新想法越来越不开放，
您提到了 Wiesner 和 Everett，据我所知他们俩都受到了某种轻视或排挤之类的待遇。这个理论得到证实了吗？我认为，在学术界的某些部分，探索新想法确实可能变得比以前更难。我
能相信社会科学是这样，也能相信医学的某些部分是这样。过去人们会做一些完全疯狂的事，比如发明一种新配方，往自己身上注射，看会发生什么，然后写一篇文章。而今天，可能需要十亿美元的投资，才能走到任何人会认为做这种事至少还说得过去、合乎伦理的地步。另一方面，
在物理学领域，比如关于计算基础、宇宙学之类的思辨，我认为情况如果说有什么变化的话，反而是朝相反的方向发展的。这在一定程度上
是因为我们现在有了预印本服务器，也就是 arXiv，每个人都可以不经任何过滤地把自己所有的新研究想法发上去。我认为这在某种程度上改变了科学的格局。我们当然还有期刊，但期刊现在更像是最后的认可印章，
在许多领域，这在找工作之类的时候是重要的，但期刊已经不再是能阻止别人看到你论文的守门人了。所以，如果你每天看一看量子物理的 arXiv，你会看到那么多天马行空的想法，疯狂的东西多得很，所以很难
相信今天的 Wiesner 或 Everett 会觉得把自己的想法公之于众有什么障碍。今天的问题更多在于有太多大胆的新想法，当然其中大多数不会有结果，大多数都会失败，所以如果你想找出真正会带来革命的东西，需要筛选的东西实在太多了。
我相信您的评论区和邮箱里塞满了这类东西，那么，这个领域里的重要想法，有多少来自学术界之外的人？还是说大多是体制内拿了博士学位的人做出来的？嗯，这两类并不是穷尽的类别，因为确实有一些突破来自不在学术界的人。
你经常发现，这些人是处在学术界边缘的人，比如他们拿了博士学位之后离开了学术界，或者只读了一部分博士，诸如此类。有一个著名的例子是张益唐（Yitang Zhang），他是来自中国的数学家，证明了存在无穷多对相差不超过 7000 万的素数，
这是数论中的重大进展。这个人在中国拿到了数学博士学位，我想是的，但后来搬到了美国，为了养家做过做三明治的工作，还做过各种其他零工，但
他一直在继续研究数学。所以，我经常收到来自一些完全是自学者的人的来信，他们觉得自己解决了 P 对 NP 问题或者别的什么。这种情况通常是
那个人根本没有理解问题本身，只是做了一些……（音乐）不过这里也有区别：有时候，自学一个领域的人，他们真的很想学，只是想找个专家聊聊，让专家告诉他们哪里方向对了、哪里犯了错，而他们会为此感谢你。
另一些时候，你会遇到真正死不松口的人，说“体制在审查我”。我在 MIT 任教的时候，有人给 MIT 的校长写信想让我被开除，还有一个人给我发死亡威胁，写得非常具体，我不得不为此联系警察，因为我不肯在我的博客上发表
他们对 P=NP 的证明，或者对量子计算的驳斥。所以各种各样的人都有。另外你还会发现，我博客的很多读者是在大学里学过技术学科的人，学过计算机科学、数学或物理，
然后进入了工业界，但仍然保持着这种联系，保持着对基本问题的好奇心。其中有些人确实想继续做研究，我现在就在和其中一位合写一篇论文。我最近在博客上发了一篇关于 Busy Beaver 函数的综述文章，然后有一位，
我想是业余爱好者，解决了其中一些未解问题，那本来就是一篇综述，他提出了很多新想法，现在他和我打算就此写一篇论文。哦，真酷，有意思。顺便问一下，这位是不是和合著 Nielsen 量子信息教科书的是同一个人？不不不不，Yitang Zhang 是一回事，他是数学家，而 Isaac Chuang 是物理学家，是合著 Nielsen
那本教科书的人。好的，请继续，是我弄错了。那我来问问 Busy Beaver。我在想，命题三是说……我对命题的编号完全没有记忆，所以，您能不能先解释一下 Busy Beaver 函数是什么，然后我再问？好的，当然。Busy Beaver 函数是一个非常非常了不起的、增长得极其迅速的整数序列，我们定义它的方式是
它是 1962 年由一位名叫 Tibor Radó 的数学家发明的。基本上我们是这样做的：我先从我们想说什么开始。如果我想说出我能想到去定义的最大的数，那为什么不直接说
“能用一千个词或更少的词命名的最大的数”，或类似的话呢？但我得小心，因为这里有一个内在的悖论：我也可以说“比能用一千个词或更少的词命名的最大的数多一的数”，但那样我刚才就是用不到一千个词命名了它。所以由此，
一百多年前逻辑学家和哲学家得出的结论是，用英语命名一个数的概念并不像我们想象的那样清晰，如果你不小心，就会导致悖论。但是，如果我们能用完全无歧义的方式来命名一个数呢？自 20 世纪 30 年代 Alan Turing 以来，我们就有了这样一种方式，
§05文稿 - 00:40
那就是计算机程序，或者说图灵机。所以我们可以说：想一想长度至多为，比如说，一千位的计算机程序所能生成的最大整数。现在你得小心，这到底是什么意思，因为计算机程序当然可能永远运行下去。我们很容易写出一个程序，说“做：打印 9，循环”，
它就会打印出无穷无尽的 9。所以我们要做的是，只考虑那些最终会停机的程序。比如对于给定的 n，我们考虑所有 n 位的可能计算机程序，它们至多有 2 的 n 次方个。许多字符串得到的东西甚至根本不是
程序，连编译都编译不过，所以我们把它们扔掉。在所有有效的 n 位程序当中，有一些会永远运行下去（我们在空白输入上运行它们），所以我们也把这些扔掉，只考虑最终会停机的。然后在所有会停机的程序当中，我们取运行步数最多的那一个，也就是停机之前步数最大的那个，而这个步数就是我们
所称的第 n 个 Busy Beaver 数。Rado 当时定义它用的是图灵机，这只是一种特定的编程语言，是 Alan Turing 在 20 世纪 30 年代发明的那种。他说，n 的 Busy Beaver 数就是任何 n 状态图灵机在停机前所能运行的最大有限步数。这个……
令人惊叹的是，可以证明这个函数比任何可计算函数增长得都快。所以，无论是什么整数序列……如果你在参加一场报最大数的比赛，而你说“一千的 Busy Beaver 数”，那你就会彻底击溃任何
不知道 Busy Beaver 函数或任何类似东西的对手。关于这个函数，还可以说其他一些了不起的事，比如，从集合论公理出发，实际上只能证明这个函数有限个值，基本上是由于哥德尔不完备定理的缘故：过了某个有限的点之后，这个函数的值，
我们大概可以认为它有确定的值，因为它是一个定义清晰的函数，然而我们却再也无法证明它们是多少了。目前，如果按 Rado 在 60 年代定义的 Busy Beaver 函数来看，只有四个值是已知的：n 为 1 时是 1，n 为 2 时是 6，n 为 3 时是 21，n 为 4 时是
107。n 为 5 时，只知道它至少是 4700 万，我们不知道它可能还要大多少。n 为 6 时，它至少约为 10 的 36000 次方，也可能大得多。n 为 7 时，它至少是 10 的 10 的 10 的 10 的 1800 万次方，而且可能还要大得多。这只是为了让大家对
这个函数的增长速度有个概念。是的，顺便说一下，我建议所有正在听的人去看看 Busy Beaver Frontier 那篇论文，我还想问您是怎么学会写得这么好的，它写得让像我这样的非专业人士也能看懂。另外澄清一下我自己的理解：并不是存在某个函数对任意 n 都大于 Busy Beaver(n)，而是说，它最终会在状态数更多的时候……
（原文此处语句不完整）它会增长，这正是我说“增长得更快”的意思。对，没错，Busy Beaver 函数的每一个具体取值只是某个正整数，是非常具体的东西，比如是 6，或者是 21。但如果你看这些整数的增长速度，它最终会超过任何可计算函数，而且在实践中不只是最终，而是非常非常快就会超过。是的，
而且您在论文里非常优雅地表明，这意味着你可以独立地证明停机问题，还有哥德尔不完备定理。是的，停机问题的不可解性、哥德尔定理，这些东西彼此紧密交织，有很多很多不同的方法可以证明它们，而 Busy Beaver 函数给出了其中一种方法：你可以
用它独立地证明存在不可计算函数，也可以用它证明哥德尔不完备定理。好，那我的问题，命题三说的是，对于任何公理化理论，你都无法用它证明所有的 Busy Beaver 值。所以我的问题是，虽然没有系统化的办法来扩展我们的集合论，但有没有可能存在某种办法，让你可以不断扩展它，从而能证明
越来越大的 Busy Beaver 值？这是个很好的问题。我想说，我们目前还真不知道，因为现在我们连 Busy Beaver(5) 都还确定不了。我的猜测是，现有集合论的资源完全足够做到这一点，但我们连这一点都不知道。
四年前，我和我的一个学生 Adam Yedidia 决定研究一个不知为什么之前没人研究过的问题：使 Busy Beaver(n) 的值独立于集合论的、我们实际上能够证明的最小 n 是多少？显然存在某个 n 使这成立，但我们说的是
一千万，还是十？实际上，这个问题归结起来几乎像是软件工程：你必须构造一台图灵机，让它检查集合论的所有定理，并且只有在发现矛盾时才会停机，而且你得用尽可能少的状态来构造这样一台图灵机。你可以构造出这样一台机器，用
仅 n 个状态，那么你就证明了集合论无法确定 Busy Beaver(n) 的值，因为如果它能确定，它就会由此确定自身的一致性，而这恰恰是哥德尔定理所不允许的。我们最终做到的是找到了一台这样的机器，有 8000 个状态，大约 8000 个状态，那是经过大量优化之后的结果，
需要大量编码、工程工作和新想法。从那以后，回到您之前的问题，又是一位学术界之外的业余爱好者，名叫 Stefan O'Rear，设法改进了我们的上界，把它降到了 800 个状态以内。对，这就是目前的纪录。现在，如果能把它降到，比如说
这是个很好的问题：能不能把它降到 10 个状态左右？那就意味着，哪怕只是为了得到 Busy Beaver 函数接下来的几个值，我们也已经必须超越现有的集合论公理。但也许不是这样，也许用现有的集合论甚至可以得到一百个值，我们不知道。现在你可以做的是，
不管在哪一点上，ZF 集合论，即 Zermelo-Fraenkel 集合论，它是大部分数学公认的基础，不管它在哪一点上耗尽了力量，我们并不确切知道那个点在哪里，你都可以用所谓的大基数公理去扩展它，这些公理基本上断言存在一种无穷，比任何能在 ZF 集合论中定义的无穷都大。或者你也可以
说，存在各种特定种类的无穷，这样大概就能以此确定更多的 Busy Beaver 函数值。但问题是，不管你想到的是什么集合论，只要你能造出一台图灵机来枚举该集合论的所有定理，那么这台图灵机有多少个状态，
§06文稿 - 00:50
就为该集合论最多能确定多少个 Busy Beaver 数设定了上限。所以在某种意义上，能确定越来越多 Busy Beaver 数的集合论，必须变得越来越复杂。我们知道这一点。而且正如您所说，永远不会有系统的办法去搜索它们，因为如果有的话，就会使 Busy Beaver 函数变得可计算。
而没有系统的搜索办法意味着，我们可以不断提出越来越多的集合论。看看现代数理逻辑，集合论学家确实在这样做，他们提出越来越多的大基数公理，但有时他们会发现自己的公理是不一致的，或者他们暂时性地采纳某个公理
并使用它，但学界并不真正确信它不会导致不一致。所以，没有万无一失的办法来想出这些公理，并确信你得到的仍然是一个一致的系统。好，让我提出一个非常非常简单的思想实验。好的。这是受那个笑话启发的：如果你向地球照射足够多的阳光，它会反射回一辆
特斯拉。好，思路是这样：如果图灵原理（Turing principle）为真，你可以在一台大到难以想象的计算机上模拟地球、太阳系和一切，连同上面所有的人类，只要给定适当的初始数据。是的。而模拟这一切是一个可计算函数，如果你每隔一百年检查一次，看看人类在这个世纪证明了的最大 Busy Beaver 数是多少，那么一百个世纪后的最大 Busy Beaver
数证明，这难道不就是一个可计算函数吗？它告诉你 Busy Beaver(n) 可以无限地越来越高，只要……哦，嗯，它会给你一个计算 Busy Beaver 函数任意值的办法，如果人类确实继续下去的话。你可以说，在这样的假设下：第一，我们物理世界中的一切都是可计算的，
我们俩几乎是不加评论地放过了这个假设，当然这本身就是一个巨大的问题，有些杰出的人物，比如 Penrose，持相反观点。但好，假设我们所做的一切都是可计算的，并且假设我们能够以某种方式不断地发现越来越多的 Busy Beaver 函数值，
无限地继续下去，那么如果这成立，我们就会得到矛盾。对。所以要么图灵原理是错的，要么我们无法无限地继续扩展。是的，一个非常保守的出路是说，我们去计算越来越多的 Busy Beaver 数的探索终将走到尽头。好，这很有意思。事实上，自 20 世纪 80 年代初以来，就没有再确定过新的 Busy Beaver 数了，
那有意思。那是 Busy Beaver(4) 被确定下来的时候。好的，好的，我期待您和那位业余爱好者合写的论文，他叫 Bruce Smith，对吧（原文转写为 “brute smith”）？好的，很有意思。那么现在让我问您，我记得去年在课上您说过，基本上我们只有很少几个非常重要的量子算法，比如 90 年代发现的 Grover 算法和 Shor 算法，而现在很
多东西都只是这些算法的扩展。您认为有没有可能发现，有没有充分的理由认为还有其他像 Grover 算法和 Shor 算法那样基础而重要的量子算法有待发现？我很希望有，我会非常激动地发现这样一个算法，或者让我的某个学生发现它。这正是我们进入这个领域所追求的那种发现。
现在，如果我们在智识上诚实的话，就必须承认，自 Grover 算法被发现以来已经 25 年了，也许在过去 25 年里，再没有发现任何像 Shor 或 Grover 算法那样基础的量子算法。我们发现的，正如你上我的课时学到的，
是 Shor 算法和 Grover 算法数量极其庞大的推广、新应用和变体，包括所谓的量子游走算法，包括基于相位估计的算法，还有一些
完全不同的量子算法也被发现了，不过它们所解决的问题可能更抽象，或者说更难解释它们到底在解决什么问题。所以你可能会怀疑：这是不是我们缺乏想象力？另一种可能是，如果你看
经典计算机科学的历史，你会发现有少数几种基本技巧是在经典计算机科学历史的很早期就被发现的。其中之一是动态规划，也就是把问题递归地分解为子问题，更一般地说就是递归；还有分治法、贪心算法、
凸规划、线性规划、高斯消元。经典算法领域是极其庞大的，然而我们所知的大多数经典算法，在某种程度上都是由这些很早就被发现的基本模式构建起来的，而我们通常
不会把这看作经典算法的失败。我们只是认为，算法世界有这些基本特征，人们一开始去找就注意到了，然后你可以走得更远，但你是在已有基本东西的基础上走得更远的。所以，也许我们应该把 Shor 算法和 Grover 算法不仅仅看作具体的算法，而是看作
量子算法世界的某些基本设计模式，而它们很早就被发现并不奇怪，就像动态规划是在经典算法历史的一开始就被发现的一样。这是一种观点。另一种观点是，当人们要求更多的量子算法，
或者说因为我们没能发现更多量子算法而责怪我们时，我喜欢用另一个问题来回答：你想要这些算法来解决什么问题？令人惊讶的是，这个问题几乎总能让他们语塞，因为他们甚至没有想过。原因在于，不管他们说出什么问题，量子算法领域的人很有可能都已经想过了，
而且我们对于 Grover 类算法能带来多大的加速是有所了解的，我们也有充分的理由认为你不可能做得比那更好。或者我们会说，也许有……比如在图同构问题上，当然，也许存在多项式时间的量子算法，但那很可能只是因为存在多项式时间的经典算法，而这个算法
只是还没有被发现，尽管已经有了重大进展。所以不管他们说出什么问题，很可能已经有人在量子算法的背景下研究过它，然后我就能告诉他们，对于那个问题，目前的情况究竟是怎样的，人们卡在哪里。所以，如果我们想发现真正全新的量子
算法，方法可能是认识到真正全新的问题，也就是人们此前甚至没有想过要为之设计算法的问题。我还喜欢这样说：在数学或科学的任何一个领域，都有这样一种现象，低垂的
§07文稿 - 01:00
果实会在很早的时候就被摘走，而我们这些稍晚进入这个领域的人，如果想找到果实，就得往更高处够。但我认为，低垂果实被摘光这个问题的终极解决办法是找一片新的果园。所以要弄清楚量子计算机有哪些潜在的问题可以解决，
是以前没有人想过的。也许，像如今终于出现的这样，人们开始拥有可以做实验的量子计算机，会有助于激发这些新问题或新应用的发现。那么，像 Grover 算法那样，从第一性原理出发，有没有理由期待还存在其他可以用量子算法解决的问题？是的，所以，比如说
任何像 Grover 算法那样基本的东西，你只要看看振幅随时间如何变化，就觉得应该存在一个算法的情况，那大概早就被人抢先发现了，因为与 25 年前相比，量子算法已经精细复杂得多了。但是有些问题，有一些证据表明可能存在量子算法，
尽管我们还不知道它。如果它存在的话，一个很好的例子是计算两个字符串之间的编辑距离，也就是把一个字符串变成另一个字符串所需的最少插入、删除和修改次数。这是 DNA 序列比对等问题的基础问题。已知最好的算法需要二次时间，事实上它基于动态规划。而且有一些
证据表明，可能存在一个需要 n 的 3/2 次方时间左右的量子算法，但如果有的话，它还没有被发现。所以存在这样的情形。明白了。好，接下来我想问的问题是，为什么这个领域乃至许多其他领域的许多重要发现，都来自
紧密沟通的合作者小组，或者此类小组中的人？您在 Sean Carroll 的播客上说过，Shor 和 Grover 是在贝尔实验室的合作者，而我不确定他们是否真的是合作者。我想他们在同一栋楼里工作。我认为 Shor 算法的发现在各处都引起了很多兴奋，但是
当然在贝尔实验室，Shor 就在那里。而我认为 Grover 也在贝尔实验室工作，但在一个完全不同的部门，我想他受到了那种兴奋气氛的影响。我甚至不确定他们在 Grover 发现他的算法之前是否认识，我可以去问问他们。不过
更广泛地说，在思想史上，重大的创新似乎总是成簇出现的，贝尔实验室就是一个巨大的例子。Shor 算法和 Grover 算法其实处在贝尔实验室鼎盛时期的尾声，那个鼎盛期主要是
40 年代、50 年代、60 年代、70 年代，在这一个地方诞生了晶体管、通信卫星和许多其他东西。另一个例子，我们可以举古代世界的雅典，可以举佛罗伦萨，
可以看看剑桥大学，比如说 20 世纪之交的剑桥，那里有那么多改变世界的数学家、经济学家、哲学家和物理学家。这也许是因为环境中的某种东西，也就是
想法在人与人之间相互激荡，人们看到有人取得了惊人的成就，要么受到启发，要么把它视为挑战，想要与之竞争，拿出自己的东西。硅谷是另一个大例子，不过更多是技术方面而不是科学方面。这是
一种解释；另一种解释是，某些地方在某些时期吸引了所有那些本来就可能产生这些伟大想法的人，这种人想去这些中心，不管它们在哪里，于是这些中心就聚集了那些可能会发现这些东西的人，
这种情况下相关并不等于因果。好，那么现在让我问您，我在这个播客上采访过很多经济学家，我想这个问题听众会感兴趣。在您那篇关于哲学家为什么应该关心复杂性的论文中，您谈到寻找纳什均衡的困难可能与经济学讨论有关，您能解释一下吗？好的，14 年前，理论计算机科学有一项重大进展，
理论证据终于被发现，说明为什么计算纳什均衡基本上是一个困难的问题。这证实了人们长期以来的一个怀疑，因为，如果我们看冯·诺依曼均衡，也就是比如说两人零和博弈的均衡，
那么用线性规划就可以很容易地找到它。但纳什均衡在某种程度上是一个更复杂的东西，纳什在 50 年代证明它们存在所用的是所谓的角谷（Kakutani）不动点定理，这是拓扑学中的一个不动点定理。如果你试图
把这个存在性证明真正展开成一个计算均衡的算法，你得到的是一个需要指数时间的算法，它最终会到达均衡，但可能得沿着一条指数级长的路径走才能到达。如果你对此感兴趣，我认为关于这个问题写得最好的，远远是最好的，是 Christos Papadimitriou 的作品，
好，2006 年 Papadimitriou 与 Goldberg 和 Daskalakis 一起，是这个困难性定理的发现者之一。它并没有证明寻找纳什均衡是困难的，甚至也没有证明它是 NP 困难的，这个问题的结构不太适合成为 NP 完全问题，因为纳什定理告诉我们
纳什均衡总是存在的。要以我们目前理解的任何方式成为 NP 完全，必须是一个判定问题，即有解还是无解，但对于寻找纳什均衡，解总是存在的，问题只在于如何找到它。但所证明的是，寻找纳什均衡基本上至少与任何其他问题一样困难，那些问题
的解由于同类原理而保证存在。所以它对于这个解被保证存在的问题复杂性类来说是完全的。那么这对经济学意味着什么？这并不清楚，它是否有直接的含义，但它符合这样一个总体
叙事：均衡存在，并不是故事的终点。如果市场实际上找不到均衡，也就是说，如果计算这个均衡需要指数时间，那么我们也不应该指望市场能找到它。当然经济学家很清楚存在这些问题，
§08文稿 - 01:10
人们并不是完全理性的，即使他们想要完全理性（他们也并不总是想），完全理性可能涉及他们根本做不了的计算。他们已经尝试过解释这类现象，成功程度不一，但我想说，纳什均衡对经济理论如此核心，所以
寻找纳什均衡的困难性也许是一个有分量的结果，强调了这个总体观点。这非常有意思。您是否认为哈耶克的知识问题，或者他表述它的方式，也可能与复杂性有关？比如在中央计划中，为了满足官僚们设定的某些约束，可能就像一个 NP 完全问题，也就是说，嗯，我
想把两件不同的事分开。一件是对经济中正在发生的事情等缺乏了解，另一件是缺乏对你所掌握的知识进行计算的能力。纳什均衡的困难性谈的是后一个问题。是的，它们在某种程度上是相关的，它们都是
偏离完全全知的不同形式，但它们是不同种类的偏离，而在理论计算机科学中，我们经常必须区分它们。比如，人们常常问我某个问题是不是 NP 完全的，而他们真正想问的其实是：收集
信息有多难？这有点像拿苹果和橘子比，是一种范畴错误。要谈论一个问题属于 P 还是 NP 或别的什么，我们假定输入是给定的，所有需要的信息都摆在你面前，我们只关心对这些信息计算某些东西的难度。当然还有
另一种困难，就是经济行为主体没有他们需要的信息，中央计划者当然也没有他们需要的信息。而且经济学中确实有一整个分支，就是信息经济学：你愿意付出多少来了解正在发生的事情，
或者你如何设计一场拍卖，从而引出你想从参与者那里获得的信息，诸如此类。我认为经济学家处理这些问题也许更容易一些，或者说这些内容比计算方面的考虑更好地融入了经济学。好，这非常有意思。再问几个问题。好的。我要把话题带回 David Deutsch
和创造力。好。在《Quantum Computing since Democritus》的“随便问”那一章里，有一个学生问您创造力属于哪个复杂性类，您说，部分原因是，我们有十亿年的自然选择，给了我们一个非常好的启发式工具箱，用来解决某些搜索问题，比如 NP 中的问题。但这听起来好像是说，我们比黑猩猩有更多启发式来解决这些问题，黑猩猩又比蚂蚁多。我
不知道您是不是这个意思，但您是否把创造力的算法看作一种你有或者没有的东西，还是说你只是有更好的启发式来在不同的……中搜索？我不认为存在创造力的算法这种东西。事实上，这个说法几乎是自相矛盾的：如果有这样一个算法，那么它输出的东西就不再有创造性了，不是吗？因为那只是该算法的输出。所以我认为
似乎确实存在某种通用的推理能力，或者说通用的创造性地发明问题解决方案的能力，比如说爱因斯坦拥有的比随便一个路人多，而随便一个路人拥有的又比黑猩猩多，
黑猩猩拥有的又比蚂蚁多，但很难清楚地表述我们到底指的是什么，使得它能够真正支撑这些跨越截然不同进化历史和生活目标的比较。您是否接受 David Deutsch 在《The Beginning of Infinity》中的术语“通用解释者”（universal explainer）：人是通用解释者，AI 也将是通用解释者，但
非人类动物不是，而这是唯一重要的分界线？我认为 Deutsch 对事物的思考极其乐观，同时也极其绝对化。我不知道还有谁像他这样乐观，也几乎没有别人像他那样非黑即白。不过，从黑猩猩到人类，似乎确实很可能存在某种
需要跨越的阈值。没错，黑猩猩比奶牛聪明，但如果你盯着它们俩看，并不会觉得黑猩猩比奶牛明显更接近于能够登月，或者能够证明“auslan 定理”（原文转写如此），或者
做到这类事情。而人类，在先后顺序上，经历了几个以前动物界从未跨越过的极其重要的里程碑。首先是语言的普遍性，也就是拥有一种递归的语言，能够
表达复杂度没有上限的思想；然后是文字的发明，即把这些思想跨代传递的能力；然后是一种可以指称任意大数的数字系统；然后是计算机，它们是通用机器，也就是有能力
建造这类机器；而所有这一切，伴随着我们能够用明确的理论来解释我们周围的世界，达到了任何其他动物物种都从未能做到的程度。话虽如此，我实际上不知道人是不是通用
解释者。也就是说，我不知道我们是不是能解释一切，甚至不知道我们是不是能解释一切可以被解释的东西。当然，我希望我们能继续解释比现在多得多的东西。但是 Deutsch 会以不寻常的方式使用词语，比如
在他谈到自己为什么如此乐观时，他乐观的一部分原因是，当他使用“人”（people）这个词时，也包括外星人。所以他会说，是的，地球上的人类有可能把自己全都毁灭掉，可能爆发核战争或环境灾难，但那没什么大不了的，因为从更广义上说的“人”，也就是宇宙中其他地方的生命，将会
继续去做那些我们本来也会做的所有了不起的事。这对我们地球上的大多数人来说，也许算不上多大的安慰。所以，当他说“人是通用解释者”之类的话时，你总得追问他，不仅要问“通用解释者”是什么意思，甚至还要问“人”是什么意思。他对“通用解释者”这一部分的主张是，正如多世界是描述量子力学最
和谐的方式，使你不必假设一个任意的坍缩；同样，既然我们没有理由期待存在无法解释的东西，也没有证明表明存在我们无法解释的东西，那么最和谐的解释就是我们能解释一切。好吧，我不知道。有些问题，比如意识的困难问题，或者“为什么会有宇宙”这个问题，不只是我们
§09文稿 - 01:20
没有解释，而是当我们试图设想什么才可能构成一个解释时，头脑就开始原地打转：一个解释，哪怕在原则上，究竟会是什么样子？这可能只是缺乏想象力，但也可能是，我们都知道那种
两岁小孩，一直问为什么，你告诉他，他又问为什么，你再告诉他，他又问为什么，问了半打为什么之后，你就一路回到了大爆炸，回到了宇宙的开端，而他们还会继续问为什么。这有可能是，
存在一些问题，具有这样的性质：每个……嗯，首先，我认为连 Deutsch 也认为，我们不会在某个时刻拥有对一切的解释，因为 Deutsch 说，我们回答的每一个问题都会引出更多的问题，
每次你解释了某件事，就会有这样的问题：这个解释所依据的东西，为什么是那样？就像那个两岁小孩，我们总是可以越挖越深。好了，现在回到我们这次谈话的前面：如果我们想想 Busy Beaver 函数，我们知道，不只是需要越来越多的
资源才能计算 Busy Beaver 函数越来越多的值，因此你永远不可能知道全部。更是存在一些固定的值，比如 Busy Beaver(800)，现有的集合论公理可证明地不足以让你确定它。同样地，据我所知也可能存在一些固定的问题，也许意识的困难问题，
也许“为什么会有宇宙”，我们目前认为属于解释的东西就是不足以解释这些问题。不过我不知道。与 Deutsch 不同，我不想断言我能从第一性原理知道答案，我想继续寻找对这些问题的解释。在你寻找解释的时候，
假定解释存在，在心理上可能是有帮助的，但我们不要把它说得太过。我们不要把一个有用的启发式提升为现实的基本原则。但是在这一点上，Deutsch 写过一本书《The Fabric of Reality》，书中谈到哥德尔不完备定理实际上证实了创造力的重要性，
因为如果我们需要提出新的公理才能证明 Busy Beaver 的某些值，那就是创造力的意义所在。至于意识的困难问题，我想他认为是可以解决的；但即便无法解决，它之所以如此困难，也不是因为它不是我们心智的产物，而只是看起来我们无法想象一种可能的心智……而这本身也可能是我们心智的产物：无论你拥有什么样的心智，我们都想象不出解决它的可能方式。最后一个问题：对于一个对技术学科感兴趣的 20 岁年轻人，也许他不像您当年那样在读博士项目，您会给什么建议？
对，对技术学科感兴趣的人。就是尽你所能地学习。我是说，从来没有哪个时代像现在这样，有这么多资源可供任何想学东西的人使用。所以去上课，找你的教授聊，上网，或者
读书，深入钻研一个学科，你可能会惊讶地发现，有时门槛其实很低。比如说你对量子计算感兴趣，当然也可以是别的任何东西，量子计算的整个文献
基本上都可以在 arXiv 上免费获得。如果你每天晚上去看新出的量子计算论文，把你感兴趣的标出来读一读，每篇论文都会提出作者们还不知道答案的新问题，有时这些问题会明确列在“开放问题”部分，其他时候
是你自己能想到的问题。你可以研究这些问题，如果你对它们有想法，可以去和论文作者交流。要成为整个领域的专家，可能需要好几年甚至几十年，
而你可能离那一步还很远，但要成为某一个特定的小问题上的世界级专家，其实并不需要多久。所以试着在某件事上成为世界级专家，哪怕是非常非常窄的一件事。一旦做到了，你就可以就此写一篇文章或者做一个项目，那会带来更多
东西，也许会带来未来的合作，然后你可以尝试成为范围稍宽一点的东西的专家，再宽一点，如此继续。是的，这是非常好的建议，我很喜欢。好的，教授，非常感谢您抽出时间。嘿，如果你喜欢这期播客，请考虑把它分享给你的朋友，并发到社交媒体上。口碑对于像这样一个新的小播客来说极其宝贵，所以，感谢收看。