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

无穷长的杆子不会动

有一张无限大的桌子上固定一个三脚支架。把一根无穷长的金属杆的一头固定在三脚架上，另一头伸向无穷远处。金属杆可以绕着三脚架顶端自由地上下转动。假设金属杆和桌子都是牛顿力学中常见的刚体。在一切牛顿力学中合理的前提条件下，神奇的事情发生了，即使只有一端被支撑，这根无限长的金属杆也根本不会动！金属杆和桌子都是无穷坚硬的刚体，杆子一旦动，就会相交，必然有一个会损坏，但刚体的假设又不允许这样的事情发生，唯一的可能就是金属杆与桌面绝对平行。那么我们看到的现象就是一根无限长的金属杆，仅仅靠一个点就可以保持水平！

希尔伯特旅馆

一家旅馆有无穷多个房间，每个房间都住了客人。一天来了一个新客人，旅馆老板说：“虽然我们已经客满，但你还是能住下的。让1号房间的客人搬到2号房间，2号房客人搬到3号房间……n号房客人搬到n+1号房间，你就可以住进1号房间了。”又一天，来了无穷多个客人，老板又说：“不用担心，大家仍然都能住进来。我让1号房客人搬到2号房间，2号房客人搬到4号房，3号搬到6号……n号搬到2n号，然后你们依次住进奇数号的房间吧。 ”

这就是希尔伯特提出的关于无穷大的悖论。虽然人们把它叫作一个“悖论”，它在逻辑上却是完全正确的，只不过大大出乎我们的意料罢了。

意大利数学家伽利略在他的最后一本科学著作《两种新科学》（Two new Sciences）中提到一个问题：正整数集合 {1，2，3，4……}和平方数集合{1²，2²，3²，4²……} 哪个更大呢？一方面，正整数集合里包含了所有的平方数，前者显然比后者大；可另一方面，每个正整数平方之后都唯一地对应了一个平方数，两个集合大小应该相等才对。伽利略比较早地使用了一一对应的思想来研究无限大，可惜没有沿着这个思路更进一步思考下去。最后他得出的结论就是，无限集是无法比较大小的。

说到这里，我们不得不提到德国另一位伟大的数学家康托，他建立了集合论，系统地研究了集合（尤其是无穷集合）的大小，只不过这个大小不是简单地叫作“大小”了，而是叫势（cardinality）。如果两个集合间的元素能建立起一一对应的关系，我们就说它们等势，这也是我们比较集合大小的方式。当我们数大教室里是不是坐满了学生，我只需要把座位和人对应起来。一个座位上坐一个人，而不需要把人数一遍，再把座位数一遍，最后看人数是不是等于座位数。我们只要把每一个数都对应为一个可数的自然数，那么这两个无穷大就是相等的。康托第一次认真研究了无穷的概念，并用了我们前面使用的证明哥德尔不完备定理的类似方式——对角线法，证明了0到1之间的无理数的数量是大于有理数的数量的。即，无理数的无穷多比自然数的无穷多要多，是更高级的无穷大。而“希尔伯特的旅馆”形象地说明了正整数集合和正偶数集合是等势的。一切和自然数集合等势的集合都称为可数集合（countable set），否则就叫作不可数集合（uncountable set）。可数的无穷大是一样大的，即偶数跟自然数一样多，这也跟我们的常识不太一致，但数学上它是对的。

问题是，今天作为人工智能基础的计算机，无论其存储还是内存有多大，都还是有限的，都还是可数的，都不是可以代表实数的无穷大，连可数的无穷大都不是。我们并不能用计算机表达一个真正意义上的无穷大。我们也无法用计算机表达一个无理数，甚至一个无限循环小数，它不得不截断到计算机作为一个物理设备所限制的对数字的表达。用一些特殊的算法，我们可以表达一个非常长的数字，但即使这样，一个无理数也会被截断。我们可以用几何和符号表达π，并且理解它的含义。但在使用计算机的时候，我们不得不用它的近似值3.14，或3.1415927，无论相差有多小，都还是个有限长的有理数，是π的近似值。这些近似很多时候会被忽略，但在有些场景下会被放大，例如随机函数发生器就是一种放大这种细微差异的算法。一个有混沌特性的方程，也可以用来放大这种差异：本来两个输入值是可以忽略掉的，例如3.1415927和3.1415926，但经过这个方程的多次迭代之后算出来的结果就可能是天壤之别了。

机器相对我们人类的数学认知而言，既不能理解甚至表达无穷大，又不能理解甚至表达无穷小。物理设备的有限性妨碍了这些概念在机器表达中的实现。我们可以看到这其中有一些重要的差别，但关于无穷的认知是否是构成机器和人类思维的界限呢？

然而，物理学却给出了一个跟我们已有数学认知不太一致的底层问题，这个问题需要数学表达方式的进一步发展才可能有最终的解决方案。根据量子力学，我们生活的世界，例如时空，也并不是由连续的无穷小构成。从时间上讲，有普朗克时间，光波在真空里传播一个普朗克长度的距离所需的时间，数值大约为5. $3 9 \times 1 0 ^ { - 4 4 }$ 秒，它是最小的时间间隔。同样的，空间也有最小的颗粒，大概是 $1 . 6 2 \times 1 0 ^ { - 3 5 }$ 米。物理上也并不允许存在无穷这样的概念，比如黑洞的密度可以到无穷大，对黑洞的结构现有的物理定律并不能够解释。同样，对宇宙的时间起点，现有的物理理论适用于大爆炸发生后 $1 0 ^ { - 4 4 }$ 秒以后的事，这之前现有的物理规律并不适用，因为又有无穷大。

在物理世界回避哥德尔不完备定理的另一种方式是，审视和考量物理世界是不是只使用到了数学的有限的可判定部分。数学可以存在无限，而物理并不存在无限。只有部分数学的结构和模式存在与物理世界中的对应，物理的相关命题可能都是来自数学命题中基于可判定陈述的那部分数学，而不是全部的数学。

图灵机

人类喜欢秩序、模式和规范。我们对于任何有意义的数字序列都感兴趣。从数拥有多少头家畜中我们发明了自然数，从测量中我们发明了有理数，从几何中我们发明了无理数。对不同的数的操作构成了算法。从古希腊开始的数学的基本认知在其形成很久以后，13世纪的西班牙数学家拉蒙·柳利（Ramon Llull）认为数学逻辑推理可以用人造的机械来实现。16世纪的英国数学家托马斯·霍布斯（ThomasHobbes）认为头脑里的逻辑推理可以表达为数值计算，“我们在无声的思维中加加减减”。在1500年前后，达·芬奇（Leonardo daVinci）设计了一台机械计算机，但他并没有建造出这台机器。更出名的计算机Pascaline是由法国数学家、机械师布莱士·帕斯卡（BlaisePascal）在1642年建造的。在这不久之前，已知的更早的一台可以被称为计算机器的设备是由德国科学家威廉·施卡德（WihelmSchickard）在1623年左右建造的。布莱士·帕斯卡写道：“算数机器产生了明显比所有动物行为更接近思维的效果。”莱布尼茨建造了一个试图对概念而不是对数学执行操作的机械装置，但是其使用范围非常有限。莱布尼茨建造的计算机器确实超过了帕斯卡的，因为莱布尼茨建造的计算器能加、减、乘、求根，而Pascaline只能加与减。从算盘到计算尺，再到机械计算器和计算芯片，人类在计算工具上的探索一直到今天都还没有停歇。图灵的天才之处在于，他认识到，在任何计算器中可执行的任何算法（即任何程序）都可以通用图灵机（Universal Turing Machine，简写为UTM）实现。于是，除了完全由硬件部分决定的计算机速度外，通用图灵机可以做任何计算机可以做的事情。而任何一台计算机都是通用图灵机的某种变体，它们是等效的。

1934年春天，哥德尔在普林斯顿做了一系列讲演。在讲演中，哥德尔引入了一类可以精确定义的可计算函数，他称之为一般递归函数。递归的概念意味着函数在运行的过程中调用自己，事实上，这也意味着无法避免的可怕的自指。这项工作很快成为图灵机的基石。

1936年，英国年轻数学家图灵发表了一篇重要文章《论可计算数及其在判定问题中的应用》，标志着图灵机的诞生。图灵在他的这篇开创性的论文中，提出了著名的“图灵机”的设想。他将逻辑中的任意命题用一种通用的机器来表示和计算，并按照一定的规则推导出结论，其结果是：可计算函数可以等价为图灵机能计算的函数。在这篇文章中，图灵定义了用图灵机可以计算的函数，同时，他也提出了一个论点：“可计算的函数”与“用图灵机可计算的函数”是一回事。换句话说，图灵机能计算的函数便是可计算的函数，图灵机无法计算的函数便是不可计算的函数。同时期，美国数学家丘奇（AlonzoChurch）也得到了相同的结论。“所有计算或算法都可以由一台图灵机来执行”的观点便被称为“丘奇—图灵论题”。

图灵机由四个部分组成：

1.输入集合，一个无限长的存储纸带，带子由一个个连续的存储格子组成，每个格子可以存储一个数字或符号；

2.输出集合，一个读写头，读写头可以在存储带上左右移动，并可以读、修改存储格上的数字或符号；

3.内部状态存储器，该存储器可以记录图灵机的当前状态，并且有一种特殊状态为停机状态；

4.状态转移表（固定的程序指令），指令可以根据当前状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作（左移还是右移），并改变状态存储器的值，令机器进入一个新的状态或保持状态不变。

整台图灵机的核心在于读写头的状态转移表，它指示着读写头的状态和当前读写头正对格子的符号如何变化。状态转移表就是由一系列这样的简单规则组成的，它相当于图灵机的源代码。

图灵机的运转和我们笔算的思维过程非常相似：在每个时刻，我们只将注意力集中在一个地方，根据已经读到的信息移动笔尖，在纸上写下符号；而指示我们写什么和怎么写的，则是早已背好的九九乘法表，以及简单的加法。如果将一个笔算乘法的人看成一台图灵机，纸带就是用于记录的纸张，读写头就是这个人和他手上的笔，而状态转移表则是笔算乘法的规则，包括九九表、列式的方法，等等。这种模式似乎也适用于更复杂的机械计算任务。如此看来，图灵机虽然看起来简单，但它足以作为机械计算的定义。

下面我们通过一个小例子来了解下图灵机到底是如何进行计算的。这个例子比较简单，我们将在空白的纸带上打印1、1、0三个数字。

假设有一条无限长的纸带，纸条上有一个个方格，每个方格可以存储一个符号，纸条可以向左或向右运动。

图灵机进行下面3个基本的操作：

1.读取指针头所指的方框里的符号。

2.修改方框中的字符。

3.将纸带向左或向右移动，以便修改其临近方框的值。

首先，我们向指针头指向的方框中写入数字1：

接着，我们让纸带向左移动一个方框：

现在，我们再往指针头指向的方框写入数字1：

接着，我们继续让纸带向左移动一个方框，并写入数字0：

这样我们就完成了一个简单的图灵机操作。

用图灵机完成异或操作