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

（1）生存：如果该元细胞的邻居中有2个或者3个元胞是活的，那么它将继续生存下去；

（2）死亡：如果它的邻居有4个及以上元细胞是活的，那么它将死于拥挤；如果它的邻居只有一个或者没有活的元细胞，那么它将死于缺乏交流。

对于死的元细胞：

繁殖：如果它的邻居有3个元细胞是活的，那么它将变成活的元细胞。

不难用任何今天的计算机语言来在计算机上实现康威的生命游戏，你可以看到一个初始的形状的元细胞组合体（元生物）可完成移动、吞噬、甚至繁殖等基本生命的动作。

图灵机所不能够

既然一切只是效率问题，无论从算法上看，还是从硬件基础的进步和高效上看，人工智能都不会解决图灵机解决不了的问题，无论如何，到今天为止，人工智能还是基于图灵机来实现的。所以，要看人工智能哪些事情是做不了的，还是回到图灵机的基础问题上来。图灵机做不了的事情，无论今天的计算机如何强大，也都做不了。

希尔伯特提出过著名的希尔伯特规划，即给定足够的公理，运用机械推导，能否对所有合法表述的表达式提供正误判断。这个形式数学主义者所怀的梦想被哥德尔无情地击碎了。虽然梦不在了，但有新的思路可以尝试。是否存在能在原则上一个接一个解决所有数学问题的某种一般机械步骤？那么问题的关键在于什么是“机械推导”，图灵给出了他的解决方案，并从此打开了新世界的大门。

有了图灵机，对于任何数学问题我们都可以写一个程序，如果它在有效时间内能够判定命题为真的话就停机输出1，如果能够判定命题为假的话也可以停机输出0。如果我们能够证明这是个普遍的办法，那就可以解决一切数学问题了。这是不是很熟悉？希尔伯特正是想这么做的。我们假设这样做是可以的，即，我们能够找到这样一个在图灵机上可以实现的普适性的算法。

停机问题

当我们设计了能够解决可描述问题的通用图灵机的时候，并且设计了它的输入输出和运算机制，一个自然的问题是：一台图灵机什么时候会停下来呢？假设给它一个计算机程序的源代码，也给它所有程序要用的数据、文件、硬盘、DVD（数字通用光盘）等等，所有它处理时需要的东西。它能告诉我程序最终能够输出我们需要的结果吗？并且在工作完成之后，程序是退出，还是会永远运行下去不会停止呢？换句话说就是，对于它会不会停止这个问题，仅仅检查程序和数据本身，是不是足以让它回答是或否呢？

更严格地说，会不会停机并不是图灵机本身的属性，它跟纸带的初始输入也有关系。对于同一台图灵机，不同的纸带输入也可能导致不同的结果和行为。比如说，我可以设计一台图灵机，它的任务只有一个：一步一步向右移动，寻找输入中的第一个1。如果输入纸带上全是0的话，那么，这台图灵机自然不会停止；但只要纸带上有一个1，那么它就会停止。所以，真正严谨的问题是：给定一台通用图灵机以及一个输入k，如果我们将k输入通用图灵机，然后让通用图灵机开始运行，这时通用图灵机是会不停运转下去，还是会在一段时间后停止？是否存在一个算法，能够在有限时间内判定一对（算法，输入）的组合是否停机，我们称之为图灵停机问题。这个问题之所以重要，是因为我们最终将证明通用图灵机范畴之内不存在这样一个算法，而人脑又能通过在系统之外的洞察判定这一对（算法，输入）的组合是否会停机，我们跟它们不一样。

乍看起来，停机问题并不难。既然我们有通用图灵机这一强大的武器，那么只需要用它一步步模拟通用图灵机在输入k上的计算过程就可以了。如果模拟过程在一段时间后停止了，我们当然可以得出“通用图灵机在输入k上会停止”这个结论。问题是，在模拟过程停止之前，我们不可能知道整个计算过程到底是不会停止，还是可能会在3分钟后停止，可能要等上十年八载，更有可能永远都不会停止。换句话说，用模拟的方法，我们只能知道某个程序在某个输入上会停止，但永远不能确定那些不停止的状况。所以说，单纯的模拟是不能解决停机问题的。

我们将编码为n的图灵机称为Tn，则存在一个算法，能够模拟任何其他的图灵机，我们称之为通用图灵机，用UTM表示。其运行性质为，输入数据分两个部分，n和k， $U \left( n , \mathbf { \alpha } _ { k } \right) = T \mathbf { \hat { n } } \left( \mathbf { \beta } _ { k } \right)$ 0

假设存在这样一个算法H，总能够在有限时间内判定一对（算法，输入）的组合是否停机，并且输出0或1。

H(n, k) =0, $T _ { n } ~ ( k )$ 不停机；1, $T _ { n } ( k )$ 停机；

接下来我们通过将两个算法结合起来生成一个新的算法 ${ \cal Q } \ ( \ n$ k）：

1. 先通过 $H \ ( \ n , \ k )$ 判定是否停机；

1. 如果停机，则输出 $\mathit { { { T } } _ { \mathrm { { h } } } } \left( \mathit { { { k } } } \right)$

1. 如果不停机，则输出0。

新算法可以表达为 $Q ( n , k ) = I _ { n } ( k ) \times H ( n , k ) = U ( n , k )$ $X H ( 1 1 , h )$ 接下来，定义 $T _ { \parallel } \left( k \right) = 1 + \hat { \mathcal { Q } } \left( k , k \right) = 1 + T _ { k } \left( k \right) \times H \left( k , \right.$ k),则当计算 $T _ { \parallel } \left( w \right)$ 时，会遇上一个不可调和的矛盾：

$$
T _ { \mathfrak { w } } ( \mathfrak { w } ) = \mid + T _ { \mathfrak { w } } \left( \mathfrak { w } \right) \times H \left( \mathfrak { w } , \mathfrak { w } \right)
$$

如果 $\begin{array} { r l } { T _ { \mathbb { W } } } & { { } \big ( \mathrm { ~ w ~ } \big ) } \end{array}$ 会停机，那么最后得到的结果为 $T _ { \mathrm { W } } \ : \ : \ : \mathrm { ~ ( ~ w ~ ) ~ = ~ 1 ~ } \ : \ : + \ :$ $\mathit { \Delta } \mathcal { T } _ { \mathrm { { W } } } \ : \ : \left( \begin{array} { l } { \phantom { - } } \\ { \phantom { - } \mathcal { W } } \end{array} \right)$

如果 $\mathit { \Delta } \mathcal { T } _ { \mathbb { W } } \left( \mathit { \Omega } _ { \mathbb { W } } \right)$ 不会停机，那么会和其定义冲突，因为等式右边的表达式总能在有限时间内停机。

所以不存在算法H，能够在有限时间内判定一对（算法，输入）的组合是否停机。

似乎是个特例，但停机问题涉及的范围可能要比我们想象中的复杂得多。

程序员碰到的最常见的问题就是一个程序写完运行后会陷入死循环。比如：当x>2，让x除以1，如果x一开始就比2大，这个语句就会死循环。这个例子很简单。再举个例子，我们可以编写一个程序GC，它遍历所有≥4的偶数，尝试将这样的偶数分成两个质数的和。如果它遇到一个不能被分解为两个质数之和的偶数，它就停机并输出这个偶数；否则，它就一直运行下去。用现代的工具编写一个演算GC的程序，对于计算机系的学生最多只能算一次大作业，不是什么困难的事。

从第一个数字4开始，每一个需要被检验的数字都是一个偶数。而每一个小于这一偶数的质数都有特定的判定方法，即用2来除这个数，一直到比这个数都小的自然数都除过了，如果能被整除，那么它就不是一个质数，如果都不能整除，那么它就是个质数。那么这个程序能够停止吗？事实上，如果它真的能停止的话，哥德巴赫猜想就被证否了。因为我们真的找到一个反例，一个偶数，不能被写成两个质数的和。

问题并不复杂，而且对任何现代的计算机语言而言，描述它的算法都很简单。上面的语句描述的是著名的哥德巴赫猜想，三百年来它都是不可证明的。然而，GC是否会停止可是牵涉到了哥德巴赫猜想。如果哥德巴赫猜想是正确的，每个大于4的偶数始终都能分解为两个质数之和的话，那么GC自然会一直运行下去，不会停机；如果哥德巴赫猜想是错误的话，必定存在一个最小的反例，它不能分解为两个质数之和，而GC在遇到这个反例时就会停机。也就是说，GC是否永远运行下去，等价于哥德巴赫猜想是否成立。如果我们能判定GC是否会停止，那我们就解决了哥德巴赫猜想。程序仅仅检查这个语句“每个大于2的偶数能够用两个质数之和表示”是否为真，然后移到下一个偶数。对所有前4000万亿个数检查下来，它都是正确的，但我们仍然没有得到一个真正的数学证明。关键在于，知道这几行代码是否运行停止就等于是否可以证明哥德巴赫猜想！如果猜想是真则软件不会停止，检查所有直到无穷大的数，都不会发现任何一个破坏这个规则的数；如果猜想为假，那软件就会在找到第一个破坏规则的数之后停止。

很明显图灵机所执行的程序只是另一个运用逻辑形式系统的方法。我们也能用语言或者软件，甚至更低级别的纯粹的哥德尔风格的配数，如果想的话。然而，基本上，几行语句就能够表示数学上最基础的问题。知道什么时候程序会停止从而给出我们想要的结果，和证明这类难题一样困难。我们甚至可以重新用哥德尔的递归函数来写这个程序，然后写这样一个语句“这个函数在某个数之后停止是否为真”。这同样是又一次证明了这个语句和证明哥德巴赫猜想是一样的。

哥德巴赫猜想目前是数学上一个很著名的不可解问题。或许某天有人会真正找到证明；但也很可能是某人证明这个猜想是不可判定的，即在算术领域里不存在对哥德巴赫猜想的证明。这样的证明不可思议的难，但类似的问题也曾经被证明过。哥德尔不完备定理事实上说明了关于它的证明有可能是不存在的，至少在算术范畴内是不存在的。

数学中的很多猜想，比如说3x+1猜想（任取一个自然数，如果它是偶数，我们就把它除以2，如果它是奇数，我们就把它乘3再加上1。如果反复使用这个变换，我们就会得到一串自然数，这串自然数的最后一个是1）、黎曼猜想等，都可以用类似的方法转化为判断一个程序是否会停止的问题。如果存在一个程序，能判断所有可能的图灵机在所有可能的输入上是否会停止的话，那么只要利用这个程序，我们就能证明一大堆重要的数学猜想。我们可以说，停机问题比所有这些猜想更难更复杂，因为这些困难的数学猜想都不过是一般的停机问题的一个特例。如果停机问题可以被完全解决，我们能写出一个程序来判断任意图灵机是否会停机的话，那么相当多的数学家都要丢饭碗了。

然而，图灵证明了判别通用图灵机运行是否可以停机的图灵机并不存在，图灵机停机问题是个不可计算问题。这同时说明了在数学和信息学中，并不存在一个终极理论或者算法来解决所有问题，总有些问题是不可计算的。图灵对于停机问题不可解决的证明是决定性的。没有一个程序仅靠检查另一个程序的源代码，就能够决定它是会停止运行，还是会永远运行下去的问题。这是从图灵机的角度对哥德尔证明的重新表述。这个证明与哥德尔的证明是相同的，只是更容易理解，这个证明可以表示成简单的代码，而不是令人费解的运行在《数学原理》逻辑语法上的函数。

而哥德尔第二不完备定理告诉我们，不存在一个通用算法来判别哪些问题是自洽的。如果一个语句是不可判定的，你不能作弊，只能写一个程序去检查它。程序虽然可以轻易表达这个陈述，但它可能会用无尽的时间去完成它的工作。只要语句的不可判定无法证明，你就证明不了程序是不是会停止。

停机问题如此复杂，机械的计算看起来没有足够的力量来完全解决它。但要想严格证明这个结论，似乎仍要求助于深藏在哥德尔不完备定理的证明中，那魔法般的自指。图灵机版本的关于不完备的证明，会让这种自指的复杂性扩散到图灵机所覆盖的所有问题中，即，任何可描述算法。这是个细思极恐的推论，因为我们还有个策略是，像鸵鸟一样明知道哥德尔不完备定理无法避免，但仍幻想它毕竟指的是极少数特殊情况下的问题，只要视而不见就可以了。但哥德尔不完备定理通过图灵机延伸到所有可描述问题，即，我们可以了解并说清楚的所有问题；不可描述的问题，是我们的未知问题，已知问题，我们都可以描述了。这样，哥德尔的不完备定理，也随着图灵机延伸到我们用现代计算机所涉猎的所有问题，这当然也包括人工智能。

NP不可解问题

1956年，哥德尔在给冯·诺依曼的信里讲到他对计算复杂性的认识。

哥德尔说，对命题证明中的每个公式F和每个自然数n，人们很容易就能构造图灵机来判定F是否有长度为N的证明。给定这样一个机器，人们就能定义一个F和n的函数ψ，使得 $\boldsymbol { \Psi } ^ { \mathrm { ~ ~ } } \left( \begin{array} { l l } { \boldsymbol { F } , } & { \boldsymbol { n } } \end{array} \right)$ 是机器判定所需的步骤N，对于F而言，N增长有多快？如果增长是n或 $\boldsymbol { \mathit { n } } ^ { 2 }$ ，那将非常有意义。哥德尔对这个问题的认识再次证明了他对什么是最基本问题的直觉把握，这事实上是计算复杂性问题的最早表述，也成为计算机科学的另一个核心未解的问题。

对于一个算法，人们能够分析出运算时间与数据量之间的大致函数关系，这个关系被称为时间复杂度，它定量描述了该算法的运行时间。

假设有n个数要排序。一个初级的冒泡排序算法所需时间与 $\boldsymbol { \mathit { n } } ^ { 2 }$ 成正比，快一点的算法所需时间与 $n { \mathrm { / } } o g \ ( n )$ 成正比。最不实用的算法就是输入的数字随机排列，直到出现完全有序的情况为止，这被戏称为“猴子排序法”（Bogo-sort）。前两个算法的时间复杂度分别记为$\textit { O } \textsuperscript { ( n ) } , \textit { O } \textsuperscript { ( n l o g n ) }$ ，最后一种平均时间复杂度则达到了$O \ ( n \cdot n . ^ { \prime } )$ 。前两种算法的复杂度是n的多项式函数，最后一种算法的复杂度是n的阶乘。当n特别小时，多项式级的算法已经快过指数级的算法；当n非常大时，人类根本看不到指数级复杂度算法结束的那天。如果问题存在多项式级复杂度的算法，这个问题就是P（polynomial，即多项式）问题。这意味着，即使面对大规模数据，人们也能相对容易地得到一个解。对应的，NP问题，不确定为是否是P问题的问题。 $M ^ { p }$ 问题指的是，能在多项式时间内检验一个解是否正确的问题，但找到这个解通常需要很长时间和计算量。比如电子邮箱账户的密码，能在多项式时间内验证一个字符串是否等于这个密码，但需要跟密码位数l成 $\boldsymbol { K } ^ { \mathrm { d } }$ 数量级的猜测（K是键盘上的有效字符数），所以“破译密码”是一个NP问题。

图7–10中最小的一个框P代表的是传统计算机所能快速解决的一系列问题，而NP则是传统计算机不一定能够迅速解决，但是如果提供一个答案，就可以快速验证答案的所有问题。而NP继续向外延伸是PH（polynomial hierarchy）问题，也就是所谓的“多项式层次结构”问题，它可以被理解为传统计算机在现在和未来可能解决的所有问题的总和。我们将在下一章里结合量子计算来说明量子NP问题。数学中一个著名的问题在于证明NP问题是否最终等价于某一类P问题。如果一旦证明它们是等价的，即有些现在看起来困难的问题迟早能找到有效的解。这绝不是个好消息，如果P问题等于NP问题了，很多基于计算复杂性的算法，比如通用密码或区块链都会不再安全。越来越多的科学家相信它们不等价。但事实上最近的神经网络算法确实使得一些以前我们认为的NP问题有了更加简洁的解法。比如我们曾经认为围棋是个NP问题，但事实上，AlphaGo在一定程度上给出了一个相对简单的解法。