人工智能时代：破解人机共存密码（套装共10册）

1993年计算机科学家伊桑·伯恩斯坦（Ethan Bernstein）和优曼许·沃兹内尼（Umesh Vazirani）为“有界误差量子多项式时间”定义了一个新的复杂度等级，他们称之为BQP问题。他们定义的类包含量子计算机可以有效解决的所有决策问题。同时他们也证明了量子计算机可以解决传统计算机可以解决的所有问题。也就是说，BQP包含P中的所有问题。

但是人们无法确定BQP是否包含NP问题。但如果P问题被证明在可解决的问题类上等价于NP问题，而不考虑其复杂度问题，则可以将NP看作是传统计算机可以解决的所有问题的类。换言之，比较BQP和NP是为了最终判定量子计算机是否优于传统计算机，即经典图灵机。

理想随机数

经典计算机不擅长的一件事是像我们一样翻硬币来生成一个理想随机数，看起来这么简单的一件事计算机居然做不到？然而事实上，计算机所产生的随机数字是确定的。这意味着如果你问同样的问题，你每次都会得到相同的答案。通过算法可以对机器进行编程以生成所谓的“随机”数字，但机器始终受编程的支配。实际上，机器经过特殊和仔细的编程，总可以消除结果的随机性。在一台完全确定的机器上，人们并不能生成任何可以被真正称为随机数字序列的东西，因为机器遵循某种确定的算法来生成它们。通常情况下，这意味着它以一个共同的种子数字开始，然后遵循一个程序。结果可能足够复杂，难以识别模式，但由于它是由一个精心定义的算法规划的数字，产生的并不是真正的随机。因此计算机所产生的随机数也被称为“伪随机数”。一个伪随机数发生器需要一个算法来生成第i个随机数Rand（i）和一个初始值“种子”N0。冯·诺依曼在1946年提出了一个简单的例子：开始取一个2s位的整数N0，称为种子，将其平方，得4s位整数（不足4s位时高位补0），然后取此4s位的中间2s位作为下一个种子数。以此类推，即可得到一系列随机数。这样，当N0=1234时，产生的序列如表7–4所示：

表7–4

如果把生成的随机数除以10000，这样就得到一个介于［0，1］的随机序列：

0.5227，0.3215，0.3362，0.3030，0.1809，0.2724……

冯·诺依曼的算法明显有很大弊端，不仅周期短而且分布不均匀，比如10000平方取中结果就一直为00000了。随后有很多深入的研究给出了更好的伪随机函数发生器。

完全基于确定性逻辑的伪随机数发生器永远不会被视为纯粹意义上的“真正的”随机数源，但在实践中它们通常足以满足要求严格的安全关键应用。实际上，精心设计和实现的伪随机数生成器可以用于安全关键加密的目的，大多数计算机生成的随机数使用伪随机数生成器，这些算法可以自动创建具有良好随机属性的长数字序列，但最终受内存使用量的限制而回归为可重复的序列，因而也不是理想随机数。这些随机数在很多情况下都很好，但还不像用作随机性源头的电磁大气噪声产生的数字那样随机。对于用计算机来模拟的大多数应用场景来说，使用伪随机数是足够的。例如，如果想对大量数据进行随机抽样，只需要将随机数字输入到程序中，使选取样本的位置或多或少地均匀分布。在这种情况下使用伪随机数是完全可以接受的。iPod（苹果公司推出的便携式多功能数字多媒体播放器）“随机”模式下的歌单也是在伪随机顺序下播放的，它的循环模式是可预测的，但这并不妨碍我们使用这个模式享受随机聆听喜爱旋律的美妙。

通过适当的设计，计算机也不是完全不能跳出这个限制。与物理世界的真实随机相结合，机器可以通过多种方式生成真正的随机数。真正的随机数在实际应用中的重要性不容小觑。例如，一个在线扑克网站，如果黑客知道随机数的生成算法和随机种子，就可以编写一个程序来预测将要见到的扑克牌。真正的随机数使这种黑客攻击变得不可能。我们可以依赖自然界来制造真实的随机数，一种方法是测量一些预期随机的物理现象，包括测量大气噪声、热噪声、其他外部电磁和量子现象。例如，在短时间尺度上测量的宇宙背景辐射、放射性衰变和电路所产生的热噪音，经过一定的放大和截取，也能获得真正的随机数。

从天然来源获得随机数速度取决于被测量的物理现象本身。自然发生的“真实”随机数有时候会很慢，我们不得不花费大量时间来收集大量数据，直到收集足够的随机性来满足需求。也可以采用混合方法，在可用时提供从自然源收集的随机性，把这些随机数用作随机种子而触发基于软件的伪随机数发生器。这种方法避免了基于较慢和纯环境方法的随机数发生器的速率限制阻塞行为。利用机器时钟作为随机函数发生器的种子，从而避免相同种子产生相同的随机数，就是这种策略的例子。

混沌

混沌是很早被经典物理和数学发现，但多少被刻意忽略掉的一套理论。从经典数学的角度上看它不那么干净，它告诉你有些东西天生是不确定的，它说小概率可以有大影响。这些是牛顿力学和经典物理不愿意多谈的，虽然经典力学在解决多体问题中早就看到了混沌的存在，但它真正登堂入室是在20世纪60年代之后。尤其是计算机技术发展促使数值运算能力大大加强，让人有信心以模型为基础，利用计算机的数值模拟重现和预测任何现实的事件。然而20世纪60年代人们在对天气的模拟中发现，即使在确定模型的基础上，也能产生非线性的不确定的结果，从而不能准确预言它的结果。

南美洲的一只蝴蝶扇动翅膀也许会引起北美洲的一场风暴，理论上这是可能的。美国气象学家、麻省理工学院教授爱德华·洛伦茨（Edward Lorenz）长期研究天气预报问题，他在计算机上用一组简化模型来模拟天气的演变。他原计划利用计算机的高速运算来提高天气预报的准确性。但是，事与愿违，他的多次计算表明，初始条件的极微小的差异，都会导致计算结果很大的不同。1963年的一天，为了在验算结果的时候省点事，他把输入值0.506127改写为0.506再算一遍。两个数值相差不大，按理说算出来的值也不会相差太大，然而，每一步的计算结果的差异很快以指数形式增长，以至于两个初始值相差不大的输入，没多久以后输出的结果居然有天壤之别。

洛伦茨使用的方程式如下：

$$
\frac { d x } { d t } = \sigma \left( y - x \right) ;
$$

$$
\frac { d y } { d t } = x \left( \rho - z \right) - y ;
$$

$$
\frac { d z } { d t } = x y - \beta z .
$$

这一组方程在计算机里模拟气流的运动，结果对应的点画出来看着很像一只蝴蝶。洛伦茨因此开创了一门新的学科：Chaos，混沌学。有人称它为21世纪继相对论和量子力学后的第三大科学发现。但之后的发展说明，这样的说法多少有些言过其实了。混沌本身的科学魅力在于：长期行为对初始条件有敏感的依赖性。初始条件产生的微小变化被不断放大，对未来将造成巨大影响。正如中国古书所载，“失之毫厘，谬以千里”。蝴蝶效应会受到许多其他因素的干扰，“蝴蝶扇翅”与“风暴来临”绝不是简单的直接因果，而可能是复杂的连续因果。同样的，古代谚语有“钉子缺，蹄铁卸；蹄铁卸，战马蹶；战马蹶，骑士绝；骑土绝，战事折；战事折，国家灭”。这也是非线性放大的例子。

图7-11 洛伦茨发现的混沌效应

虽然混沌的发现和计算机息息相关，混沌现象也揭示了一类计算机无法完成的问题。动力学本身具有不可预测性，任何小的差别在演化了一段时间之后所导致的结果会完全不同。有限容量的计算机在表达数字的时候，不得不采取近似，忽略掉舍去微小的小数点后几位之后的不同，但这点不同会造成大相径庭的结果，而到底哪个会更接近真相，计算机是无法给出判断的。因此，一个混沌系统不能用计算机来精确地计算它长期演化的准确结果，计算值与真实会相差很大。研究表明，这一切不确定性都是系统内在的动力学性质，跟测量精度没太大关系。由此物理学很快发展出来非线性的混沌理论，延伸至分形数学、耗散系统和自组织行为。

量子随机数

创作了“思考者”的艺术家罗丹（Auguste Rodin）说，雕塑作品早就埋在了石头里，我只是负责把它挖出来。这句话引出来一个重要的话题，什么是自由创作，或者什么是自由意志？

• 我们是否因为自己的自由意志创造了这个作品？

• 或者那个作品已经存在了，我只是去除了它周围的石头？如果是真的，这个作品是注定的。

我们无法通过检查证据回答这个问题。在哲学术语中，它“在经验上是无法回答的”。这是哲学家们辩论的东西。宗教人士可能会指出经文支持其中一个结论而不是另一个结论。然而，在物理学中，量子随机性为自由意志提供了启示，甚至它本身可能就是我们具有自由意识的源头。

牛顿给出了经典物理中运动和力、重力定律和其他物理原理的优雅描述，从而去诠释上帝的伟大设计。人们相信，一旦知道了物体此刻的运动状态和受力情况，就可以准确地预言它未来所有的运动状态。小到苹果大到行星，都可以精确地被把控在人类所掌握的数学工具里。在经典物理世界（牛顿物理学）中，可以认为随机性甚至是不存在的。当扔起一枚硬币时，正面或背面的机会被认为是各50%。但我们知道这样的概率统计只是一种方便的模型，它给了我们大概的主意，假设硬币两面均匀，没有其他任何干预，它应该发生什么。现实生活中的硬币在空中的翻转受制于人们用拇指将硬币推入空中的力量，风和气流的存在，以及硬币两面的物理特性，等等，这些因素都是确定的，硬币的运动因此可以由经典物理定律来描述。可以说，所有经典物理所说的随机性，只要经过足够的数据仔细分析，以及有足够的数据采集，精确的数学模型和强大的运算能力，就是具有确定性的。

爱因斯坦因此不喜欢量子力学声称的纯粹随机性。对此他有一个著名的说法：“上帝不掷骰子。”爱因斯坦认为量子系统坍缩到某一个状态上的概率必须像掷硬币一样。在翻转硬币之前，我们只能通过概率来推测结果，正面或反面。在扔到空中之后，结果是由环境来决定的，通过好的数学工具和足够的预先测量，我们总会知道确定性结果。在实践中，如果我们足够多次地翻转硬币，我们将得到一半正面一半反面的结果。这不是因为环境是确定的，而是因为确定的环境不会让硬币的任何一面有优势。

爱因斯坦认为量子力学也必须符合类似的规律。宇宙中存在更深层次的未知规律，必然应该有一套更好的理论来解释量子力学的所有问题，并且预测量子力学所不能预测的新东西，他将其归纳为隐函数理论。因为我们不知道它们是什么，我们能做的最好就是应用概率模型来解释我们的观察结果。但我们怎么能确定是否有我们尚且不知道的隐藏的东西呢？

那么问题就来了，我们所做的事情其发生是注定的，还是由自由意志选择的？当量子波函数坍缩时，它是否注定会因为一个未知的潜在原因而坍缩，正如爱因斯坦所认为的那样？这样的坍缩是否与其他主观和外在的任何影响无关？比如观测者自己的行为？这些问题都启发着我们对自然的自由意志的含义的思考。如果它是伪随机的，那么我们今天的意识是不是很久很久以前就可以被计算和预测，比如此时此刻在想的事情通过足够多的原子在几千年前的状态下就可以计算出来，我们姑且忽略计算复杂性的问题。如果量子随机真的在底层起着作用，那这些行为将永远无法预测，我们是具有自由意识的。

20世纪60年代，英国工程物理学家贝尔（John Bell）提出了检验量子随机性的杀手级证明。贝尔定理最终证实了量子随机没有被更深层次的规律决定。大自然不可预测的自由行为不由先验的可追溯的算法来决定。通过量子坍缩，宇宙不断产生新的信息。在贝尔定理下，经典力学所描述的翻转硬币的机制不再适用于量子力学。在量子世界中，我可以在完全相同的条件下翻转相同的硬币，有时会是正面，有时会是背面，宇宙中没有任何因素决定其随机的结果。

那么，这是说量子随机性导致了我们思维的独立和自由吗？虽然量子随机性作为解释我们的大脑如何工作的理由依然是个大胆的甚至是证据不足的推测，但它确实启发了我们在密码学方面一些有价值的应用，例如它使在线金融交易更为安全。伪随机数生成器生成随机数字串作为交易代码源，甚至可以通过随机性安全测试。但是，如果用于生成这些数字的确定性规则是可以做逆向工程的，即一旦被人知道生成随机数的算法和种子，就可以被破解或者被准确预测。如果系统被黑客入侵，这些信息就会被获取，从而无法保证它的可靠性。相比较而言，因为量子世界确实是随机的，量子随机数发生器将是一种潜在的解决方案。这个一点也不抽象，当你在网上转账时，你的手机会从银行收到一串交易代码来保证转账的可靠性，但这串代码，迄今都还是由伪随机函数生成的，当一个有足够能力的黑客来破解的时候，他可以确定地知道这个数值，从而威胁交易的安全。

牛津大学物理学家罗杰·彭罗斯认为，人类思维的非算法（不可计算）特征，如创造力，源于大脑微管中的量子坍塌。如果他是正确的，我们的大脑正在创造真正新鲜的新信息。但是有一个问题：量子坍缩产生的信息只是随机的，如果没有一定意义和程度上的关联，它们就是随意且毫无用处的。仅凭随机性这些信息无法在创造性思维中产生明显的复杂性，在我们的神经元中随机的嗡嗡作响不会解决哪怕最简单的数学问题或写出一部伟大的小说。会有一群能在打字机上打出莎士比亚著作的猴子吗？只要猴子够多、时间够长，数学上总有机会，但物理上我们没法让大脑的每一个原子的状态都随心所欲地坍缩到什么态上，而我们的行为和意识被这些随机的不良结果控制。要知道只有那一部莎士比亚是有用的，其他的都是废物，而产生这一部的概率是非常非常小的。因此要形成有意义的自由想法和意识，大脑必须为一般目的制定或组织量子坍塌形成的新信息，我们仍然没法解答人的思维中创造力是如何发生的这一问题。我不认为大脑是单纯地以达尔文方式进化出来的，简单机械系统产生不出大脑，生命力是宇宙中元素的一种组织形式，它遵循特定的作用规律，这些规律既不是简单的也不是机械的。

常识？

我们现在知道了：经典理性是不能将所有人类的数学直觉形式化的。如果我们能够成功地形式化它的一部分，这事实上就恰好需要一种新的直觉知识，例如，这种形式逻辑上自洽的知识。人类通过对数据的截断来获得常识的机制和图灵机的停机问题，大概有深邃的关联，人可以知道什么数据可以形成足够有用的常识，而不是无穷无尽地引入新的概念。对于计算机的搜索能力来说，它显然无法得出到底哪里是我们认知获得满足的边界。人类会对自己周围的世界进行逻辑推理，我们在为自己看到的东西建立模型，我们有大量的常识知识来帮助我们发现新的情况。这种建立模型的能力是从哪里来的？是从具体事物和数据中抽象出来的某一线索？更重要的是，人工智能和它们的具象——计算机缺乏常识。