1.1.4　计算能力

1936—1937年，艾伦·图灵（Alan Turing, 1912—1954）在论文《论可计算数及其在判定问题上的应用》[27]里提出了一个抽象的计算装置——确定型图灵机（deterministic Turing machine,DTM），简称图灵机。如今，它已成为可计算性理论（computability theory）研究的基础。

读者可以把图灵机直观地想象成带一个读写头和一条无限长格带的自动打字机，如图1.132所示，格带的每个格子里至多有一个字符。一般地，格带字符和机器状态的集合都是有限的。这台打字机严格地遵循着事先定义好的规则（不妨称之为“程序”）行事，别看它结构简单，人类能用算法做的所有事情都可以通过它来实现。

1937—1938年，图灵在普林斯顿大学攻读博士学位，导师是美国数学家、λ演算之父阿隆佐·邱奇（Alonzo Church, 1903—1995）。作为计算装置，λ演算与图灵机是等价的，二者可以相互模拟。前者强调变换规则的操作，后者侧重计算机器的直观。1936年，邱奇比图灵的论文稍早几个月给出了判定问题（Entscheidungs problem）的否定证明。邱奇证明了，找不到一个通用的算法来判定任意两个λ表达式是否等价。

寻找算力更强的机器

图灵机有许多扩展，但它们的计算能力与图灵机等价[28]，即不考虑时间复杂度，在这些计算装置上可计算的函数，在图灵机上也是可计算的。图灵机最经典的扩展包括以下几种。

　如果状态转移函数是多值的，则该计算装置被称为非确定型图灵机（nondeterministic Turing machine, NTM）。显然，DTM是NTM的特例。

　如果转移函数是随机的（满足条件：从每个非终止状态转出的所有情形的概率之和归一），则称之为概率图灵机（probabilistic Turing machine,PTM），它是对NTM的推广。

　如果图灵机的状态是量子态，状态转移函数是酉变换，格带上每一比特变成了“量子比特”，则称之为量子图灵机（quantum Turing machine, QTM）[29]。

很多实际的计算问题带有时效限制，如预测明天的天气情况或股票价格，我们不可能完全抛开时间复杂性只在可计算性的水平泛泛地谈论机器的计算能力。长期以来，人们关心这样一个问题：是否存在一个在多项式时间内DTM无法解决而NTM可解决的判定问题（decision problem）(20)？

1．我们把在多项式时间内DTM和NTM能解决的全体判定问题构成的类分别记作P和NP（nondeterministic polynomial），显然有P⊆NP。因此，上述问题也可以表述为：是否NP⊆P？简称为P/NP问题。它是理论计算机科学中尚未解决的难题之一，学界一般认为P是NP的一个真子类。

2．类似地，我们分别用BPP（bounded-error probabilistic polynomial）和BQP表示PTM和QTM以某个小的错误概率（例如，1/3）解决的判定问题类。结果BPP⊂BQP已经被证实[30]，是否有BPP⊆P是一个未解之谜。

那些PTM在多项式时间内以低于1/2的错误概率解决的判定问题类记作PP（probabilistic polynomial）。通常认为P、NP、BPP、BQP、PP的关系如图1.134所示。

虽然计算能力等价，但在算法复杂度方面，PTM/QTM与DTM有着深刻的不同。打个比方，PT-M/QTM是个做题快的学生，而DTM是个做题慢的学生。如果考试没有时间限制，两个学生能力相当（即计算能力等价）而得到同样的分数。但如果考试有时间限制，DTM的表现就不如PTM/QTM了。

人类一直在寻求算力更强（即在多项式时间内能解决更多判定问题）的计算装置，量子计算机几乎已经呼之欲出了。

量子计算

“天下武功，唯快不破”。当量子计算机（quantum computer）成为新一代的计算工具，它的强大算力将助力人工智能突破计算瓶颈，以此弥补算法上的不足。譬如，一个300量子比特的寄存器可同时存储2300（比已知宇宙中所有原子的数量还多）个状态的叠加。按照美国物理学家理查德·费曼（Richard Feynman, 1918—1988）的设想，只有用量子的方式才可以模拟复杂的微观世界。传统的图灵机在某一时段内只能存储和处理一个状态（即一个长度为n的0,1串），而量子计算机理论上是一个按照量子规律运行的图灵机（即量子图灵机），则可同时处理2n个状态的叠加，其中n是（量子）比特[29]。

虽然图灵机和量子图灵机在计算能力上等价，但它们在一些具体问题上的算法复杂度是有巨大差别的。打个比方，图灵机和量子图灵机与台下的观众握手，前者一次只能握一人，后者一次就握遍了。

1993年，计算机科学家姚期智（Andrew Yao, 1946—　）首次证明了量子图灵机模型与量子电路模型的等价性[31]。这两类模型各有特点，前者对计算复杂性理论颇有价值，后者有助于直观设计量子计算模型，姚期智的工作可谓打通了量子模型的任督二脉。2000年，姚期智因为在密码学、计算复杂性理论及量子计算等方面的杰出工作而获得图灵奖。

强人工智能也许正如英国物理学家罗杰·彭罗斯（Roger Penrose, 1931—　）在《皇帝新脑》一书里预测的那样，存在大量不可计算的情形，因此不可能在图灵机上实现[7]。其实，图灵早就意识到了这一点[8][9][10]。除了可计算性的问题，强人工智能还有计算复杂性的问题。人们坚信有在多项式时间内超越图灵机的计算装置，目前虽没能证明，但量子计算是最有希望的备选之一[30][32]。

量子算法是量子计算的主要研究内容之一。有三个里程碑式的量子算法，分别涉及整数的素因子分解、搜索和求解线性方程组。

　 1994年，美国计算机科学家、应用数学家彼得·休尔（Peter Shor, 1959—　）提出素因子分解的量子算法[33]，时间复杂度是O(n2(logn)(loglogn))。相比经典算法的复杂度O(exp{n1/3(logn)2/3})，休尔算法的加速效果是非常明显的。

　从n个元素中找出某个特定的对象，逐个搜索平均需要n/2次。1996年，印度裔美国计算机科学家洛夫·格罗弗（Lov Grover, 1961—　）提出一个量子搜索算法[34]，把复杂度降低到，格罗弗算法只需做次搜索即可。

　利用经典的高斯消元法求解线性方程组A_n×nx=y的时间复杂度是O(n3)。2009年，三位计算机科学家阿拉姆·哈罗（Aram Harrow）、阿维那坦·哈西迪姆（Avinatan Hassidim）、赛斯·劳埃德（Seth Lloyd,1960—　）提出了一个求解线性方程组的量子算法[35]，时间复杂度只有O(log₂n)，被称为HHL算法。

理论上，量子计算机有模拟任意自然系统的能力。随着出现更多的量子算法及其应用，可以预见，量子人工智能（quantum AI）、量子机器学习在生物制药、化学工程、天气预报、认知计算等传统方法捉襟见肘的复杂应用场景将大有作为。届时，量子计算机将有能力处理具有真实意义的复杂系统（complex system）(21)，进而揭示记忆、情感、语言、智能的本质。