|
四、模拟 1、什么是模拟？ 什么是模拟？又是一个基本的问题，爱因斯坦说过，越是基本的概念就越是难以刻画 清楚。模拟这个概念就是一个很难说清的问题。 如果你站在一个朋友面前，冲着他做了一些鬼脸。那么他也会学着你的动作冲你做鬼 脸，那么他就对你进行了模拟。 很明显，在你和你朋友之间存在着一系列的对应关系：你的手对应他的手，你的眼睛 对应它的眼睛，你的嘴巴对应他的嘴巴……。而且你的手、眼睛、嘴巴做出来的动作也会对 应他的手、眼睛、嘴巴做出来的动作。因而，模拟的关键是对应！如果集合A中的元素可 以完全对应B中的元素，那么A就可以模拟B。 仍然用你冲你的朋友做鬼脸的例子，假如这次你做出的鬼脸以及动作没有被他立即模 仿而是被他用某种符号语言记录到了日记本上了。比如：“X年X月X日，疯子XX冲我做 了一个鬼脸：他伸出了左手食指放到了右眼下面往下拉他脸上的肉，并且吐出了他长长的舌 头！”。过了N多天后，你的这位朋友掏出了日记本，按照上面的描述冲着大家做了这个鬼 脸。很显然他仍然模拟了你当时的动作。那么，你朋友日记本上的那段对话描述是不是对你 鬼脸动作的模拟呢？似乎答案是否，因为这段文字跟你没有半点相像。然而你的朋友正是根 据这段描述才做出了对鬼脸动作的模拟。也就是说，他把那段文字翻译成了他的动作，而他 这个动作就是对你的模拟。这个翻译的过程很显然就是某种信息的变换，我们完全可以把它 理解为一个计算的过程，也就是可以用图灵机来实现的算法过程。所以，我们说日记本上的 那段指令也构成了对你鬼脸动作的模拟，原因是这些信息也与你的鬼脸动作构成了对应。具 体的，我们可以用下面的图表示： 这里A是你的鬼脸动作，B是你朋友做出来的鬼脸动作，C是日记本上的描述。你朋 友的动作B模拟了你的动作A，而B的动作信息是通过执行C上的描述得到的，也就是说 存在着一个从C到B上信息的变换。这样我们认为C也对A进行了模拟。 2、图灵机之间的模拟 下面来考虑图灵机之间的模拟。按照前面的定义，一台图灵机包括：输入集合I，输出 集合O，内部状态集合S，程序规则表T四个要素。那么如果两个图灵机之间的这些元素都 存在刚才说的对应关系，就认为两个图灵机可以相互模拟了。然而图灵机的功能是完成对输 入信息进行变换得到输出信息的计算。我们关心的也仅仅是输入输出之间的对应关系。因而 一台图灵机A如果要模拟B并不一定要模拟B中的所有输入、输出、内部状态、程序规则 文本框: A文本框: B文本框: C文本框: 模拟文本框: 变换文本框: 模拟 表这些元素，而只要在给定输入信息的时候，能够模拟B的输出信息就可以了。 因此，我们可以用下面的图来表示图灵机之间的模拟： 也就是说在给定相同输入信息的情况下，只要输出信息o’能够模拟信息o就可以，也 就认为B模拟了A。而信息o’对信息o的模拟又符合我们上面对一般集合之间模拟的定义。 也就是说如果存在另外一台图灵机能够把信息o’计算并映射成信息o，就认为o’模拟了o。 说白了也就是o’可以与o不一样，但是只要你能用一个图灵机把o’经过一系列运算变换到 相同的o，就认为o’模拟了o。因而也就是图灵机B模拟了图灵机A。 进一步，我们可以假设A和B输入的信息也不一样，一个i，另一个是i’，那么如果i 和i’之间也存在着模拟对应关系的话，我们仍然认为B可以模拟A。也就是下面的图： 有一点需要注意，如果A图灵机模拟了B图灵机，那么并不一定B图灵机可以模拟A 图灵机。因为有可能A图灵机比B图灵机处理的信息更多。也就是说假如B能处理的信息 就是1，2，34，而A处理的信息除了这四个数之外，还有5,6,7,8，那么显然当输入1234 的时候A能够模拟B，而当输入5678的时候B没定义了，不能完成任何操作。在这个时候 B显然不能模拟A了。 3、计算等价性 讲了这么多关于模拟的知识有什么用呢？模拟的一个关键作用就是阐明什么是等价 的。比如为了完成加法运算，你写了一段程序，而我也写了另一段程序，虽然我们两个的程 序可能完全不一样，然而只要我们两个程序之间能够相互模拟，也就是说只要给定两个数， 我们都能正确的一模一样的算出它们的和，那么我们两个程序就是等价的！ 具体地说，如果A能够模拟B，并且B也能模拟A，那么A和B就是计算等价的。计 算等价性是非常强有力的，因为它揭示了在我们这个宇宙中某种非常普遍的规律。我们仍然 用刚才说的加法算法为例子来说明。虽然计算两个数的加法的方法可能有无穷多种，也有可 能用各种各样的计算机语言，什么C,Basic,JAVA等等来实现，更有可能奔跑在不同的计算 机上，然而所有这些程序，这些计算的结果意义都是相同的。也就是说所有与加法运算算法 计算等价的计算机程序都是一回事儿，因而加法算法这个东西是某种永恒而独立的！ 看！我们在宇宙中找到了某种永恒性了，这种永恒性反映了宇宙规律中某种本质上的 文本框: 输入信息i椭圆: 图灵机A椭圆: 图灵机B文本框: 输出信息o文本框: 输出信息o’文本框: 模拟文本框: 模拟文本框: 模拟文本框: 模拟文本框: 输出信息o’文本框: 输出信息o椭圆: 图灵机B椭圆: 图灵机A文本框: 输入信息i文本框: 输入信息i’文本框: 模拟 美！计算等价性就和能量守恒定律一样具有这种高级的对称性，我甚至觉得计算等价性要比 能量守恒定律更加深刻！因为无论如何能量守恒定律仍然是刻画了物理系统的某种属性，而 计算等价性则刻画的是非常广泛的信息系统之间的某种守恒和对称性，而一切系统都可以被 抽象为信息系统，甚至是物质世界，所以，计算等价性是跨越所有系统之间的某种高级对称 的、永恒的、美的东西。 为了进一步理解计算等价性的威力所在，我们不妨科幻一下。假设我们能够用计算机 模拟某个人，比如说张三的思维过程了（也就是假设真正的人工智能可以实现了）。那也就 是说我们可以用一个计算机软件X来完成对张三思维的模拟。这样，这个软件就会在一切 与它具有计算等价性的程序甚至系统上实现张三这个人的思维过程！比如我们完全有可能让 一大堆分子的碰撞来实现X这个软件，那么就会在这大堆分子碰撞的过程中完成对张三思 维的模拟，也就是说张三这个人的意志蹦到了这一大堆分子系统中去了！更进一步，我们还 可以找来足够多的人比如这个星球上所有的人来模拟那大堆分子的碰撞，从而完成软件X 的计算。这意味着什么？意味着张三这个人的思维或者说意识在那群人的整体上突现了！很 有可能，这些构成软件X的人都并没有意识到在他们上层的张三的意识的出现。更有趣的 是，张三自己很有可能就在那一群人之中呢！ 相信你已经能够参悟到了什么是计算等价性的威力了，那么我也相信你能够理解为什 么说任何一台我们使用的计算机都不过是图灵机的翻版了。 4、意义* 考虑下面三句话：“请把窗户关上！”，“Please close the window！”，“01001110111”。这 三句话分别说给不同房间中的三个人。第一句话告诉给一个中国人，于是他关上了窗户；第 二句话告诉了一个英国人，他也关上了窗户；第三句话告诉的是一个机器人，他也关上了窗 户。这三句话从表面看显然是完全不一样的，然而当它们让不同的人来听的时候，却达到了 相同的最终结果：窗户被关上了。那么，我们自然会想，这三句话有何相同呢？显然，答案 是他们的意义相同。然而什么又是意义呢？ 真正回答意义的本质是一个很困难的问题，现在人们正在努力理解语义是什么。虽然 我们仍没有完全回答这个问题，但是，不妨从图灵机、计算以及计算等价性的观点来考虑该问题。如果把中国人、英国人、机器人都看作是图灵机，而那三句话看作是对他们的输入信 息，那么最终的结果就是图灵机计算的输出。这个时候我们看到三种结果是相同的。也就是 说这些图灵机之间是可以相互模拟的。 考虑这三句话，显然它们都具有相同的意义。而根据前面的叙述，能够相互模拟的图 灵机是具有相同的计算等价性的。因而描述听到关窗指令后并按照指令行事的图灵机具有相 同的计算等价性。而这种计算等价性就好像是前面说到的加法规则一样是独立于计算系统、 执行机构的。因而，我们能得到下面的图： 通过这个对比图，我们不难得出结论：所谓语言的意义，就是执行这个语言系统的计 算等价性！ 我们如何知道不同的语言表达了相同的意义呢？显然，我们只要有了翻译就可以明白 “请把窗户关上”与“Please close the window”具有相同意义，而翻译所作的工作无非就是 输入中文信息输出英文信息这样的信息转换工作，因而，也就是一个计算过程！ 然而当不存在从一个语言到另外一个语言的翻译的时候，我们也并不能断定某一个符号 序列对于固定的图灵机是否有意义。这就是说，我们虽然不能明白鸟叫是什么含义，但并不 能否认它们的叫声可能有意义，因为只有鸟自己才能明白叫声的含义。 五、万能图灵机 1、编码 其实我说的这个“万能图灵机”就是计算机术语中的“通用图灵机”，英文是Universal Turing Machine。而我之所以称之为“万能图灵机”完全是因为这个名字似乎听起来更加直 观。 前面已经讲述了模拟的概念，那么自然会产生这样一个问题：存在不存在一台图灵机 能够模拟所有其他的图灵机呢？答案是存在的。这种能够模拟其他所有图灵机的图灵机就叫 做通用图灵机，也就是我们所说的“万能图灵机”。这种机器在图灵计算这个范畴内，是万 能的！ “万能图灵机”会怎样工作呢？假如我把信息x输入到了图灵机M中，M就能计算出 一个结果o。那么如果我把x和M的信息都输入给万能图灵机，那么万能图灵机也会输出o， 也就是万能图灵机可以模拟任何一台特殊的图灵机。这样的话我们就可仅仅通过改变输入x 和M的值就能“改变”万能图灵机的程序规则了。因而也可以认为万能图灵机就是可以任 意编程的。这里的改变两个字加上了引号，是因为事实上任何图灵机在诞生之后规则就不能 改变了，因而我们能够改变“万能图灵机”的规则，仅仅是因为看上去是这样的，其实根本 没有改变。 要说明为什么“万能图灵机”是存在的，以及它是怎样模拟其他任何图灵机的动作的， 我们必须先要理解究竟怎样把任何一台图灵机输入到“万能图灵机中”，这就需要理解编码 的概念。什么是编码呢？你可以理解为对某一堆事物进行编号就是编码。 其实我们每人每天都在跟编码打交道。每个人都有一个身份证，而这个身份证都有一 椭圆: 语言椭圆: 执行者文本框: 请把窗户关上！文本框: 中国人文本框: Please close the window！文本框: 英国人文本框: 01001110111文本框: 机器人文本框: 同意义文本框: 同意义文本框: 计算等价文本框: 计算等价文本框: 相同处：椭圆: 意义椭圆: 计算等价性文本框: 输入指令文本框: 输入指令文本框: 输入指令 个ID号码吧？那么这个号码就是你的编号。上学的时候老师给我们每个人都分配一个学号 也是编码。 26个字母能够被编码，比如a对应1，b对应2，……，这是显而易见的。然而任意一 个英文单词都是可以被编码的则不那么容易一眼看出来。事实上，我们可以按照字典顺序把 所有的单词都列出来。也就是说字母顺序越靠前，字符长度越短的单词排在前面，其次长单 词，字母顺序靠后的单词就排在后面。比如一种可能的字典顺序： a, about, an…, bad, be, behave….. 只要这样一排好序，我们就能给每个单词赋予一个数字，最简单的方法是，给第一个 字母分配1，第二个分配2，……，因而我们就给所有的单词都编码了。下面讨论任意一个图灵机能不能被编码。我们假设讨论的所有图灵机的输入集合都是 仅有0,1两种，而它的输出也仅仅有0,1,2,3四个动作分别表示前移，后移，涂写0，涂写1。 而内部状态数最多为10000个（总之足够多就可以了）。下面考虑程序。 假设图灵机的程序表为： 当前内部状态s 输入数值i 输出动作o 下一时刻的内部状态s' 2 1 0 3 1 0 3 2 3 0 1 1 … … … … 那么我们可以把它写到一行中，这就是2,1,0,3; 1,0,4,2; 3,0,1,1，注意用“，”分开了内 部状态，输入数值，输出动作和下一时刻的状态，而用“；”分开了一行一行具体的程序。 这样无论这个表有多大，我们都可以把它写成这样的一个字符串。这个字符串就相当于一个 英文单词，这就是对该图灵机程序的一个描述。同理，其他的图灵机也能够得到这样的一个 单词描述，那么我们再用字典序的方法对这些描述进行编码，也就得到了对所有图灵机的编 码。 如果一台图灵机的编码是M，它读入的信息是x，这样只要把M和x用“.”号隔开的 方法分开作为数据输入到“万能图灵机”中，运用特殊的算法，这个万能的机器就能得出对 M计算x的模拟结果了。事实上可以由定理证明万能图灵机对于任意的编码都是存在的， 在这里我们就不叙述证明过程了。 2、自食其尾 既然“万能图灵机”能够模拟任何一台图灵机的动作，那么它能不能模拟它自己的动 作呢？答案是肯定的。我们首先看到“万能图灵机”也是图灵机，也有固定的输入、输出、 状态的集合、固定的程序，因而它也能被编码。于是我们就可以把它自己的编码信息输入给 它自己了。这就好像一条蛇咬到了自己的尾巴。会发生什么呢？自食其尾就会产生怪圈，虽 然我们现在还没有看到任何不好的征兆，然而在下一节里面，我们将看到这种怪圈会诞生什 么样的结论。而且我们也会看到，其实这个怪圈是和康托尔对角线法则、哥德尔定理有关的。 图灵机一旦能够把程序作为数据来读写，就会诞生很多有趣的情况。首先，存在某种 图灵机可以完成自我复制！事实上，计算机病毒就是这样干的！我们简单说明一下，这个特 殊的图灵机是如何构造的。我们假定，如果一台图灵机是X，那么它的编码就记为，这 样能够自我复制的图灵机T的功能是，把T的编码写到纸带上输入到“万能图灵机”， 那么“万能图灵机”就能根据读入的，在纸带上再次输出的一份拷贝’，并且 =’。下面就来大概解释如何构造这样的T。首先T由两部分构成AB。第一部分A 的功能是指导“万能图灵机”把B的编码原封不动的打印到纸带上，这个时候纸带上就 有了，如果这个时候你想用同样的方法打印到纸带上是不行的，因为会出现循环定 义。然而B可以这样做，读入纸带上的信息X，生成能够打印X的图灵机：p(X)的编码 打印到纸带上，并把X和的内容前后调换，有定理保证这样的图灵机是存在的。这 样当B读到纸带上的信息之后就会打印出能够打印的图灵机的编码也就是了， 然后把和位置对换就构成了也就是 ，所以P把自己进行了一次拷贝。初看 起来，这种自我复制的程序是不可能的，因为这包含了无穷无尽的怪圈。P要能产生它自己 就意味着P中至少包含了一个 ，而这个 中又包含了至少一个 ……，最后P必 然是一个无限大的程序，然而我们却能够证明P是可能的。 有了“万能图灵机”还能得到很多有趣的结论，比如假设有一大群图灵机，让它们彼 此之间随机的相互碰撞，当碰到一块的时候，一个图灵机可以读入另一个图灵机的编码，并 且修改这台图灵机的编码。那么这样一个图灵机“汤”中会产生什么呢？圣塔菲研究所的芳 塔娜已经研究了这个实验，并得出了惊人的结论：在这样的系统中会诞生自我繁殖的、自我 维护的类似生命的复杂组织，而且这些组织能进一步联合起来构成更大的组织！ 六、停机问题 1、死循环 在进行正式讨论之前，我们先来看看一个非常简单的猜硬币游戏。假如我的两个拳头中一个攥着一枚硬币，另一个没有，然后让你猜是哪一个？于是你 告诉我左手中有。这时候我不会把手张开，而是背过身去做一番手脚，然后把拳头伸过来， 张开手！哈，你错了吧，硬币在右手中！大概傻子都能看出来我的伎俩之所在！不用说，采 用这种方法我保证百战百胜。因为我总是等你说出来哪个手有硬币之后再动态的改变我的策 略。所以，这改变之后的状态就已经不是你猜的了。 大概你会觉得不可思议：其实图灵停机问题就是一个类似该游戏的原理！ 下面我们来看看图灵停机问题是怎么回事儿。让我们考虑这样一个问题：存在不存在 一个程序比如说P，能够判断出任意一个程序X是否会在输入Y的情况下陷入死循环？我 们不妨设P(X,Y)表示P判断程序是X，数据是Y的结果。如果存在死循环，那么P(X,Y)就 输出一个yes。如果不存在死循环，那么P(X,Y)就输出一个no。我们的问题就是这样的P(X,Y) 存在么？这就是停机问题。所谓的某个程序X在输入Y上停机就是说X不存在着死循环， 反过来如果不停机就是存在着死循环，因而这里停机和死循环是一回事儿。那么，这种判断 停机问题的程序P存在么？ 答案是不存在的。下面我可以证明我的这个结论。 我们不妨假设程序P存在。那么我们可以根据P设计一个新的程序Q如下： X是任何一段程序的编码： Program Q(X){ m=P(X,X) do while (m=no) … … end do if m=yes then return } 这段程序通俗来讲就是：输入任何一段程序X，调用函数P(X,X)并得到返回值m，如 果m=no，也就是说根据P的定义，P判断出程序X作用到它自己身上X不存在死循环。那 么Q就不停的做do while和end 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)不存在！ 2、如何理解 也许你会感觉整个论证过程有些怪异，为什么不存在这种P(X,Y)程序呢？而上面的论 证过程中仅仅说P(X,Y)当作用到P(Q,Q)上时会产生矛盾。似乎并不能说明P作用到其他程 序上不能判断是否死循环。比如你可以考虑编写这样一段程序，当一发现某个程序do while(T)，这里T总是为真，这样的语句出现的时候就判断这个程序有死循环。这显然是可 能的。但问题的关键是，你假设了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呀，就相当于你总要先说出硬币在哪个手！ 3、对角线删除方法 我在开始的时候就提到了图灵停机问题、哥德尔定理等等都来源于康托尔的对角线删除 法则。那么，下面我们就来看看，如果运用对角线删除法则如何证明图灵停机问题呢？采用 这种全新的证明思路，也许你会更加清楚地认识到停机问题的本质。 问题没有变，是否存在一个程序P(X,Y)判断出来任意一个程序X当输入Y的时候是否 有死循环，或者说是否停机。 我们仍然用反证法，假设这样的P(X,Y)是存在的。而我们知道程序X本身是可以被编 码的。也就是可以为所有的程序进行编号：1，2，3，……，而数据Y本身也是这样的编号 1，2，3，……，因而我们就可以把每一对X和Y的组合排列在一张表上。比如列表示的是 数据Y，而行表示的是程序X，这样P(X,Y)的值也就是yes或no就可以写在第X行第Y列 的对应位置上，表示P(X,Y)判断出的X作用在输入Y上是否会死循环的结果。比如下面的 表就是一个示例： 1 2 3 4 5 6 …… Y …… 1 yes no no yes yes no …… yes …… 2 no no yes yes no yes …… no …… … …………………………………………………… X no yes no yes yes no …… yes …… … …………………………………………………… 到这里没有发生什么毛病。我们知道上表中的每一个行都表示一个确定的程序作用到不 同的数据上所得到的结果。比如程序X作用在1,2,3,4,……,Y，……上给出的结果就是一个 序列： no,yes,no,yes,yes,no,……,yes，…… 下面我们把上表对角线上的元素挑出来。也就是专门找那些第1行第1列，第2行第2 列，……这样的元素就可以得到一个序列： yes,no,no,yes, …… 而根据这个序列我们完全可以构造这样一个反序列： no,yes,yes,no, …… 也就是说这个序列在每一个位上都与前一个对角线序列不同！这个序列就称为对角线删 除序列。那么我问，这个对角线删除序列是否在我们表中的某一行上呢？答案是否定的！这 个序列必然不在表中。因为它的第一个元素与1,1不同，第二个元素与2,2不同，……。换 一种方式解释就是：假设对角线删除序列的确在表上列出来了，那么这个序列必然在某个固 定的行，比如说就在第1001行。那么我们就要考虑这第1001行，第1001列的元素，我们 知道根据序列的构造方法(1001,1001)对应表中的元素是与序列上的这个元素不同的！因而产 生了矛盾，也就是说这个构造出来的对角线删除序列不在表中！ 我们完全可以设计出一段程序Q使得Q作用在1,2,……,X,……上产生的序列就是对角 线删除序列，而对角线删除序列不在表中就意味着程序P并不能判断出程序Q作用在任意 输入上是否停机。其实这里的程序Q就是前一节论证停机问题的程序Q。 用对角线删除的证明方法来看究竟哪里出错了呢？错误就出在我们假设程序P能够得 到这样一张完整的表，这张表对所有的程序计算得到是否停机的答案。 4、意味着什么？ 我们已经看到了，的确存在着一类问题我们人类能构造出来，而图灵机是不能解的，。 我们知道图灵机不能解的问题也就是一切计算机不能解的问题，因而这类问题也叫做不可计 算的。因此，必然存在着计算机的极限。实际上，运用我们前面叙述的计算等价性原理，有很多问题都可以被归结为图灵停机问题，也就是说图灵停机问题揭示了宇宙中某种共性的东 西，所有那些计算机不能解决的问题从本质上讲都和图灵停机问题是计算等价的。比如在最 开始我们就提到的希尔伯特第10问题就是一个典型的不可计算问题！还有很多问题是不可 计算的，尤其是那些涉及到计算所有程序的程序。比如是否存在一个程序能够检查所有的计 算机程序会不会出错？这是一个非常实际的问题。我们都知道计算机程序特别容易犯错误， 为了检查出某段计算机程序的错误，我们人类就必须对这个程序进行人工的检查。那么能不 能发明一种聪明的计算机软件，输进去任何一段计算机程序，这个软件就会自动帮你检查输 入的程序是否有错误？答案仍然是不存在的，其实这个问题可以被证明和图灵停机问题实质 上是一样的！于是我们的梦想又破灭了！ 图灵停机问题也和复杂系统的不可预测性有关。我们总希望能够预测出复杂系统的运行 结果。那么能不能发明一种聪明的程序，输入进去某个复杂系统的规则，输出的是这些规则 运行的结果呢？从原则上讲，这种事情是不可能的。它也是和图灵停机问题等价的。因而， 我们得出来的结论就是：要想弄清楚某个复杂系统运行的结果，唯一的办法就是让这样的系 统实际运作，没有任何一种计算机算法能够事先给出这个系统的运行结果。你很有可能不同 意我的观点，因为毕竟我们能够发明很多预测复杂系统的方法，而不需要一定要让复杂系统 去真实的运作。但是，你还是没有理解我这里的问题。我们强调的是不存在一个通用的程序 能够预测所有复杂系统的运行结果，但并没有说不存在一个特定的程序能够预测某个或者某 类复杂系统的结果。那么这种特定的程序怎么得到呢？显然需要我们人为地编程得到！也就 是说存在着某些机器做不了的事情，而人能做。这似乎为人工智能的崇拜者给以了沉重的打 击！ 人工智能真的是不可能的么？彭罗斯曾经写过一本科学明著：《皇帝新脑》来论证人工 智能的不可能性。它所运用的方法就是我们上面的逻辑。因为对于任何一个人工智能程序来 说，总存在着它解决不了的问题！但是似乎我们人类却不受这种限制，我们总是能够发现一 个程序是否有死循环，总是能够找到对某类复杂系统预测的方法，并且我们还能构造出来图 灵停机问题这样的问题。然而事实并没有那么简单，反对者马上就会论证到，其实针对某一 个具体的人，比如说就是彭罗斯，我们也能够运用前面的方法构造出一个彭罗斯自己不能解 的问题！然而事实情况下要构造彭罗斯不可解的问题太麻烦了，而我们只是说原则上讲这种 问题是存在的！因而计算机超越不了的问题，人自己也超越不了，所以说人工智能是可能的！ 看看上面提到的两方面论证似乎都很有道理，究竟哪个正确呢？真的会存在某个人不可 解的类似图灵停机的问题么？其实要想彻底回答这个问题就相当于问超越图灵计算的限制 是否可能？如何超越图灵机停机问题呢？下面我们将详细讨论一下这个问题。 5、超越图灵计算* 我们仍然用那个猜硬币的游戏为例来说明。 在进行了几轮猜硬币的游戏之后，你已经很恼火了，认为这样的游戏不公平。于是你想 了一个妙招来对付我：每当我让你说硬币在哪个手中时，你先胡乱的说一个答案，比如左手。 这个时候我会根据你的答案动态调整把硬币放到了右手中。这个时候你赶紧抢着说，不对， 我猜你的硬币在右手！我没办法只能再次调整策略把硬币放到了左手。你又赶快说：是在左 手！……。就是这样，你也学会了我的方法，根据我的策略不断调整你的策略从而让我不可 能赢你。能不能把这种方法用到超越图灵停机问题呢？ 前面我们已经看到了类似这样的过程。假如你写出了一个程序P能够判断所有程序是 否停机，那么我就能够构造一个程序Q是你的程序判断不了的。这个时候还没有结束，你 又根据我的Q构造了新的程序P’，然而我又能构造一个程序Q’仍然让你的程序P’解决不了。 但是你没有结束，又构造了新的程序P’’，我于是又构造Q’’……。 乍一看，似乎这个过程并不能说明任何问题。原因很简单，我要求的是构造一个固定的 程序P判断出所有程序是否停机。而你给我的并不是一个具体的实实在在的程序，而是一 个不断变化的捉摸不定而虚无飘渺的程序序列！并且你的这些总在变化的程序序列总是要根 据我构造的程序才会确定改变！ 首先一点值得肯定的是，运用这种方法，我们的确能够超越图灵计算了，只要反复不停 的变换我们的程序就不可能找出它不能解的问题。然而，另一方面又会让我们很失望：这样 的变换过程并不能给出一个实实在在的程序来！我们拥有的仅仅是不断改变的程序序列，而 不是一个实际存在的程序！ 这正是问题的关键所在：要想彻底超越图灵计算的限制，我们必须要放弃程序的实在性。 也就是说程序在每时每刻都要变化成不是它自己了。那么这样的一个不断变化得不是它自己 的怪东西存在么？ 几千年的人类科学一直在研究实实在在的东西。无论是原子、分子还是计算机程序，它 们必须是一个实实在在存在的个体，在这种前提下科学才能够对它进行研究！如果当我们研 究它的时候，它已经变得不是它自己了，那么科学就对它无能为力了。然而，我不禁要提出 这样的问题：真的一切都是固定不变的存在着么，有没有某种东西在每一时刻都在变得不是 它自己了呢？ 这个问题似乎是一个古老的哲学问题了记得赫拉克里特就曾经提到过：一个人不能两次 踏入同一条河流。我想他说的正是这样的问题：因为河流在每时每刻都不再是它自己了。河 流是一大群流动的水滴构成的整体，在每时每刻这些水滴都在不停的运动、流逝，因而当你 两次踏入这条河的时候，所有的水滴可能都不一样了，那么我们怎么能说这些水滴构成的整 体还是同一条河呢？ 再考虑我们人自己。你很可能拿着一个你3岁时候的照片兴奋的对你的朋友说：“看， 我3岁的时候多可爱呀！”。然而你这句话意味着什么呢？意味着照片反映的3岁时的你和现 在的你是同一个个体！然而，3岁的你和现在的你是多么不同呀！我们知道，你无疑就是一 大堆细胞构成的一个整体。而基本生理学知识告诉我们，实际上人体的所有细胞每隔大约4 年就会因为新陈代谢的作用全部更新一遍。也就是说，你的细胞全被掉了包了，更何况3 岁时候的你和现在的你差了多少个4年呀？那凭什么说那个3岁时候的你就是现在的你呢？ 这个问题看似玄学，不过我认为现在我们的确应该认真对待该问题了。尽管从分析的角 度来说3岁的你和现在的你的确不是一个个体，然而常识告诉我们，这两个你的确都是同一 个人！那就意味着，你这个个体并不是一成不变的一些固定的细胞，而是一个每时每刻都在 变化，都在更新的一个一大堆细胞组成的构形。这个构形在每时每刻都要利用更新的一大堆 细胞去维持自己的存在！我们得到了什么？和我们前面叙述的超越图灵机的讨论结合起来， 就发现，原来人还有赫拉克里特的河流这种东西刚好就满足那种超越图灵计算的要求。也就 是说人还有赫拉克里特的河流在每时每刻都在不停的更新它自己从而变得不是它自己了。那 么很有可能，某一种做类似变化的个体的变化规律就是不停超越它自己的图灵停机程序，这 样的虚幻的个体就真的能够超越图灵计算了！ 总结前面的讨论，我们不难给出结论，一个固死的能够被写出就不再变化的程序不可能 超越图灵计算的限制，然而如果一个程序每时每刻都已经变化得不是它自己了，这个程序就 能够超越图灵计算。联系到人这个个体，我们能得到：因为每时每刻的人都已经由于细胞的 变化而变得不再是它自己了，所以人是超越图灵计算的！还记得在前面我提到的一个问题么： “人脑的信息处理过程能不能被表示成固定的程序呢？”。我这里的答案就是否定的！也就 是说人脑信息处理的过程并不是一个固定的程序！如何制造真正的人工智能呢？很显然，我 们不能用一个简单的程序来构造，而必须是利用其它的方法，这个方法是什么呢？现在还没 有结论！ 七、悬而未决 到此，我已经把全部的有关图灵机、可计算理论、停机问题的一些重要概念介绍完了。 然而在计算理论这个领域里还有很多重要的问题没有介绍。但我不得不根据我的兴趣进行取 舍。在整个介绍过程中，一方面我介绍了人们已经得出来的结论，另一方面，我尽量把一些 没有解决的问题展现给大家。回忆起来，这些悬而未决的问题包括下面几个： 1、 是否一切的信息处理过程都具有固定的程序呢？人脑有固定的程序么？ 2、 如何用计算机程序进行归纳？能对所有事物进行一劳永逸的归纳算法是否存在？ 3、 什么是意义，更确切的，什么是语义？ 4、 图灵停机问题是不可超越的么？ 5、 人工智能是否可能？ 还有很多问题在本文中没有提出来，然而我认为也是相当重要的。例如，我们如何用图 灵机模型表示一般的学习过程？若干小的图灵机是如何自动的构造出更大的图灵机的（这就 是万事万物自组织的过程）？生命的目的性如何用图灵机模型表示？ 另外最近的计算主义已经把宇宙中一切的过程都归结为计算过程了，也就是说到处都是 图灵机正在做运算。那么我们能不能从图灵机的角度探讨时间和空间的本质呢？ 计算理论另外一大类问题就是探讨计算的时间和空间复杂度！！！
阅读全文(1619) | 回复(0) | 编辑 | 精华
|
