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

a、b代表两个二进制变量。那么它们的异或关系（计作a⊕b）是，如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。

接下来我们尝试一个稍微复杂点的操作，我们尝试对1、1、0三个数做一个异或操作，将110变为001。要让图灵机完成计算，就类似于向图灵机输入表7–1中的操作指令，这些指令组成一个小程序。

我们假设图灵机纸带现在的状态如下：

现在读取到的符号是0，按照操作指令，我们应该往方框写入1并向右移动一个方框：

1

现在读取到的符号是1，按照操作指令，我们应该往方框写入0并向右移动一个方框：

类似地，现在读取到的符号是1，我们重复相同的操作。

最后，我们读取到了一个空白字符，图灵机不做任何操作。按照复杂一点的计算机理论，异或操作可以是通用算法的基础，即它可以组合成各种复杂的算法。我们使用图灵机成功完成了异或操作，理论上来讲也就可以完成加法、减法、乘法、除法操作，只不过是实现的步骤复杂些而已。

我们再看一个稍微复杂一点的例子。我们把读写头当作一只能顺着纸带爬的虫子，它有两个状态，吃饱和饥饿。

1.虫子所在一个无限长的纸带上，这个纸带被分成了若干小的方格，而每个方格都只有黑和白两种颜色。纸带的片段如图7–7所示：

2.虫子根据当前所在格子的颜色查表做出行动。

3.每一步虫子可以向右移动一个格子或向左移动一个格子。

4.虫子的操作程序为：黑色有食物，虫子吃到食物右移一格，白色是空白区，没有食物左移一格，即：

表7–2 虫子的操作程序

在这个情况下格子的颜色是虫子的输入信息，集合为：{黑色，白色}，操作指令：{右移一格，左移一格}。

从图7–7中“开始”位置开始，虫子会怎么移动呢？

1.开始是黑色，虫子右移一格，到达第2格；

2.第2格黑色，虫子右移一格，到达第3格；

3.第3格黑色，虫子右移一格，到达第4格；

4.第4格白色，虫子左移一格，回到第3格；

5.第3格黑色，虫子右移一格，到达第4格；

6.第4格白色，虫子左移一格，回到第3格；

7.……

可见，虫子会在这条带子上的第4格和第3格之间来回移动循环不止，进入死循环。

我们假设一个复杂点的情况，虫子会有饥饿、吃饱两种状态，食物可以被虫子吃掉或种植。假设黑色方格是有食物，虫子可以吃掉它，虫子就会感觉饱了。当读入的信息是白色方格的时候，虽然没有食物但它仍然维持吃饱状态，只有当再次读入黑色方格时它才会感觉饥饿，这并没有实质的道理，仅是规则而已。

我们在该设定中改进下模型：

1.虫子所在格子为黑色时

（1）如果虫子处于吃饱状态，虫子不吃食物，格子还是黑色，虫子左移一格，虫子状态变为饥饿；

（2）如果虫子处于饥饿状态，虫子吃掉食物，格子变成白色，虫子不动，虫子状态变为吃饱。

2.虫子所在格子为白色时

（1）如果虫子是吃饱状态，虫子不吃食物，格子还是白色，虫子右移一格，虫子仍为吃饱状态；

（2）如果虫子是饥饿状态，虫子种植食物，格子变为黑色，虫子不动，虫子仍为饥饿状态。

那么，虫子的操作程序如表7–3：

表7–3 改进后的虫子操作程序

在这种情况中，输入集合为{黑色，白色}，输出集合为{左移一格，右移一格，吃掉食物格子变白，种植食物格子变黑}，虫子内部状态{吃饱，饥饿}。

假设虫子初始是饥饿状态，从图7–8中“开始”位置启动程序：

图7–8

1.“开始”格是黑色，虫子为饥饿状态，吃掉食物开始格子变白，虫子不移动，虫子新状态为吃饱；

2.“开始”格为白色，虫子为吃饱状态，虫子右移一格，到达第2格，虫子状态仍为吃饱；

3.第2格为白色，虫子为吃饱状态，虫子右移一格，到达第3格，虫子状态仍为吃饱；

4.第3格为白色，虫子为吃饱状态，虫子右移一格，到达第4格，虫子状态仍为吃饱；

5.第4格为黑色，虫子为吃饱状态，虫子左移一格，到达第3格，虫子新状态为饥饿；

6.第3格为白色，虫子为饥饿状态，虫子要停留一下种植食物，格子变黑，虫子状态仍为饥饿；

7.第3格为黑色，虫子为饥饿状态，吃掉食物第3格变白，虫子不移动，虫子新状态为吃饱；

8.第3格为白色，虫子为吃饱状态，虫子右移一格，到达第4格，虫子状态仍为吃饱；

9.第4格为黑色，虫子为吃饱状态，虫子左移一格，到达第3格，虫子新状态为饥饿；

10.……

我们发现，这个程序似乎又在第3格和第4格之间无限循环起来了。图灵发现了这个问题，那么能不能也做一台超级算法机器来让它自动判断任何一个图灵机是否能进入无限循环呢？

1936年图灵在他那篇著名的论文中指出形式逻辑系统和通用图灵机之间的等价性。一台图灵机执行算法的行为和一个人由前提到结论而进行演绎推理所遵循的逻辑的、一步一步的推理之间的对应。简言之就是，当给定任何一台具有无限记忆的数字计算机C时，我们可以找到一个形式系统F，使C的可能输出与F中可能的定理是一致的，反之亦然。借用这种等价性，图灵用计算机理论术语将哥德尔不完备性问题重新表述为图灵不停机问题。他证明这两个问题在逻辑上是等价的。

哥德尔不完备定理

对于任何自洽的、声称要判定所有算术陈述的，即证明或否定它们的形式系统F，都存在一个算术命题，在该系统中既不能证实，也不能证伪。因此，形式系统F是不完备的。

图灵不停机定理

对于任何声称要判定所有图灵机程序是否停机的图灵机程序H，都存在一个程序P和输入I，使得程序H不能判定处理数据I时，P是否会停机。

图灵机的意义——探索计算的极限

既然图灵机如此简单，能不能将它“升级”，赋予它更多的硬件和自由度，使它变得更强大呢？比如说，让它拥有多条纸带和对应的读写头，而纸带上也不再限定两种符号，而是三种、四种甚至更多种符号？的确，放宽限制之后，在某种程度上，对于相同的任务我们能设计出更快的图灵机，但从本质上来说，“升级”后的图灵机能完成的任务，虽然也许会慢点但原来的图灵机也一样能完成。也就是说，这种“升级”在可计算性上并没有实质性的突破，放宽限制后的机器能计算的，原来的通用图灵机也能完成。既然计算能力没有质的变化，无论采取什么样的结构，用多少种符号，都还是台图灵机。

图灵机的核心在于它的简单。这给物理上实现一台真实可用的并且可以解决“任何可描述问题”的机器铺设了道路。对于工程师而言，只要给出状态转移表，在现实中用机械建造一台图灵机并非什么难事。数学家冯·诺依曼就在图灵机模型的基础上提出了奠定现代计算机基础的冯·诺依曼架构。这种架构以运算器为中心，输入输出设备和存储器之间的数据传送通过控制器完成。从第一台每秒可以进行数千次计算的埃尼阿克（ENIAC）计算机起，到至今每秒可以进行数亿亿次运算的中国神威·太湖之光超级计算机，现代计算机的发展依旧遵循着冯·诺依曼体系。从20世纪40年代到今天，以图灵机为基础的计算机，已经深入到我们生活中的每一个角落。没有图灵机，现代人类简直无法生存，而图灵机恰恰是人工智能的基础，无论人工智能有多么雄伟壮阔的图景，它都还是一台图灵机，无非是复杂了一点，计算速度快了一点。

但我们很快就会有新的问题，是否每一个问题都可计算？会不会出现像逻辑中的悖论一样有无法判定的问题？图灵为了解答这个问题，基于他设计的能够模拟所有计算的机器，证明了：这个机器在有限时间内能够执行完毕的问题便是可以判定的问题，这个机器无法在有限时间内执行完毕的问题便是不可以判定的问题。而且由于哥德尔不完备定理的存在，图灵机中一样存在不可判定问题，而且无法避免。

图灵机模型是目前为止应用最为广泛的经典计算模型，没有之一。除了我们将要讨论到的量子计算的一些迹象之外，目前尚未找到其他计算模型可以计算图灵机无法计算的问题。图灵停机问题开启了可计算性理论的序幕，这是计算学科最核心的理论之一。图灵也提出了可以用计算机解决的问题的判定方法，为计算机编程语言的发展奠定了基础。

通用图灵机是现代通用计算机的理论原型，为现代计算机指明了发展方向，肯定了现代计算机实现的可能性。1936年，冯·诺依曼再次慧眼识英雄，就像他高度评价哥德尔一样，他高度评价了图灵。而正是冯·诺依曼给这个领域取名为“可计算性”。判定问题有了精确的数学表述之后，立即在数学基础乃至整个数学界中产生了巨大的影响。因为这时一些不可判定命题的出现，标志着人们在数学历史上从另外一个角度认识到：有一些问题虽然有答案，但是不可能找到算法解的。在过去，人们一直模模糊糊地觉得，任何一个精确表述的数学问题总可以通过有限步骤来判定它是对还是错，是有解还是没有解。找到不可判定问题再一次说明用有限过程对付无穷的局限性，它从另外一个角度反映了数学内在的固有矛盾。一旦算法的精确定义由图灵机完成，人们同样认识到这躲不过哥德尔不完备定理的影响，可计算性和不完备性这两个概念是紧密联系在一起的。

用图灵机来模拟生命

数学家约翰·康威（John Conway）在1970年发明了著名计算机程序“康威生命游戏”，“康威生命游戏”具有图灵机的普适性，可以模拟任何其他生命游戏规则系统。这个生命游戏由一些基于简单数学规则的元细胞组成，它能模拟出细胞的生、死以及繁殖的过程。“康威生命游戏”的基本思想是给定一个初始构型，然后观察该构型按照“康威生命游戏”的基本规则如何变化（对应于我们前面所讲的图灵机的状态转移表：程序）。

生命游戏的基本规则如下：

1.元细胞分布在规则划分的二维方形网格上；

2.元细胞具有0、1两种状态，0代表“死”，1代表“生”；

3.一个元细胞下一个时刻的生死由本时刻本身的生死状态和周围8个邻居的状态决定，即：

对于活的元细胞：