第 2 章 图灵的计算王国

第 2 章 图灵的计算王国

张江

图灵机(Turing Machine)与计算理论(Theory of Computation)是人工智能乃至整个计算机科学的理论基础。邱奇-图灵论题(Church-Turing Thesis)告诉我们,一切可计算过程都可以用图灵机模拟。因此,无论如何人工智能都无法逃脱图灵机可计算理论的范畴。本章从图灵可计算理论的基础出发,忽略掉一切实用的工程细节,来讨论计算机可以做和不可以做的事情。从这些讨论中,我们可以站在一定的理论高度来窥探人工智能的前进方向。

本章首先会引入图灵机模型,为了让读者对这个概念有比较直观的理解,我采用了一个人工生命“小虫”的比喻来叙述。接下来会介绍跟图灵机有关的概念,例如什么是模拟,什么是“万能计算”(即通用计算,universal computation)等。最后是关于图灵停机问题的探讨,我个人认为很有可能未来对人工智能的重大突破都来源于对图灵停机问题的深入理解。另外,我除了用自己的方式介绍一些现有的基本概念之外(为了尽量表达得清楚明白,我不得不放弃理论论证的严格性),还探讨了很多我认为很有价值而计算理论却没有涉及的问题。在这部分内容上我都标上了*号,我尝试着给出了自己的思考结果,而没有经过严格的理论推敲,希望读者能有选择地看待这些问题和观点。

图灵机

计算是一个司空见惯、古已有之的概念。例如,我国古代发明的算盘就是一种计算的机器。然而,现代科学的计算概念则要追溯到20世纪初希尔伯特给国际数学界留下的著名的希尔伯特第十问题:“是否存在着判定任意一个丢番图方程有解的机械化运算过程。”很多数学家如库尔特·哥德尔(Kurt Godel)、阿隆佐·邱奇(Alonzo Church)、斯蒂芬·克莱尼(Stephen Kleene)等人都给出了各自的解答。然而,这些解答都很抽象或烦琐,只有图灵给出的解答——图灵机模型既直观又简洁,因此人们普遍接受了图灵机模型作为计算理论的标准模型。

下面,我们开始介绍图灵机模型。我先把这个概念抛给你,虽然有些无趣,不过请坚持看下去,后面我会重新解释的。在这里你只需要认识它的轮廓。图灵机是如图2-1所示的一个装置。

图 2-1 图灵机

这个装置由下面几个部分组成:一条无限长的纸带;一个读写头(中间那个大盒子);内部状态(盒子上的方块,比如A、B、D、E);还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令及其内部状态进行磁带的读写和移动。

它工作的时候是这样的:从读写头在纸带上读出一个方格的信息,并且根据它当前的内部状态开始在程序表中查找对应的指令,然后得出一个输出动作,也就是往纸带上写信息,还是移动读写头到下一个方格。程序也会告诉它下一时刻内部状态转移到哪一个。

具体的程序就是一个列表,也叫作规则表或指令表,如表2-1所示。

表2-1 规则表

当前内部状态(s

输入数值(i

输出动作(o

下一时刻的内部状态(s'

B

1

前移

C

A

0

往纸带上写1

B

C

0

后移

A

因此,图灵机只要根据每一时刻读写头读到的信息和当前的内部状态进行查表,就可以确定它下一时刻的内部状态和输出动作了。

图灵机就是这么简单!不可思议吧?而只要你修改它的程序(也就是上面的规则表),它就可以为你做计算机能够完成的任何工作。因此可以说,图灵机就是一个最简单的计算机模型!

也许,你会觉得图灵机模型太简单,怎么可能完成计算机的复杂任务呢?问题的关键是如何理解这个模型。

如何理解图灵机

我们不妨考虑这样一个问题。假设一只小虫在地上爬,那么我们应该怎样从信息处理的角度来建立一个小虫的模型呢?

首先,我们需要对小虫所在的环境进行建模。我们不妨假设小虫所处的世界是一个无限长的纸带,这个纸带被分成了若干小方格,而每个方格都只有黑和白两种颜色。很显然,这个小虫要有眼睛、鼻子或者耳朵等感觉器官来获得外部世界的信息。我们不妨把模型简化,假设它仅仅具有一个感觉器官:眼睛,而且它的视力弱得可怜,也就是说,它仅仅能够感知到它所处的方格的颜色,因此这个方格所在位置的黑色或者白色的信息就是小虫的输入信息。小虫模型如图2-2所示。

图 2-2 小虫模型

另外,我们当然还需要让小虫能够动起来。我们仍然考虑最简单的情况:小虫的输出动作就是在纸带上前进一个方格或者后退一个方格。

仅仅有了输入装置和输出装置,小虫还不能动起来,原因很简单,它并不知道该怎样在各种情况下选择它的输出动作。于是我们就需要给它指定行动的规则,这就是程序。假设我们记小虫的输入信息集合为I={黑色,白色},它的输出可能行动的集合是O={前移,后移},那么程序就要告诉它在给定了输入(比如黑色)的情况下,它应该选择什么输出。因而,一个程序就是一个从I集合到O集合的映射。我们也可以用列表的方式来表示程序,如表2-2所示。

表2-2 一个程序

输入

输出

前移

后移

这个程序非常简单,它告诉小虫当读到一个黑色方格的时候就往前走一个方格,当读到一个白色方格的时候就后退一个方格。

我们不妨假设,小虫所处的世界的一个片段是:黑黑黑白白黑白……(如图2-3所示),小虫从左端开始。

{%}

图 2-3 小虫世界的一个片段

那么小虫读到这个片段会怎样行动呢?它先读到黑色,然后根据程序前移一个方格,于是就会得到另外一个黑色信息,这个时候它会根据程序再次前移一个方格,仍然是黑色,再前移。这个时候就读到白色方格了,根据程序,它应该后退一个格,这个时候就是黑色了。前移,白色,后移,黑色,……可以预见小虫会无限地循环下去。

然而,现实世界中的小虫肯定不会傻傻地在那里无限循环下去。我们还需要改进这个最简单的模型。首先,小虫除了可以机械地在世界上移动以外,还会对世界本身造成影响,因而改变这个世界。比如小虫看到旁边有食物,就会把食物吃掉。在我们这个模型中,也就相当于必须假设小虫可以改写纸带上的信息。因而,小虫可能的输出动作集合就变成了O={前移,后移,涂黑,涂白}。这个时候,我们可以修改之前的程序,如表2-3所示。

表2-3 修改后的程序

输入

输出

前移

涂黑

纸带是黑黑白白黑……,小虫会怎样行动呢?图2-4到图2-10分别表示出了这个例子中小虫每一步的位置(标有圆点的方格就是小虫的当前位置)以及纸带的状况。

第一步:小虫在最左边的方格,根据程序的第一行,读入黑色应该前移。

{%}

图 2-4 第一步

第二步:仍然读入黑色,根据程序的第一行,前移。

{%}

图 2-5 第二步

第三步:这个时候读入的是白色,根据程序的第二行,应该把这个方格涂黑,而没有其他的动作。假设这张图上的方格仍然没有涂黑,而在下一时刻才把它表示出来。

{%}

图 2-6 第三步

第四步:当前方格已经是黑色的,因此小虫读入黑色方格,前移。

{%}

图 2-7 第四步

第五步:读入白色,涂黑方格,原地不动。

{%}

图 2-8 第五步

第六步:当前的方格已经被涂黑,继续前移。

{%}

图 2-9 第六步

第七步:读入黑色,前移。

{%}

图 2-10 第七步

小虫的动作还会持续下去,我们看到,小虫将会不停地重复上面的动作不断前移,并会把所有的纸带涂黑。

显然,你还可以设计出其他的程序来,然而无论你的程序怎么复杂,无论纸带子的情况如何,小虫的行为都会要么停留在一个方格上,要么朝一个方向永远运动下去,要么就是在几个方格上来回打转。然而,无论怎样,小虫比起真实世界中的虫子来说,有一个致命的弱点:那就是如果你给它固定的输入信息,它就会给你固定的输出信息!因为程序是固定的,每当黑色信息输入的时候,无论如何小虫都仅仅前移一个方格,而不会做出其他的反应。它似乎真的是机械的!

如果我们进一步更改小虫模型,那么它就会有所改进,至少在给定相同输入的情况下,小虫会有不同的输出情况。这就是加入小虫的内部状态。我们可以做这样一个比喻:假设黑色方格是食物,虫子可以吃掉它,而当吃到一个食物后,小虫就会感觉到饱了。当读入的信息是白色方格的时候,虽然没有食物但它仍然吃饱了,只有当再次读入黑色的时候它才会感觉到自己饥饿了。因而,我们说小虫具有两个内部状态,并把它所有内部状态的集合记为S={饥饿,吃饱}。这样小虫行动的时候不仅会根据它的输入信息,而且会根据它当前的内部状态来决定输出动作,并且还要更改它的内部状态。而它的这一行动仍然要用程序控制,只不过跟上面的程序比起来,现在的程序就更复杂一些了,如表2-4所示。

表2-4 更复杂的程序

输入

当前内部状态

输出

下一时刻的内部状态

饥饿

涂白

吃饱

吃饱

后移

饥饿

饥饿

涂黑

饥饿

吃饱

前移

吃饱

这个程序复杂多了,你不仅需要指定每一种输入情况下小虫应该采取的动作,而且还要指定在每种输入和内部状态的组合情况下小虫应该怎样行动。看看我们的小虫在读入黑白白黑白……这样的纸带的时候会怎样。仍然用一系列图(图2-11到2-18)来表示,灰色的圆点表示饥饿的小虫,白色的圆点表示它吃饱了。为了清晰,我们把小虫将要变成的状态写在了图的下方。

假定它仍然从左端开始,而且小虫处于饥饿状态。这样读入黑色,当前饥饿状态,根据程序第一行,把方格涂白,并变成吃饱(这相当于把食物吃了,注意吃完后,小虫并没动)。

{%}

图 2-11 第一步

第二步:当前的方格变成了白色,因而读入白色,而当前的状态是吃饱状态,那么根据程序中的第四条应该前移,仍然处于吃饱状态。

{%}

图 2-12 第二步

第三步:读入白色,当前状态是吃饱,因而会重复第二步的动作。

{%}

图 2-13 第三步

第四步:仍然重复上次的动作。

{%}

图 2-14 第四步

第五步:读入黑色,当前状态是吃饱,这时候根据程序的第二行应该后移方格,并转入饥饿状态。

{%}

图 2-15 第五步

第六步:读入白色,当前饥饿状态,根据程序第三行应该涂黑,并保持饥饿状态。(注意,这只小虫似乎自己吐出了食物!)

{%}

图 2-16 第六步

第七步:读入黑色,当前饥饿,于是把方格涂白,并转入吃饱状态。(呵呵,小虫把自己刚刚吐出来的东西又吃掉了!)

{%}

图 2-17 第七步

第八步:读入白色,当前吃饱,于是前移,保持吃饱状态。

{%}

图 2-18 第八步

这时候的情况已经跟第四步的完全一样了,因而小虫会完全重复五、六、七、八步的动作,并永远循环下去。最后的黑色方格似乎是一个门槛,小虫无论如何也跨越不过去了。

小虫的行为比以前的程序复杂了一些。尽管从长期来看,它最后仍然会落入机械的循环或者无休止的重复。然而这与前面的程序从本质上已经完全不同了,因为当你给小虫输入白色信息的时候,它的反应是你“不能预测”的。它有可能涂黑方格也有可能前移一个格。当然前提是你不能打开小虫看到它的内部结构,也不能知道它的程序,那么你所看到的就是一个“不能预测”的满地乱爬的小虫。如果小虫的内部状态数再增多呢?那么它的行为会更加地“不可预测”。

说到这里,你可能对于“小虫的行为不可预测”这句话持反对意见。因为所有可能的输入状态是固定的,所有的内部状态无论多少也是固定的,那么小虫所有可能的行为就应该是有限的。然而,不要忘记纸带的长度是无限的,虽然每个具体的输入可能只有0和1两种状态,然而这些0和1的输入组合却是无限的。退一步说,输入纸带的情况是有限的(你可以理解为01组合经过若干长度就会出现循环,比如011011011…),那么我们的小虫最终会不会必然陷入到无休止的循环中呢?答案是肯定的,因为这个时候输入的组合数乘以内部状态总数是一个有限的数值,因而小虫必然会在某时开始重复。无论哪种情况,似乎你都可以通过某种聪明的“数学”判断小虫是否会循环以及在什么时候循环。也就是说,通过你那聪明的数学,只要看看小虫的程序,而不用执行它就能够预言小虫在多少步之后必然会“傻傻地”重复以前的动作。这样一来,那可真是名副其实的“雕虫小技”了。然而真的是这样吗?这种判定小虫傻傻循环的一般定理或程序存在吗?这个问题留待我们后面进行讨论。

好了,如果你已经彻底搞懂了我们的小虫是怎么工作的,那么你已经明白了图灵机的工作原理。因为从本质上讲,最后的小虫模型就是一个图灵机。

如何理解图灵机模型*

刚才用小虫说明了图灵机的工作原理,相信你的第一个反应就是,这样的模型太简单了!它根本说明不了现实世界中的任何问题!下面,我就要试图说服你,图灵机这个模型是伟大的。

首先,我想说的是,其实我们每一个会决策、会思考的人就可以被抽象地看成一台图灵机。

为什么可以做这种抽象呢?首先我们可以考虑扩展刚才的小虫模型。因为小虫模型是以一切都简化为前提的,所以它的确是太简单了。然而,我们可以把小虫的输入集合、输出行动集合、内部状态集合进行扩大,这个模型一下子就实用多了。首先,小虫完全可以处于一个三维空间中,而不是简简单单的纸带上;其次小虫的视力很好,它一下子能读到方圆500米的信息。当然,小虫也可以拥有其他感觉器官,比如嗅觉、听觉等,而这些改变都仅仅是扩大了输入集合的维数和范围,并没有其他更本质的改变。同样的道理,小虫可能的输出集合也异常地丰富,它不仅可以移动自己,而且可以尽情地改造它所在的自然界。进一步地,小虫的内部状态可能非常多,而且控制它的行为的程序可能异常复杂,那么小虫会有什么本事呢?这就很难说了,因为随着小虫内部状态数的增加,随着它所处环境的复杂度的增加,我们正在逐渐失去对小虫行为的预测能力。但是所有这些改变仍然没有逃出图灵机的模型:输入集合输出集合内部状态固定的程序。就是这四样东西抓住了小虫信息处理的根本。

那么我们人能不能也被这样抽象呢?显然,输入状态集合就是你所处的环境中能够看到、听到、闻到、感觉到的所有的一切,可能的输出集合就是你的每一言每一行,以及你能够表达出来的所有表情动作。内部状态集合则要复杂得多。因为我们可以把任意一个神经细胞的状态组合看作一个内部状态,那么所有可能的神经细胞的状态组合将是天文数字!

似乎你会说,这个模型根本不对,还有很多思维本质的东西没有概括进去,比如记忆问题。人有记忆,图灵机有么?其实,只要图灵机具有了内部状态,它就相应地具有了记忆。比如上面讲到的具有饥饿和吃饱两种状态的小虫,就会记住它所经历过的世界:如果吃到食物,就用吃饱状态来“记住”吃过了食物这件事。什么是记忆呢?假如你经历了一件事情并记住了它,那么只要你下一次的行动在相同条件下和你记住这件事情之前的行动不一样了,就说明该事情对你造成了影响,也就说明你确实记住了它。

学习的问题反映在模型中了吗?学习是怎么回事儿呢?似乎在图灵机模型中不包括学习,因为学习就意味着对程序的改变,而图灵机是不能在运行过程中改变它的程序的。然而,我们不难假设,你实际上并不能打开一个人的脑袋来看,所以它的实际程序规则你是不知道的。很有可能一个图灵机的规则没有改变,只不过激活了它的某些内部状态,因而它的行为发生了本质的变化,尽管给它相同的输入,它却给出了完全不同的输出,因而在我们看来,它似乎会学习了。而实际上,这个图灵机的程序一点都没变。

还有很多现象似乎都能被图灵机包括,如人类的情绪和情感。你完全可以把它看作某种内部状态,因而处于心情好的情绪下,你的输入输出是一套规则,而心情不好的时候则完全是另一套规则。这仍然没有逃出图灵机的模型范围。

接下来的问题就是我们人类的思维究竟是不是和图灵机一样遵循固定的程序呢?这个问题初看似乎是不可能的,因为人的行为太不固定了,可以说是不可预言的。然而我会争辩道,无论如何神经元传递信息、变化状态的规律都是固定的,是可以被程序化的。那么脑作为神经元的整体,它的运作必然也要遵循固定的规则也就是程序了。如果是这样,正如图灵相信的,人脑也不会超越图灵机这个模型,所以,人工智能也必然是可能的。然而,我认为这个问题的答案很有可能没有这么简单,我们将在最后详细讨论这个问题。

无论如何,我相信你已经能够体会到了图灵机模型实际上是非常强有力的。数学家们早已经提出了邱奇-图灵论题以概括图灵机的计算能力,任何可计算过程都可以用图灵机来模拟。这是一个论题而非定理,因为它实际上是对可计算过程的定义,而非证明。但迄今为止,人们尚未发现一个可以视为计算的过程是图灵机不能模拟的。

计算

说了这么多,也许你已经了解了图灵机的威力,也许还将信将疑,然而,你肯定仍然看不出来图灵机和计算有什么关系。实际上,图灵机是一个理论计算机模型,它最主要的能耐还是在于计算上。下面我们就来看看什么是计算。

我可以先给出一个很摩登的对计算概念的理解:如果我们把一切都看作信息,那么广义上讲,计算就是对信息的变换。你会发现,其实自然界充满了计算。如果我们把一个小球扔到地上,小球又弹起来了,那么大地就完成了一次对小球的计算。因为你完全可以把小球的运动都抽象成信息,它无非是一些位置、速度、形状等能用信息描述的东西,而大地把小球弹起来无非是对小球的这些信息进行了某种变换,因而大地就完成了一次计算。你可以把整个大地看作一个系统,而扔下去的小球是对这个系统的输入,那么弹回来的小球就是该系统的输出,因而也可以说,计算就是某个系统完成了一次从输入到输出的变换

这样理解不要紧,你会发现,现实世界到处都是计算了。因为我们完全可以把所有的自然界存在的过程都抽象成这样的输入输出系统,所有的大自然存在的变量都看作信息,因而计算无处不在。的确,正是采取了这样的观点,人们才有可能发明什么DNA计算机、生物计算机、量子计算机这些新鲜玩艺儿。因为人们把DNA的化学反应、量子世界的波函数变换都看作计算了,自然就会人为地把这些计算组合起来构成计算机了。

下面回到图灵机。为什么说图灵机是一个计算的装置呢?很简单,图灵机也是一个会对输入信息进行变换给出输出信息的系统。以前面说的小虫为例,纸带上一个方格一个方格的颜色信息就是对小虫的输入,而小虫所采取的行动就是它的输出。似乎小虫的输出太简单了,因为它仅仅就有那么几种简单的输出动作。然而,复杂性来源于组合。虽然每一次小虫的输出动作都很简单,然而当我们把所有这些输出动作组合在一起,它就有可能非常复杂了。比如我们可以把初始时刻的整个纸带看作输入信息,那么经过任意长的时间,比如说100年后,小虫通过不断地涂抹纸带,最后留下的信息就是输出信息,那么小虫完成的过程就是一次计算。事实上,在图灵机的严格定义中,存在一个所谓的停机状态,当图灵机一到停机状态,我们就认为它计算完毕了,因而不用费劲地等上100年。

计算的组合

更有意思的是,我们可以把若干个计算系统进行合并,构成更大的计算系统。比如还是那个小球,如果往地上放了一个跷跷板,小球掉到地上会弹起这个跷跷板的另一端,而跷跷板的另一端可能还是一个小球,于是这个弹起的小球又会砸向另一个跷跷板……

我们自然可以通过组合若干图灵机完成更大更多的计算,如果把一个图灵机对纸带信息变换的结果输入给另一台图灵机,然后再输入给别的图灵机……这就是把计算进行了组合。也许你还在为前面说的无限多的内部状态和无限复杂的程序而苦恼,那么现在不难明白,实际上我们并不需要写出无限复杂的程序列表,仅仅将这些图灵机组合到一起就可以产生复杂的行为了。

有了图灵机的组合,我们就能够从最简单的图灵机开始构造复杂的图灵机。那么最简单的图灵机是什么呢?我们知道最简单的信息就是0和1,最简单的计算就是对0或1进行的布尔运算。而布尔运算本质上其实就三种:与、或、非。从最简单的逻辑运算操作最简单的二进制信息出发,我们其实可以构造任意的图灵机。这点不难理解:任何图灵机都可以把输入、输出信息进行01编码,任何一个变换也可以最终分解为对01编码的变换,而对01编码的所有计算都可分解成前面说的三种运算。也许,现在你明白了为什么研究计算机的人都要去研究基本的布尔电路。奥秘就在于,用布尔电路可以组合出任意的图灵机(详见本书第3章)。

征服无限的方法

回忆你小时候是如何学会加法运算的。刚开始的时候,你仅仅会死记硬背。比如你记住了1 + 1= 2,2 + 4= 6,……。然而无论你记住多少固定数字的运算,都不叫学会了加法。原因很简单,假如你记住了n 对数的加法,那么我总会拿出第 n+1 对数是你没有记住的,因此你还是不会计算。原则上,自然数的个数是无穷的,任何两个数的加法可能结果也是无穷的。如果采用死记硬背的方法,我们的头脑怎么可能记住无穷多个数字的计算法则呢?但是随着年龄的增长,你毕竟还是最终学会了加法运算!说来奇怪,你肯定明白其实加法运算并不需要记住所有数字的运算结果,仅仅需要记住10以内的任意两个数的和,并且懂得进位法则就可以了。

你是怎么做到的呢?假设要计算32 + 69的加法结果,你会把32写到一行,把69写到下一行,然后把它们对齐。于是你开始计算2 + 9 = 11,进一位,然后计算3 + 6 = 9,再计算9 + 1 = 10,再进一位,最后,再把计算的每一位的结果都拼起来就是最终的答案101。这个简单例子给我们的启发就是:做加法的过程就是一个机械的计算过程,这里的输入就是32和69这两个数字,输出是101。而你的程序规则就是把任意两个10以内的数求和。这样,根据固定的加法运算程序你就可以计算任意两个数的加法了。

不知你发现了没有,这个计算加法的方法能够让你找到运用有限的规则应对无限可能情况的方法。我们刚才说了,实际上自然数是无限的,所有可能的加法结果也是无限的。然而运用刚才说的运算方法,无论输入的数字是多少,只要你把要计算的数字写下来,就一定能够计算出最终的结果,而无需死记硬背所有的加法。

因而,可以说计算这个简单的概念是一种用有限来应对无限的方法。我们再看一个例子,假如给你一组数对:(1,2)(3,6)(5,10)(18,36),这时问你102对应的数是多少?很显然,仅仅根据你掌握的已知数对的知识,是不可能知道答案的,因为你的知识库里面没有存放着102对应数字的知识。然而,如果你掌握了产生这组数对的程序法则,也就是看到如果第一个数是 x,那么第二个数就是 2x 的话,你肯定一下子就算出102对应的是204了。也就是说,你实际上运用 2x 这两个字符就记住了无限的诸如(1,2)(3,6)(102,204)这样的数对。

这看起来似乎很奇怪。我怎么可能运用有限的字符来应对无限种可能呢?实际上,当没有人问你问题的时候,你存储的 2x 什么用也没有,而当我问你102对应的是多少时,我就相当于给你输入了信息102,而你仅仅是根据这个输入信息102,进行一系列的加工变换得到了输出信息204。因而输入信息就好比是原材料,你的程序规则就是加工的方法,只有在原材料上进行加工,你才能输出最终产品。

这让我不禁想起了专家系统方法。其实专家系统就是一个大的规则库,相当于存储了很多(1,2)(3,6)(5,10)这样特殊的规则对。但它存储的东西再多,总归会是有限的,你只要找到一个它没有存储到的问题,它就无能为力了。因而专家系统就会在你问到102对应多少的时候失败。如何解决问题?人们想出了很多方法,比如元规则。其实元规则就相当于刚才所说的计算加法的程序,或者 2x 这样的东西。运用元规则的确可以应对无限种情况了。所以,这就是你问计算机任何两个数相加是多少,它总能给出你正确答案的原因,虽然它不必记住所有这些加法对的信息。

然而仅仅是元规则就能解决所有问题吗?假如给你三组数对,排列成一张表:

1,2 3,6 4,8   100,200

3,9 2,6 8,24  100,300

1,4 2,8 3,12  100,400

那么请问在第6行上,3这个数字对应的是多少?我们先要找出第一行的规律是2x 没有疑问,第二行呢?是3x,第三行是4x,那么第6行就应该是7x 了,因而在第6行上3应该对应的是21!跟前面不太一样的是,虽然我们得到了每一行的规则比如2x,但是随着行数的增加,这个规则本身也变化了:第2行是3x,第3行是4x,因而我们又得到了一个规则本身的规则,即如果行数是 n 的话,那么这一行的规则就是(n + 1)x。我们显然能够根据输入的 nx 计算出数值。在专家系统里,这种原理就是元规则的规则,元元规则……,应该是无穷的。然而专家系统本身并不会自动归纳这些规则,人必须事先把这些元规则写到程序里,这就是专家系统最大的弊端。而我们人似乎总能在一些个别的事件中归纳出规则。进一步问,机器可以归纳吗?这就相当于说:可以为归纳方法编出程序吗?这也是一个很有趣的问题,下面我们会详细讨论。可以设想,假如我们找到了真正归纳的方法,那么编写出这样的程序,它就会一劳永逸地自己进行学习归纳了。我们再也不用给它编制程序和规则了。这正是人工智能的终极目标。

归纳*

金庸在他的武侠小说《倚天屠龙记》中曾讲述了这样一段故事:武林泰斗张三丰在情急之下要把他新创的武功“太极拳”传授给新起之秀张无忌。张无忌除了有一身精湛的“内功修为”外,还对武学具有极高的悟性。当张三丰给他打过一趟太极拳以后,他就把所有的招式全部记下来了,并且当场把所学的太极拳重新再打给张三丰看。在张无忌练拳的过程中,张三丰反复问他一个问题:“你已经忘掉几招了?”张无忌的回答令在场的其他人异常不解,因为他越在那里揣摩太极拳的奥秘,忘记的招数就越多。旁边的人不明白,这样的学法忘得这么快,怎么可能学会武功呢?然而,没过多长时间,张无忌说已经忘掉了所有的招式。张三丰笑着说:“不错,你终于学会了‘太极拳’。”

从这个例子中,我们看到了什么?张无忌之所以能学会太极拳,是因为他已经能够从具体的一招一式中抽象出更高层次的武学规律了,因而,当把所有有形的武功招数都忘记的时候,他已经掌握了太极拳的精髓。太极武功讲究的就是借力打力,以柔克刚。说白了,就是事先并没有固定招式存在,等到敌人进攻的时候再动态地生成破解的招术。

运用到图灵机模型中,我们不难发现,如果把具体的武功招术比喻成一些输入,把应对招术比喻成图灵机的输出,那么太极所讲究的借力打力、以柔克刚的方法其实就是类似2x这样的图灵程序。因而张无忌学太极拳的过程就是从特殊的输入输出提升到一般算法的过程,也可以说,张无忌运用了归纳学习法。

然而,仔细观察上一节的叙述,我们就会发现,虽然图灵机能够将2x这样的法则计算得出结果,但是抽象出 2x 本身并不是机器自动产生的,而是需要我们外在的人编程进去。那么,面对这样的问题,图灵机究竟能不能像张无忌一样进行归纳思维呢?

可以设想,如果计算机真有了张无忌那两下子,我们人类可要省事儿多了。我们甚至不需要为计算机编程序,它就会自动从若干个具体事例中归纳出一般的通用规律。然而,计算机究竟能不能具有真正的归纳能力呢?让我们来仔细考虑下面这个问题。

如果计算机能自动归纳,也就意味着我们可以为归纳方法编写一段程序P。这个程序可以理解为输入的是一些特殊的数对,输出的是能够生成这些数对的程序。也就是说输入具体的“招术”,输出的是这些“招术”的一般规律。如果程序P真的可以归纳,那么P就必然可以归纳出所有的规律。我们已经讨论过了,其实任何一个程序都能够被看作对输入的一个变换而得到输出。那么程序P自然也是。假设这些对子(a,b),(c,d),(e,f),……都是程序P的输入输出对,那么我们挑选出前1000个(总而言之是足够多的对子)。把这1000个特殊情况输入到P中,那么P就应该能够产生这些对子的共性,也就是P自己这个程序了。换句话说,程序P产生了它自己,P自己把自己给归纳出来了。这似乎陷入了怪圈之中!另外,我们人类设计出来P,如果P可以归纳所有的规律,那么P能否归纳出“人归纳P”本身这个规律呢?仍然是怪圈问题!这样的问题似乎还有很多。事实上,索洛莫诺夫(Solomonoff)很早就提出了通用归纳(universal reduction)模型,并对这个问题给出了明确的回答:虽然我们可以数学地写出通用归纳模型,但它却是不可计算的,也就是程序P并不存在,这与后面讨论的图灵停机程序有关。详细讨论请参见本书第5章。我们将会看到还有很多问题都涉及了逻辑中的怪圈,而由于计算理论已经触及了逻辑、信息的根本,所以把一些问题引向逻辑怪圈并不奇怪。

模拟

什么是模拟?又是一个基本的问题,阿尔伯特·爱因斯坦说过,越是基本的概念就越是难以刻画清楚。模拟这个概念就是一个很难说清的问题。

如果你站在一个朋友面前,冲着他做了一个鬼脸。那么他也会学着你的动作冲你做鬼脸,那么他就对你进行了模拟。

很明显,在你和你朋友之间存在着一系列的对应关系:你的手对应他的手,你的眼睛对应他的眼睛,你的嘴巴对应他的嘴巴……而且你的手、眼睛、嘴巴做出来的动作也会对应他的手、眼睛、嘴巴做出来的动作。因而,模拟的关键是对应。如果集合A中的元素可以完全对应B中的元素,那么A就可以模拟B。

仍然是以做鬼脸为例,假如这次你做出的鬼脸以及动作没有被他立即模仿而是被他用某种符号语言记录到了日记本上,比如“X年X月X日,疯子XX冲我做了一个鬼脸:他伸出了左手食指放到了右眼下面往下拉他脸上的肉,并且吐出了他长长的舌头!”。过了N多天后,你的这位朋友掏出了日记本,按照上面的描述冲着大家做了这个鬼脸。很显然他仍然模拟了你当时的动作。那么,你朋友日记本上的那段描述是不是对你鬼脸动作的模拟呢?答案似乎是否,因为这段文字跟你没有半点相像。然而你的朋友正是根据这段描述才做出了对鬼脸动作的模拟。也就是说,他把那段文字翻译成了他的动作,而他这个动作就是对你的模拟。这个翻译的过程很显然就是某种信息的变换,我们完全可以把它理解为一个计算的过程,也就是可以用图灵机来实现的算法过程。所以,我们说日记本上的那段指令也构成了对你鬼脸动作的模拟,原因是这些信息也与你的鬼脸动作构成了对应。具体的,我们可以用图2-19表示。

图 2-19 模拟

图中A是你的鬼脸动作,B是你朋友做出来的鬼脸动作,C是日记本上的描述。你朋友的动作B模拟了你的动作A,而B的动作信息是通过执行C上的描述得到的,也就是说,存在着一个从C到B的信息变换。这样我们认为C也对A进行了模拟。

图灵机之间的模拟

下面来考虑图灵机之间的模拟。按照前面的定义,一台图灵机包括输入集合I、输出集合O、内部状态集合S、程序规则表T四个要素。那么,如果两个图灵机之间的这些元素都存在刚才说的对应关系,就认为这两个图灵机可以相互模拟了。然而图灵机的功能是完成对输入信息进行变换得到输出信息的计算。我们关心的也仅仅是输入输出之间的对应关系。因而一台图灵机A如果要模拟B,并不一定要模拟B中的所有输入、输出、内部状态、程序规则表这些元素,而只要在给定输入信息的时候能够模拟B的输出信息就可以了。

因此,我们可以用图2-20来表示图灵机之间的模拟。

{%}

图 2-20 图灵机之间的模拟

也就是说,在给定相同输入信息的情况下,只要输出信息 o' 能够模拟信息 o,也就认为B模拟了A。而信息 o' 对信息 o 的模拟又符合我们上面对一般集合之间模拟的定义。也就是说,如果存在另外一台图灵机能够把信息 o' 计算并映射成信息 o,就认为 o' 模拟了 o。说白了也就是 o' 可以与 o 不一样,但是只要你能用一个图灵机把 o' 经过一系列运算变换到相同的 o,就认为 o' 模拟了 o。因而也就是图灵机B模拟了图灵机A。

进一步地,我们可以假设A和B输入的信息也不一样,一个是 i,另一个是 i',那么如果 ii' 之间也存在着模拟对应关系的话,我们仍然认为B可以模拟A,如图2-21所示。

{%}

图 2-21 图灵机之间的模拟

有一点需要注意,如果A图灵机模拟了B图灵机,那么B图灵机并不一定可以模拟A图灵机。因为有可能A图灵机比B图灵机处理的信息更多。也就是说假如B能处理的信息就是1,2,3,4,而A处理的信息除了这四个数之外,还有5,6,7,8,那么显然当输入1,2,3,4的时候A能够模拟B,而当输入5,6,7,8的时候B就没定义了,不能完成任何操作,这时B显然不能模拟A了。

计算等价性

讲了这么多关于模拟的知识有什么用呢?模拟的一个关键作用就是阐明什么是等价的。比如为了完成加法运算,你写了一段程序,我也写了一段程序,虽然我们两个的程序可能完全不一样,然而只要我们两个程序之间能够相互模拟,也就是说只要给定两个数,我们都能正确地一模一样地算出它们的和,那么我们两个程序就是等价的。

具体地说,如果A能够模拟B,并且B也能模拟A,那么A和B就是计算等价的。计算等价性是非常强有力的,因为它揭示了在我们这个宇宙中某种非常普遍的规律。我们仍然以刚才说的加法算法为例来说明。虽然计算两个数的加法的方法可能有无穷多种,也有可能用各种各样的计算机编程语言如C、Basic、Java等来实现,更有可能跑在不同的计算机上,然而所有这些程序,这些计算的结果意义都是相同的。也就是说,所有与加法运算算法计算等价的计算机程序都是一回事儿,因而加法算法这个东西是永恒而独立的。

看!我们在宇宙中找到某种永恒性了,这种永恒性反映了宇宙规律中某种本质上的美。计算等价性就和能量守恒定律一样具有这种高级的对称性,我甚至觉得计算等价性要比能量守恒定律更加深刻。因为无论如何能量守恒定律仍然刻画了物理系统的某种属性,而计算等价性刻画的则是非常广泛的信息系统之间的对称性,而一切系统都可以被抽象为信息系统,甚至是物质世界。所以,计算等价性是跨越所有系统之间的某种高级对称的、永恒的、美的东西。

为了进一步理解计算等价性的威力所在,我们不妨科幻一下。假设我们能够用计算机模拟某个人比如张三的思维过程,也就是说我们可以用一个计算机软件X来完成对张三思维的模拟。那么,这个软件就会在一切与它具有计算等价性的程序甚至系统上实现张三这个人的思维过程。比如我们完全有可能让一大堆分子的碰撞来实现X这个软件,那么就会在这一大堆分子碰撞的过程中完成对张三思维的模拟,也就是说张三这个人的意志蹦到这一大堆分子系统中去了。更进一步,我们还可以找来足够多的人(比如这个星球上所有的人)来模拟这一大堆分子的碰撞,从而完成软件X的计算。这意味着张三这个人的思维或者说意识在这群人的整体上突现了。很有可能,这些构成软件X的人都没有意识到在他们上层的张三的意识的出现。更有趣的是,很有可能张三自己就在那一群人之中呢。

相信你已经能够参悟到计算等价性的威力了,那么相信你能够理解为什么说任何一台我们使用的计算机都不过是图灵机的翻版了。

意义*

考虑下面三句话:“请把窗户关上!”“Please close the window!”“01001110111”。这三句话分别说给不同房间中的三个人。第一句话告诉给一个中国人,于是他关上了窗户;第二句话告诉了一个英国人,他也关上了窗户;第三句话告诉的是一个机器人,他也关上了窗户。这三句话从表面上看显然是完全不一样的,然而当它们说给不同的人听的时候,最终却达到了相同的效果:窗户被关上了。那么,我们自然会想,这三句话有何相同之处呢?显然,答案是它们的意义相同。然而什么又是意义呢?

真正回答意义的本质是一个很困难的问题,现在人们正在努力理解语义是什么。虽然我们仍没有完全回答这个问题,但是,不妨从图灵机、计算以及计算等价性的观点来考虑这个问题。如果把中国人、英国人、机器人都看作图灵机,把那三句话看作对它们的输入信息,那么最终的结果就是图灵机计算的输出。这个时候我们看到三种结果是相同的,也就是说这些图灵机之间是可以相互模拟的。

这三句话具有相同的意义,而根据前面的叙述,能够相互模拟的图灵机是计算等价的。而这种计算等价性就像前面说到的加法规则一样是独立于计算系统和执行机构的。因而,我们能得到图2-22。

{%}

图 2-22 计算等价性

通过图2-22,我们不难得出结论:所谓语言的意义,就是执行这个语言系统的计算等价性。

我们如何知道不同的语言表达了相同的意义呢?显然,只要有了翻译,我们就可以明白“请把窗户关上”与“Please close the window”具有相同的意义,而翻译所做的无非就是输入中文信息输出英文信息这样的信息转换工作,因而,也就是一个计算过程。

然而,当不存在从一种语言到另外一种语言的翻译的时候,我们也并不能断定某一个符号序列对于固定的图灵机是否有意义。例如,我们虽然不能明白鸟叫是什么含义,但并不能否认它们的叫声可能有意义,因为只有鸟自己才能明白叫声的含义。

万能图灵机

前面已经讲述了模拟的概念,那么自然会产生这样一个问题:是否存在一台图灵机能够模拟所有其他的图灵机呢?答案是存在的。这种能够模拟其他所有图灵机的图灵机叫作通用图灵机(Universal Turing Machine),也就是我所说的“万能图灵机”。我之所以这么称呼它,是因为这种机器在图灵计算这个范畴内是万能的。

万能图灵机会怎样工作呢?假如我把信息 x 输入到了图灵机M 中,M就能计算出一个结果 o。那么如果我把 x 和M的信息都输入给万能图灵机,那么它也会输出 o,也就是万能图灵机可以模拟任何一台特殊的图灵机。这样的话我们仅仅通过改变输入 x 和M的值就能“改变”万能图灵机的程序规则了,因而也可以认为万能图灵机就是可以任意编程的。这里的“改变”两个字加上了引号,是因为事实上任何图灵机在诞生之后就不能改变规则了,因而虽然看上去改变了万能图灵机的规则,其实根本没有改变。

编码

要理解为什么万能图灵机是存在的以及它怎样模拟其他任何图灵机的动作,我们必须要先理解究竟怎样把任何一台图灵机输入到万能图灵机中,这就需要理解编码的概念。什么是编码呢?你可以理解为对某一堆事物进行编号。

其实我们每人每天都在跟编码打交道。每个人都有一个身份证,身份证都有一个号码,那么这个号码就是人的编码。

26个字母能够被编码,比如a对应1,b对应2,……,这是显而易见的。然而任意一个英文单词都可以被编码则不那么容易一眼看出来。事实上,我们可以按照字典顺序把所有的单词都列出来。字母顺序越靠前、字符长度越短的单词排在前面,字母顺序越靠后、字符长度越长的单词就排在后面。比如一种可能的字典顺序如下所示:

a, about, an…, bad, be, behave…..

只要这样排好序,我们就能给每个单词赋予一个数字,最简单的方法是,给第一个单词分配1,第二个分配2,……因而我们就给所有的单词都编码了。

下面讨论任意一个图灵机能不能被编码。我们假设讨论的所有图灵机的输入集合都仅有0,1两种,而它的输出也仅仅有0,1,2,3四个动作,分别表示前移、后移、涂写0、涂写1。而内部状态数最多为10 000个(总之足够多就可以了)。

假设图灵机的程序表如表2-5所示。

表2-5 图灵机程序表

当前内部状态(s

输入数值(i

输出动作(o

下一时刻的内部状态(s'

2

1

0

3

1

0

3

2

3

0

1

1

那么我们可以把它写到一行中,这就是2,1,0,3; 1,0,3,2; 3,0,1,1,注意用“,”分开了内部状态、输入数值、输出动作和下一时刻的状态,而用“;”分开了一行一行具体的程序。这样无论这个表有多长,我们都可以把它写成一个这样的字符串。这个字符串就相当于一个英文单词,这就是对该图灵机程序的一个描述。同理,其他的图灵机也能够得到这样的一个单词描述,那么我们再用字典序的方法对这些描述进行编码,就得到了对所有图灵机的编码。

如果一台图灵机的编码是M,它读入的信息是x,这样只要把M和 x 用“.”号隔开,分开作为数据输入到万能图灵机中,运用特殊的算法,这个万能的机器就能得出对M计算 x 的模拟结果了。事实上可以由定理证明万能图灵机对于任意的编码都是存在的,在这里我们就不叙述证明过程了。

自食其尾

既然万能图灵机能够模拟任何一台图灵机的动作,那么它能不能模拟它自己呢?答案是肯定的。我们首先看到万能图灵机也是图灵机,也有固定的输入、输出、状态的集合、固定的程序,因而它也能被编码。于是我们就可以把它自己的编码信息输入给它自己。这就好像一条蛇咬到了自己的尾巴,自食其尾就会产生怪圈,虽然我们现在还没有看到任何不好的征兆,然而在下一节里面,我们将会看到这种怪圈会产生什么样的结论。而且在第4章我们也会看到,其实这个怪圈是和康托尔对角线法则、哥德尔定理有关的。

图灵机一旦能够把程序作为数据来读写,就会诞生很多有趣的事情。首先,存在某种图灵机可以完成自我复制。事实上,计算机病毒就是这样干的。我们简单说明一下这个特殊的图灵机是如何构造的。我们假定,如果一台图灵机是X,那么它的编码就记为<X>。这样能够自我复制的图灵机T的功能是把T的编码<T>写到纸带上输入万能图灵机,那么万能图灵机就能根据读入的<T>执行T,在纸带上再次输出<T>的一份副本<T>',并且<T> = <T>'。下面就来解释如何构造这样的T。首先T由两部分构成:A和B。第一部分A的功能是指导万能图灵机把B的编码<B>原封不动地打印到纸带上,纸带上就有了<B>,如果这个时候你想用同样的方法打印<A>到纸带上是不行的,因为A就会打印自己了。然而B却可以这样做:读入纸带上的信息X,生成能够打印X的图灵机p(X)的编码<p(X)>,打印到纸带上,并把X和<p(X)>的内容前后调换,有定理保证这样的图灵机是存在的。这样当B读到纸带上的信息<B>之后,就会打印出能够打印<B>的图灵机的编码也就是<A>,然后把<A>和<B>位置对换,就构成了<AB>,也就是<P>,所以P把自己进行了一次复制。初看起来,这种自我复制的程序是不可能的,因为这包含了无穷无尽的怪圈。P要能产生它自己<P>,就意味着P中至少包含了一个<P>,而这个<P>中又包含了至少一个<P>……最后P必然是一个无限大的程序,然而我们却能够证明P是可能的。关于自复制的进一步讨论可参见本书第4章。

有了万能图灵机,还能得到很多有趣的结论,比如假设有一大群图灵机,让它们随机地相互碰撞,当碰到一块的时候,一个图灵机可以读入另一个图灵机的编码,并且修改这台图灵机的编码。那么这样一个图灵机“汤”中会产生什么呢?美国圣塔菲研究所的方塔纳(Walter Fontana)完成了这个实验,并得出了惊人的结论:在这样的系统中会诞生自我维护的类似生命的复杂组织,而且这些组织能进一步联合起来构成更大的组织!

停机问题

尽管图灵机如此强大,它也有解决不了的问题。例如,一个著名的不可解问题就是图灵停机问题。

死循环

还记得我们前面提到的可怜的“小虫”吗?当时我们就提出来一个问题:会不会存在某种聪明的算法P,只要检查一下小虫的程序和纸带信息,而不用执行它,就能够让我们预言小虫是否会陷入死循环,无休止地重复前面的动作?

我们不妨设P(X,Y)表示P判断程序X作用到数据(纸带)Y上是否存在死循环的结果。如果X作用到Y上存在死循环,那么P(X,Y)就输出一个yes;否则就输出一个no

可惜的是,这种判断任意程序作用到任意数据上是否停机的程序P并不存在。我们可以给出一个证明。

在进行正式讨论之前,我们先来看一个非常简单的猜硬币游戏。

假如我两只手中有一个攥着一枚硬币,另一个什么都没有,然后让你猜硬币在哪一个手中?于是你告诉我左手。这时候我不会把手张开,而是背过身去做一番手脚,然后把手伸过来,张开手!哈,你错了吧,硬币在右手中!

大概傻子都能看出来我的伎俩之所在。不用说,采用这种方法我保证百战百胜。因为我总是等你说出来是哪只手有硬币之后再动态地改变我的策略。所以,改变之后的状态已经不是你猜的了。

大概你会觉得不可思议:其实图灵停机问题的证明就与这个游戏有点类似。

我们采用反证法,假设P程序存在。那么我们可以根据P设计一个新的程序Q:

Program Q(X){
    m=P(X,X)
    do while (m=no)
          ...
          ...
    end do
    if m=yes then return
}

这里的X是一个程序的编码。

这段程序通俗来讲就是:输入任何一段程序X,调用函数P(X,X)并得到返回值m,如果m=no,根据P的定义,P判断出程序X作用到它自己身上X不存在死循环。那么Q就不停地做do whileend do之间的语句。如果m=yes,这表示P判断出程序X在X上存在死循环,就返回,结束该函数。

可以看到,这样定义的函数Q(X)是没有问题的。下面就进入关键时刻了:Q这个程序作用到Q自身的编码也就是Q(Q)上会不会发生死循环呢?当然我们可以运用强有力的函数P(Q,Q)来计算这个问题。

假设Q(Q)会发生死循环,那么P(Q,Q)就会返回yes。然而根据Q函数的定义,把X=Q代入其中,会发现由于P(Q,Q)返回的是yes,也就是m=yes,因此Q函数会马上结束,也就是程序Q(Q)没有发生死循环。然而如果假设Q(Q)不会发生死循环,那么P(Q,Q)应该返回no,这样根据Q函数的定义,把X=Q代入Q(Q)会得到m=no,这样程序就会进入do while循环,而这个循环显然是一个死循环,因而Q(Q)发生了死循环。这又导致了矛盾。

无论Q(Q)会不会发生死循环,都会产生矛盾,然而哪里错了呢?答案只能是最开始的前提就错了,也就是说,我们最开始的假设P(X,Y)能够判断任意程序X在输入Y的时候是否死循环是错误的,这样的程序P(X,Y)不存在。

如何理解

也许你会感觉整个论证过程有些怪异,为什么不存在这种P(X,Y)程序呢?而且在上面的论证过程中仅仅说当P(X,Y)作用到P(Q,Q)上时会产生矛盾,似乎并不能说明P作用到其他程序上不能判断是否发生死循环。比如可以考虑编写这样一段程序,一发现某个程序中有do while(T)(这里T总是为true)这样的语句就判断这个程序会有死循环。这显然是可能的。但问题的关键是,你假设了P(X,Y)能够判断任意一个程序是否发生死循环,问题的关键就在于“任意程序”。因为假如你根据判断是否有do while(T)语句的方法写出了一个程序P来判断某程序是否发生死循环,那么我就会根据你这个程序P再构造出一个程序Q,就是利用前面提到的论证方法,我们不妨写成QP(这里下标P的含义表示根据你的程序P构造的Q)。这样你的P在遇到P(Q,Q)这样的怪东西的时候就无能为力了。

可能你还不服输,于是你又改进了你的程序变成了P',这个时候P' 能够判断包含了QP这个程序的所有程序情况了。那么我又会根据你的新程序P' 构造出一个更新的QP',你的程序P' 仍然不能判断,当然你还可以构造P'',P''',…,我也会跟着构造QP'' ,QP''' ,…,总而言之这个过程是无穷的。因为我总在你之后构造程序,所以你是水我是船,水涨船高,我总能比你高一级别。

这很像刚开始叙述的那个猜硬币的游戏。你想猜对我的硬币,就必须告诉我你的答案是左手还是右手,然而问题是我总能根据你给出的答案进行动态调整,让你永远也猜不对!停机问题也是如此,我总能根据你的程序P来构造P判定不出来的问题Q,我总会赢!很简单,因为你总要在我之前构造好P,就相当于你总要先说出硬币在哪个手中。

意味着什么

我们已经看到了,的确存在着一些我们人类能构造出来而图灵机不能解的问题。我们知道图灵机不能解的问题也就是一切计算机都不能解的问题,因而这类问题是不可计算的。因此,必然存在着计算机的极限。实际上,根据我们前面叙述的计算等价性原理,很多问题都可以被归结为图灵停机问题,也就是说图灵停机问题揭示了宇宙中的某种共性,所有计算机不能解决的问题从本质上讲都和图灵停机问题是计算等价的。比如在最开始我们提到的希尔伯特第十问题,就是一个典型的不可计算问题。还有很多问题是不可计算的,尤其是那些涉及计算所有程序的程序。比如是否存在一个程序能够检查所有的计算机程序会不会出错,这是一个非常实际的问题,然而这样的程序仍然是不存在的,其实可以证明这个问题和图灵停机问题实质上是一样的。于是我们的梦想又破灭了。

图灵停机问题也和复杂系统的不可预测性有关。我们总希望能够预测出复杂系统的运行结果。那么能不能发明一种聪明的程序,输入某个复杂系统的规则,输出的是这些规则运行的结果呢?从原则上讲,这种事情是不可能的。它也和图灵停机问题等价。因而,我们得出来的结论就是:要想弄清楚某个复杂系统运行的结果,唯一的办法就是让这样的系统实际运作,没有任何一种计算机算法能够事先给出这个系统的运行结果。但这并不是说不存在一个特定的程序能够预测某个或者某类复杂系统的结果。那么这种特定的程序怎么得到呢?显然需要我们人为地编程得到。也就是说存在着某些机器做不了而人能做的事情。这对人工智能的崇拜者来说似乎是沉重的打击。

人工智能真的是不可能的吗?彭罗斯曾经写过一本科普名著《皇帝新脑》来论证人工智能的不可能性。书中所运用的方法就是我们上面的逻辑。因为对于任何一个人工智能程序来说,总存在着它解决不了的问题。但是似乎我们人类却不受这种限制,我们总是能够发现一个程序是否有死循环,总是能够找到对某类复杂系统预测的方法,并且我们还能构造出图灵停机这样的问题。然而事实并没有那么简单,反对者马上就会论证到,其实针对某一个具体的人,比如说彭罗斯,我们也能够运用前面的方法构造出一个彭罗斯自己不能解的问题。然而事实上要构造彭罗斯不可解的问题太麻烦了,而我们只是说原则上讲这种问题是存在的。因而计算机超越不了的问题,人自己也超越不了,所以说人工智能是可能的。

上面提到的两方面论证似乎都很有道理,究竟哪个正确呢?真的存在某个人类不可解的类似图灵停机的问题吗?其实要想彻底回答这个问题就相当于问超越图灵计算的限制是否可能。如何超越图灵停机问题呢?下面我们将详细讨论这个问题。

超越图灵计算*

我们仍然以那个猜硬币的游戏为例来说明。

在进行了几轮猜硬币的游戏之后,你已经很恼火了,认为这样的游戏不公平。于是你想了一个妙招来对付我:每当我让你说硬币在哪只手中时,你先胡乱说一个答案,比如左手。于是我会根据你的答案进行动态调整,把硬币放到了右手中。这个时候你赶紧抢着说:不对,我猜你的硬币在右手!我没办法只能再次调整策略把硬币放到了左手中。你又赶快说:是在左手!……就是这样,你也学会了我的方法,根据我的策略不断调整你的策略从而让我不可能赢你。能不能把这种方法用到超越图灵停机问题呢?

前面我们已经看到了类似这样的过程。如你写出了一个程序P能够判断所有程序是否停机,那么我就能构造一个你的程序判断不了的程序Q。这时你又根据我的程序Q构造了新的程序P',然而我又能构造一个程序Q',仍然让你的程序P' 判断不了。但是你没有结束,又构造了新的程序P'',于是我又构造了Q''……

乍一看,似乎这个过程并不能说明任何问题。原因很简单,我要求的是构造一个固定的程序P判断出所有程序是否停机,而你给我的并不是一个具体的实实在在的程序,而是一个不断变化、捉摸不定、虚无飘渺的程序序列,并且你的这些总在变化的程序序列总是要根据我构造的程序才会确定改变。

首先值得肯定的一点是,运用这种方法,你的确能够超越图灵计算了,只要反复不停地变换你的程序,就不可能找出它不能解的问题。然而,另一方面又会让我们很失望:这样的变换过程并不能给出一个实实在在的程序来。我们拥有的仅仅是不断改变的程序序列,而不是一个实际存在的程序。

这正是问题的关键所在:要想彻底超越图灵计算的限制,我们必须放弃程序的实在性。也就是说程序每时每刻都要变化。那么这样一个不断变化得不是它自己的怪东西存在吗?

几千年的人类科学一直在研究实实在在的东西。无论是原子、分子还是计算机程序,它们必须是一个实实在在存在的个体,在这种前提下科学才能够对它进行研究。如果当我们研究它的时候,它已经变得不是它自己了,那么科学就对它无能为力了。然而,我不禁要提出这样的问题:真的一切都是固定不变地存在着的吗?有没有某种东西在每一时刻都在变得不是它自己呢?

这似乎是一个古老的哲学问题了。记得赫拉克利特就曾经提到过:一个人不能两次踏入同一条河流。我想他说的正是这样的问题:因为河流在每时每刻都不再是它自己了。河流是一大群流动的水滴构成的整体,这些水滴每时每刻都在不停地运动、流逝,因而当你两次踏入这条河的时候,所有的水滴可能都不一样了,那么我们怎么能说这些水滴构成的整体还是同一条河呢?

再考虑我们人自己。你很可能拿着一个3岁时的照片兴奋地对你的朋友说:“看,我3岁的时候多可爱呀!”然而你这句话意味着什么呢?意味着照片反映的3岁的你和现在的你是同一个个体。然而,3岁的你和现在的你是多么不同呀!我们知道,你无疑就是一大堆细胞构成的整体。而基本生理学知识告诉我们,人体的所有细胞每隔大约4年就会因为新陈代谢的作用全部更新一遍,也就是说,你的细胞全被调了包了,更何况3岁的你和现在的你差了多少个4年呀?那凭什么说那个3岁的你就是现在的你呢?

这个问题看似玄学,不过我认为现在我们的确应该认真对待该问题了。尽管从分析的角度来说,3岁的你和现在的你的确不是一个个体,然而常识告诉我们,这两个你的确都是同一个人。那就意味着,你这个个体并不是一些一成不变的固定的细胞,而是一个每时每刻都在变化和更新的一大堆细胞组成的构形。这个构形在每时每刻都要利用更新的一大堆细胞去维持自己的存在。和我们前面叙述的超越图灵机的讨论结合起来就会发现,人和赫拉克利特的河流这种东西刚好就满足超越图灵计算的要求。也就是说人和赫拉克利特的河流在每时每刻都在不停地更新自己从而变得不是它自己了。那么很有可能,某一种做类似变化的个体的变化规律就是不停超越它自己的图灵停机程序,这样的虚幻的个体就真的能够超越图灵计算了。

总结前面的讨论,我们不难得出结论,一个写出就不再变化的固死的程序不可能超越图灵计算的限制,然而如果一个程序每时每刻都变化得不是它自己了,那么这个程序就能够超越图灵计算。联系到人这个个体,我们就能得到:因为每时每刻的人都已经由于细胞的变化而变得不再是它自己了,所以人是超越图灵计算的。还记得我在前面提到的一个问题吗:人脑的信息处理过程能不能被表示成固定的程序呢?我这里的答案就是否定的,也就是说人脑信息处理的过程并不是一个固定的程序。如何制造真正的人工智能呢?我们的答案就是: 一个能不断改变自己的程序,而且这种改变也不是一个固定的程序。

推荐阅读

关于计算理论有很多值得参考的教科书,例如《计算理论导引》,以及比较全面的 Elements of the Theory of Computation 。另外一本比较通俗的是 Computability: An Introduction to Recursive Function Theory,作者用一种图灵机的变种来介绍计算理论中的各种概念。关于图灵的生平,可以参看《艾伦·图灵传》。想要了解方塔纳关于图灵机的试验,可以参考 Algorithmic Chemistry 一文。

参考文献

[1] Michael S. 计算理论导引. 唐常杰等译. 北京:机械工业出版社,2006.

[2] Lewis H R. Elements of the Theory of Computation, Prentice-Hall, Inc,1998.

[3] Cutland N J. Computability: an introduction to recursive function theory, Cambridge University Press, 1980.

[4] Fontana W. Algorithmic Chemistry, Langton C G, Taylor C, Farmer J D. Artificial life II. SFI Studies in the Sciences of Complexity, vol. X, (1991):159-210.

[5] 安德鲁·霍奇斯. 艾伦·图灵传:如迷的解迷者. 孙天齐 译. 长沙:湖南科学技术出版社,2012.

目录

  • 序一
  • 序二
  • 前言
  • 第 1 章 人工智能之梦
  • 第 2 章 图灵的计算王国
  • 第 3 章 从零开始的计算机系统
  • 第 4 章 一条永恒的金带
  • 第 5 章 从算法复杂性到通用人工智能
  • 第 6 章 深度学习:大数据时代的人工智能新途径
  • 第 7 章 关于人工智能与人脑智能的思考:康博士和贝博士的对话
  • 第 8 章 “人工”人工智能:从人机交互到人类计算
  • 第 9 章 美丽的注意力之流
  • 第 10 章 无处不在的自然语言处理
  • 第 11 章 从简单程序到群集智能
  • 第 12 章 从生物群体到机器人群体
  • 第 13 章 瓦克星计划:创造一个三体世界
  • 第 14 章 AI天气预报员