量子计算公开课：从德谟克利特、计算复杂性到自由意志 | 周末读书
量子计算公开课：
从德谟克利特、计算复杂性到自由意志
作者：［美］斯科特·阿伦森（Scott Aaronson）
译者：张林峰 李雨晗
出版：图灵|人民邮电出版社
斯科特·阿伦森 Scott Aaronson，量子计算和理论计算机领域影响力巨大的学者。2020年度ACM计算奖得主。现为得克萨斯大学奥斯汀分校讲席教授，曾任教于麻省理工学院。主要研究领域为理论计算机科学。其研究兴趣集中在探索量子计算机的能力和极限，以及更广泛的计算复杂性理论。阿伦森毕业于康奈尔大学，获得加州大学伯克利分校计算机科学博士学位。曾荣获Tomassoni Chisesi物理学奖（2018年）、Simons研究员奖（2017年）、美国国家科学基金会的Alan T. Waterman奖（2012年）等奖项。
想获得该书的读者可以在后台留言，写下您试读的体会，留言点赞前8名的读者将获赠该书一本（三个月内已获得赠书的读者不参与此次活动）。截止时间是7月12日早8点，10点会公布8位获奖者名单。期待您的参与！
A
第4章：“心智与机器”
现在我们要开始讲一些我知道你期待已久的东西：一顿关于心智、机器和智能的哲学大餐！
不过，首先让我们讨论完可计算性。在本章中，我们将反复用到一个称为谕示（oracle）的概念。这个概念很容易理解：假设我们拥有一个“黑箱”，或所谓“谕示”，它能够立马解决一些困难的计算问题，给出其结果。（当我还是大学新生时，有一次我跟导师谈起了一个假想的“NP– 完全性精灵”可能带来的后果：它将立马告诉你，给定一个布尔表达式是不是可满足的。导师不得不纠正我：它们 不叫“精灵”，它们叫“谕示”。这听上去就专业多了！）
谕示似乎首先由图灵在他 1938 年的博士论文中开始研究。显然，任何会用一整篇论文来研究这些假想事物的人必定是位极端纯粹的理论家，绝不会务实。图灵的情况便是如此——事实上，在博士毕业后的 1939 至 1943 年，他都在研究 26个字母的某种深奥的对称变换。
不管怎样，如果给定问题 B 的一个谕示，问题 A 即可由一个图灵机解决，那么我们称问题 A 图灵可归约（Turing reducible）到问题 B。换句话说，“A 不比 B难”：如果我们有一个假想的设备能够解决 B，那我们也能够解决 A。如果两个问题互相图灵可归约，我们就称两者是图灵等价的（Turing equivalent）。因此，比如，一个命题能否从集合论公理中得到证明的问题与停机问题就是图灵等价的：如果你能够解决其中一个问题，那么你就能够解决另一个。
现在，图灵度（Turing degree）是指对于某个给定问题，所有与之图灵等价的问题的集合。图灵度有什么例子？其实我们已经见过两个例子了：(1) 可计算问题的集合，以及 (2) 与停机问题图灵等价的问题的集合。说这两者的图灵度不相等，也就是以另一种方式说停机问题不可解。
有比这两者更高的图灵度吗？换句话说，有什么问题比停机问题更难，它即便借助停机问题的谕示也解决不了？好吧，考虑下述“超级停机问题”：给定一个拥有停机问题谕示的图灵机，然后问它是否会停机。我们能够证明即便拥有一般停机问题的谕示，这个超级停机问题仍然解决不了吗？是的，我们可以！我们只需拿出图灵对于停机问题不可解的原始证明，然后“进行升级”，给所有机器都配上一个停机问题的谕示。证明的每一步都与原来的一模一样，这时我们称这个证明“相对化（relativize）了。
这里有一个更微妙的问题：有没有什么问题的难度介于可计算问题和停机问题之间？这个问题最早在 1944 年由埃米尔·波斯特（Emil Post）提出，并最终在 1956 年由美国人理查德·弗里德伯格（Richard Friedberg）和苏联人 A. A. 穆奇尼克（A. A. Muchnik）分别独立解答。答案是肯定的。事实上，弗里德伯格和穆奇尼克证明了一个更强的结论：存在两个问题 A 和 B，给定一个停机问题的谕示，两者均可解；但给定一个对方的谕示，两者都不可解。这些问题可通过一个旨在消除所有可能使 A 归约到 B，或者使 B 归约到 A 的图灵机的无穷过程加以构造。不幸的是，这样得到的问题是极其不自然的；它们不像任何在实践中可能遇到的问题。甚至直至今日，我们还没有找到一个“自然”的、具有中间图灵度的例子。
自从弗里德伯格和穆奇尼克取得突破以后，有关图灵度结构的诸多细节已被深入研究。这里提一个最简单的问题：如果两个问题 A 和 B 均可归约到停机问题，那么是否一定存在一个可归约到 A 和 B 的问题 C，使得任何可同时归约到 A 和 B 的问题都可归约到 C ？想想吧！但现在是时候转入下一个话题了……（顺便一提，这个问题的答案是否定的。）
可计算性的哲学基础是邱奇—图灵论题。它得名自艾伦·图灵及其导师阿隆佐·邱奇，尽管他们对于“自己”的这个论题持何种态度还存在争议。简单来说，邱奇—图灵论题说的是，任何“自然地被视为可计算”的函数都可被一个图灵机计算。或者换句话说，任何关于计算的“合理的”模型都将给出与图灵机模型相同的可计算函数的集合，或者是其真子集。
这里存在一个显而易见的问题：这个命题是什么类型的？这是一个表明何种函数在物理现实中可计算的经验命题，还是一个关于“可计算”一词含义的定义性命题，又或是跟两者都沾点边？
好吧，无论答案如何，邱奇—图灵论题可谓极其成功。正如你可能知道的（并且我们之后也会讨论到），量子计算严肃挑战了所谓的拓展邱奇 – 图灵论题：任何自然地被视为可有效计算的函数都可被一个图灵机有效计算。但在我看来，到目前为止，尚没有什么能够严肃挑战原始的邱奇 – 图灵论题——不论是作为一个关于物理现实的命题，还是作为一个关于“可计算”的定义。
对于邱奇—图灵论题的“不打紧”的挑战则已经有很多。事实上，一些会议和期刊便专注于这些挑战——你可以在网上搜索“超计算”（hypercomputation）。我读过其中一些材料，它们大多是这个思路：假设你能够在一秒内完成一个计算的第一步，在二分之一秒内完成下一步，在四分之一秒内完成再下一步，在八分之一秒内完成再下一步，如此等等，那么你便会在两秒内完成无限次的计算！好吧，这听上去有点儿傻，也许加入一个黑洞或其他什么东西能让它更特别一些。对于这样的东西，那些守旧的图灵反对派又能作何回应呢？（这让我想起了一个关于超级计算机的笑话：它的运行速度如此之快，以至于它能在 2.5 秒内完成一个无限循环。）
我们应该立即质疑，要是大自然真希望赋予我们如此巨大的计算能力，它也不应该以如此乏味、无趣的方式实现。其中奥秘应当毫不费力就能被我们发现。不过，要想真正看清楚为什么超计算的思路是错误的，你需要用到雅各布·贝肯施泰因（Jacob Bekenstein）和拉斐尔·布索（Raphael Bousso）等人提出的熵界（entropy bound）——这是物理学家自认为的对于量子引力为数不多的了解之一， 我们之后还会提起它。因此，邱奇—图灵论题（甚至是其原始的、非拓展的版本）其实与物理学中一些最深刻的问题相关联。而在我看来，自其诞生以来的 75 年里，无论是量子计算，还是模拟计算，又或是任何其他东西，都没能严肃挑战到邱奇—图灵论题。
另一个紧密相关的对于这种基于几何级数的计算的质疑是，我们确实在某种程度上理解为什么这种模型不合乎物理：我们相信，当时间短到 10-43 秒（普朗克尺度）时，时间的概念本身会开始瓦解。我们不知道在那里具体会发生什么。但无论如何，这种情况一点儿也不像（比如）量子计算。正如我们将要看到的，在量子计算中，没有人能对理论何处会出错、计算机何时会停止运行有丝毫定量的概念。这使得有人不禁猜想，计算机可能永远都不会停止运行。
一旦进入普朗克尺度，你可能会说，讨论将真的变得非常复杂。你可能还会说，在实践中，我们总是受限于噪声和不完美。
但问题是，为什么我们会受到限制？为什么不能将一个实数放在寄存器中？我认为，如果你真的试图让讨论变精确，你终究避免不了要谈到普朗克尺度。如果我们将邱奇—图灵论题阐释为一个关于物理现实的命题，那么它应当包含这个现实中的所有东西，包括你两耳之间的黏糊糊的神经网络。当然，这将我们直接引向了我向你承诺过的一个战事激烈的智力战场。
有个有趣的历史事实，会思考的机器的存在可能性不是人们在使用计算机多年后才渐渐意识到的。相反，他们在开始谈论计算机的那个时刻便立马想到了这一点。诸如莱布尼茨、查尔斯·巴贝奇、爱达·洛夫莱斯、艾伦·图灵、约翰·冯·诺伊曼（John von Neumann）等人从一开始就意识到，计算机不只是另一种蒸汽机或烤面包机；而由于它具有通用性，因此我们很难在谈论计算机时不谈到我们自身。
现在，我要求你暂时时放下这本书，抽几分钟读一下图灵第二著名的论文《计算机器与智能》（“Computing Machinery and Intelligence”）。
这篇论文的核心思想是什么？我读后的感觉是，它呼吁反对有机沙文主义。确实，图灵在其中提出了一些科学论证、一些数学论证，以及一些认识论论证。但在所有这些论证背后其实暗含着一个道德论证：如果一台计算机能以与人类区分不出的方式与我们互动，那么当然，我们可以说计算机并没有“真正”在思考，它只是在模拟。但基于同样的理由，我们也可以说其他人没有真正在思考，他们只是假装在思考。因此，凭什么我们在一种情况下这样说，而在另一种情况下又那样说？
如果你允许我对此发表评论（好像我一直做的是别的事情似的……），那么我会说，这个道德问题，这个双重标准问题，是约翰·塞尔、罗杰·彭罗斯等“强人工智能质疑者”无法自圆其说的。人们确实能够给出有分量的、有说服力的论证来驳斥会思考的机器的存在可能性。但这些论证的唯一问题是，它们也同样驳斥了会思考的大脑的存在可能性！
举个例子：一个常见的论证是，如果一台计算机看上去像是智能的，那其实只是设计它的人类的智能的反映。但如果人类的智能也仅是造就它的数十亿年生物演化过程的反映，这个论证又该得出什么推论呢？人工智能质疑者无法诚实地思考这个类比，每每让我感到非常失望。其他人具有的“质性”（qualia）和“关涉性”（aboutness）被简单视作理所当然接受了。只有机器的质性存在质疑。
但或许人工智能质疑者可以这样反驳：我相信其他人在思考，是因为我知道我在思考，而其他人看上去跟我很相像——他们都有十根手指、腋毛，等等。但一个机器人看上去则大为不同——它由金属制成，有天线，用轮子在室内移动，等等。因此，即便一个机器人表现得像在思考，谁又知道实际是怎样的呢？但如果我接受这个论证，为什么不能进一步推论？我为什么不能说，我承认人类会思考，但至于狗和猫，谁知道呢？它们看上去跟我太不相像了。
在我看来，我们可以将关于人工智能的所有讨论分成两类：源自图灵 1950 年论文的 70%，以及在那之后半个多世纪新涌现的 30%。
因此在 60 多年之后，我们敢说，确实有些事情会让艾伦·图灵感到出乎意料。是什么呢？其中之一是我们所取得的进展相较于当初的预期，是多么微乎其微！你还记不记得图灵做过一个可证伪的预测：
我相信在约 50 年后，我们将能够编程拥有约 109 存储容量的计算机，使得它们能够如此好地进行模拟游戏，以至于一位普通的裁判在经过五分钟的质询后正确判断出它们是否为机器的概率不超70%。
那么事实证明他的预测怎么样呢？首先，我们注意到他关于计算机本身的预测相当好。图灵预测在 50 年后（也就是到 2000 年），我们将能够编程拥有达109 （即 1G）存储容量的计算机。
但关于计算机通过模仿游戏的预测呢？图灵的预测怎么样了？
好吧，你们当中的一些人可能听说过一个叫作 ELIZA 的程序，它由约瑟夫·魏岑鲍姆在 1966 年编写。这个程序模拟了一个心理医生，它始终重复你所说的话，不论你说的是什么。魏岑鲍姆发现了一件惊人的事情，很多人对这个程序敞开了心扉！甚至有时，当你告诉他们，他们之前是在与一个程序（而且还是一个极其简单的程序）对话时，他们都不相信你。
很多年前，有人想出了一个好点子，将原始的 ELIZA 程序放进美国在线（AOL）的聊天室中，然后看会发生什么。如果你到这个网站上去看，你会发现一些很好笑的对话（幸好是匿名的），包括试图勾引这个程序、向它透露自己的感情，等等。下面这段对话是我的最爱，其中某男在最终对程序提出暗示之前，自称计划读完文学学士学位，然后将“与星巴克展开商务合作”。
某男：我想你正在为戏弄我的感受而兴奋不已。
ELIZA ：你的感受？
某男：不加入我的幻想来让我感到沮丧。
ELIZA ：你的幻想？
某男：恋爱的幻想。
ELIZA ：这跟你读完文学学士学位，然后将与星巴克展开商务合作有丝毫关系吗？
如今最先进的人机对话能力已经超过这个程度了，但也没有超过那么多。看上去，我们实际需要修正图灵测试了：如果想要验证一台计算机是否具有智能，那么我们需要要求人类裁判具有某种最低水平的智能。
当然，这里的一个问题在于，这些人一开始就假设自己是在与另一个人交谈。而在图灵测试中，裁判需要努力区分出人类和机器。因此，这不是真正的图灵测试，只是为了引人一笑罢了。不过，在过去几十年里，休·勒布纳（Hugh Loebner）一直在做一个更接近于图灵所设想的测试 A。在这里，参与测试的人被告知他们需要努力区分出人类和计算机——但许多聊天记录还是同样惨不忍睹，不论是从机器智能的角度，还是人类智能的角度。（比如，一位试图深入聊聊莎士比亚的女人被判定为计算机，因为“人类不会知道那么多有关莎士比亚的事情……”）
你可能会好奇，如果让计算机替代人类来质询会怎样？事实上，也有人这样做了。路易斯·冯·阿恩（Luis von Ahn）获得 2006 年麦克阿瑟奖，部分原因就是他在验证码（CAPTCHA）上所做的工作。验证码是一些网站用来区分合法用户与垃圾邮件程序的测试。我敢说，你肯定遇到过它们——那些你需要重新输入一遍的怪异扭曲的字母。这些测试的关键特性是，一台计算机应该能够生成和评价它们，但不能够通过它们！（很像教授为期中考试出题……）应该只有人类能够通过这些测试。所以简单来说，这些测试是在利用人工智能的缺陷。（好吧，它们也是在利用单向函数求逆计算的困难性，对此我们稍后会说到。）
关于验证码的有趣一点是，它们引发了验证码程序员与人工智能程序员之间的一场军备竞赛。当我在美国加利福尼亚大学伯克利分校读研时，我的一些研究生同学写出了一个叫作 Gimpy 的程序 [1]，它能在大约 30% 的时间里破解验证码。所以验证码不得不被加以强化，然后人工智能研究者再接再厉，想法破解……如此交替反复。谁会赢呢？
你看，当你注册一个邮箱账号时，你经常会直接面对一个古老的“何为人类”的谜题……
尽管人工智能在图灵测试方面仍然任重道远，但它们确实已经取得了一些重大进展。我们都知道卡斯帕罗夫与深蓝的对战，以及 IBM 的“沃森”在《危险边缘！》电视智力竞赛中战胜了人类冠军肯·詹宁斯，赢得冠军。可能不那么众所周知的是，1996 年，一个叫作 Otter 的程序 A 被用来解决一个困扰了数学家六十多年、连塔斯基（Alfred Tarski）及其他著名数学家都久攻不下的代数难题——罗宾斯猜想。（看起来，塔斯基几十年来都把这个问题交给了他最得意的门生。但最终，他开始把它交给他最糟糕的弟子……）这个问题很容易陈述：给定三条公理
● A 或 (B 或 C) = (A 或 B) 或 C，
● A 或 B = B 或 A，
● 非 ( 非 (A 或 B) 或非 (A 或非 (B)))=A，
我们能够由此推导出非 ( 非 (A))=A 吗？
我需要强调，这里的证明不像阿佩尔和哈肯对于四色定理的证明那样，计算机基本上只是验证数以千计的可能情况。在这里，整个证明只有 17 行长。一个人就能进行验证，然后说：“对啊，我本该也能想到的。”（在原理上！）
还有什么其他人工智能？还有一个极其复杂的人工智能系统，你们几乎所有人都用过，并且今天说不定还会用到很多次。是什么？对，搜索引擎，比如谷歌。
你可能会看下这些例子——深蓝、罗宾斯猜想、谷歌以及“沃森”，然后说，这些其实不是真正的人工智能。它们只是一些利用聪明算法实现的大规模搜索。但这样的说法无疑会让人工智能研究者感到恼怒。他们会说：如果你告诉 20 世纪60 年代的人们，30 年后我们将能够战胜国际象棋特级大师，然后问他们这算不算人工智能，他们会说，这当然算是人工智能！但当我们现在已经做到时，它却不再是人工智能了——它仅仅是搜索！（哲学家也有类似的抱怨：只要哲学的某个分支得出了任何实实在在的东西，它就不再被称为哲学！而是被称为数学或科学。）
相较于图灵时代的人们，我们现在还意识到了另外一件事。那就是，当我们试图编写程序模拟人类智能时，我们其实是在与数十亿年的生物演化相较量，而这非常之艰难。由此可得到一个违反直觉的结论：让计算机程序在国际象棋比赛中打败卡斯帕罗夫，要比让计算机识别不同光照条件下的人脸容易多了。常常是，对于人工智能来说最困难的任务，是那些对于五岁小孩来说不值一提的任务，因为这些功能已经通过演化融入我们的身体，我们甚至不加考虑就能做到。
在过去六十多年中，有没有出现关于图灵测试本身的新洞见？在我看来，没有太多。不过从另一个角度，确实有一个著名的“未遂”洞见——塞尔的中文房间。这个论证在 1980 年左右被提出，它认为，即便一台计算机确实通过了图灵测试，它也不会是智能的。事情是这样的，假如你不会说中文。你坐在一个房间中，有人透过墙上的一个洞递给你一张写有中文问题的纸条，而你可以通过查阅一本规则手册来回答问题（同样也是用中文）。在这种情况下，你可能得以进行一场智能的中文对话，然而根据假设，你一句中文也不理解！因此，符号处理不意味着理解。
强人工智能支持者会如何回应呢？他可能会说，你或许不懂中文，但那本规则手册懂中文！换句话说，理解中文是由你和规则手册构成的系统涌现的一个特性，就像理解母语是你大脑中的神经元系统涌现的一个特性。
塞尔对此的回应是：好，那我把规则手册背下来！这时，除了你的大脑之外没有其他系统了，但你依旧不理解中文。对此，人工智能支持者会立刻反驳说：在这种情况下同样存在另一个系统！假设你背下了规则手册，我们就需要区分原始的你与新的、通过遵循所记忆的规则而生成的模拟存在——这个存在与你的唯一联系可能是，它碰巧与你栖息于同一具躯体中。这个回应或许听上去很疯狂，但“疯狂”只是对从未接触过计算机科学的人而言。对于一位计算机科学家来说，一个计算（比如，一个 LISP 解释器）能够通过严格执行规则生成另一个不同的、不相关的计算（比如，一个太空射击游戏）是完全合理的。
你看，就像我稍后会讨论的，我并不知道中文房间论证的结论是真还是假。我也不知道对于一个物理系统来说，“理解”中文需要什么样的必要或充分条件——我想，塞尔或其他任何人也不知道。但单单作为一个论证，中文房间的几个方面始终困扰着我。其一是在我们应当预期直觉会非常不可靠的一类问题上， 会不自觉地诉诸直觉——“这只是一本规则手册！”其二是双重标准：神经元系统可以理解中文，这一点被视为显而易见的，而且完全不成问题，这使得人们根本不会去想为什么规则手册不能理解中文。其三，中文房间论证在如此大程度上建基于一个可能成问题的意象，换句话说，它试图通过巧妙的表述避开整个计算复杂性的议题。它让我们想象一个人迎来送往一堆纸条，却对其内毫无理解和洞察，就像一些笨拙的新生在数学考试中写下(a +b)2=a2+b2 。但我们讨论的是多少张纸条？那本规则手册到底有多大？而你需要以多快的速度查阅它，才能进行一场接近实时的智能的中文对话？如果规则手册中的一页对应于说中文的人的大脑中的一个神经元，那么我们谈论的这本“规则手册”至少要有地球那么大，可被一大群以接近光速穿行的机器人检索查阅。当你将它表述成这样子时，你可能就不再无法想象，由此生成的这个说中文的巨型实体可能拥有被我们称为理解或洞察的东西。
当然，每个人在谈论这些东西时，其实都在极力避免涉及意识的问题。你看，意识有着怪异的双重性：一方面，它可以说是我们了解到的最神秘的东西；另一方面，它不仅是我们直接感知到的东西，而且在某种意义上，它也是我们唯一直接感知到的东西。你知道的，我思故我在，诸如此类。举个例子，我可能错误地认为我的衬衫是蓝色的（可能我产生了幻觉或者出于别的原因），但对于我认为它是蓝色这件事情，我不会出错。（如果我会出错，那么我们会得到一个无穷递归。）
有没有其他东西也能带来绝对确定的感觉？没错，是数学！顺便一提，我认为数学与主观经验之间的这种相似性或许可以帮助解释数学家的“准神秘主义”倾向。（我已经能够听到一些数学家倒吸了一口冷气。真不好意思！）物理学家理解这一点很重要：当你与一位数学家交谈时，你可能并不是在与一位畏惧真实世界因而退缩到自己的思想小天地的人交谈，你可能是在与一位一开始就不认为真实世界有什么“真”的人交谈！
我的意思是，想一想我之前提到过的四色定理的计算机辅助证明。那个证明解决了一个有着百年历史的未解之谜，但它的解决办法是将问题归约为数以千计的可能情况。为什么有些数学家不相信这个证明，或者至少希望找到一个更好的证明？因为计算机“有可能会犯错”吗？好吧，这是个很弱的质疑，因为这个证明已经被多个独立的团队用不同的软件和硬件反复验证过了。再说了，人类也时常会犯错误！
我想，归根结底，这里的问题在于，存在一种观念，在其中，四色定理已被证明；还存在另一种很多数学家所理解的证明的观念，而这两种观念并不相同。
对于很多数学家来说，如果只是一个物理过程（有可能是经典计算、量子计算、交互式协议等）运行完毕，然后就声称这个命题已被证明，那么不论相信“这个物理过程是可靠的”的理由有多么充分，一个命题都并未被证明。相反，只有当数学家感到他们的心智可以直接感知到其正确性时，这个命题才是被证明了的。
当然，我们很难直接讨论这些事情。但我在这里试图要指出的是，很多人的“仇视机器人情绪”很有可能源自以下两个因素：
1. 一种直接的经验确定，即认为机器人是有意识的——能够感知到色彩、声
音、正整数等，而不论其他人能不能；
2. 一种信念，即如果这些感知只是一个计算，则机器人不可能通过这种方式
具有意识。
比如，我认为彭罗斯对于强人工智能的质疑就源自以上两个因素。而他借助哥德尔定理的论证只是后加的装饰。
在那些这样想的人看来（在某些情绪下，我也属于其中），赋予一个机器人意识等价于否认自己能够意识到自己是有意识的。有没有什么体面的方法可帮助他们摆脱这个困境？也就是说，不暗含哪怕一点儿双重标准（为我们自己和机器人制定不同规则）的方法？
我个人喜欢哲学家戴维·查默斯所提出的破解方法。简单来说，查默斯所主张的是一种“哲学上的 NP 完全性归约”：将一个谜归约为另一个。他说，如果某一天，计算机在每一个可观测的方面都能够模拟人类，那么我们不得不承认它们是有意识的，正如我们承认其他人是有意识的。至于它们如何才能变得有意识呢？——好吧，我们对此的了解程度就如同我们对一大群神经元如何能变得有意识的了解程度一样，少之又少。确实，这是个谜，但这个谜看上去与另一个谜并没有那么不同。
思考题
1. 我们能否不失一般性地假设，一个计算机程序能够读取自身的源代码？
2. 要是在 19 世纪之前被称作“水”的那个东西被事实证明是 CH4 而非 H2O，
那么它还是水吗？还是它会成为其他的东西？
目录
中文版序言 v
致中国读者 ix
引言 xi
第1章 原子和虚空 1
第2章 集合 6
一阶逻辑规则 7
关于非负整数的皮亚诺公理 7
集合论的公理 9
第3章 哥德尔、图灵和他们的小伙伴 15
图灵机 16
额外补充 23
第4章 心智和机器 25
第5章 古复杂性 38
第6章 P、NP和它们的小伙伴 47
第7章 随机性 62
第8章 密码学 80
密码学 81
伪随机数发生器 83
单向函数 86
公钥密码学 87
第9章 量子力学 93
小于0%的可能性？95
混合态 99
平方规则 100
实数与复数 102
线性 106
第10章 量子计算 113
反算 117
与经典复杂性类的关系 118
量子计算和NP完全性问题 124
量子计算和多世界 126
第11章 彭罗斯 128
打开黑盒子 130
冒险说些显然的事 133
所有人都瞄着这一整块量子“肥肉” 133
第12章 退相干和隐变量 137
进坑 138
故事一 退相干 140
退相干和热力学第二定律 142
故事二 隐变量 145
“行不通”定理大荟萃 148
隐变量的例子 153
第13章 证明 160
何为一个证明？160
概率证明 162
零知识证明 163
PCP 166
模拟隐变量理论的复杂性 167
第14章 量子态有多大？171
第15章 量子计算十一诘 185
第16章 学习 194
第17章 交互式证明、电路下界及其他 207
交互式证明 208
新进展 218
量子交互式证明 221
第18章 人择原理趣谈 224
第19章 自由意志 244
第20章 时间旅行 258
第21章 宇宙学和复杂度 273
第22章 问我什么都行 289
注释 306
致谢 317
查看更多周末读书内容
《物理》在淘宝店和微店上线，扫码即可购买过刊和现刊。
▼往期精彩回顾▼