人工智能伦理

图1.133 邱奇

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

寻找算力更强的机器

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

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

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

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

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

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

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

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

图1.134 图灵机、NTM、PTM、QTM在多项式时间内解决判定问题的能力

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

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

量子计算

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

图1.135 美国物理学家理查德·费曼首先提出量子计算机的构想

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

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

图1.136 2004年至今，姚期智在清华大学任教，推动了国内理论计算机科学的发展

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