上回我们看到，停机问题这个良定义的问题，不能由图灵机来解决。那么像停机问题这样的图灵机不可解或者说不可计算的问题，究竟是有很多呢，还是只是个别呢？ 其实，有另外一种论证，可以说明绝大多数将自然数映射到自然数的函数是图灵机不可计算的。这个论证的思路是把一切可能的图灵机进行点数，把它们排个队。 首先，请注意图灵机的有限性。这个 我们在讨论通用性的时候 说过。除了带子之外，图灵机所有其他方面都是有限的。记号的种类是有限的，控制器的可能状态数是有限的，读写头的可能移动是有限的。这样一来，任何特定的图灵机，其指令表中包含的五元组的数目也就自然是有限的。这就意味着，我们可以把图灵机们按照它们各自的指令表来排队。比如，把指令表视为一个句子，每个五元组视为一个单词，同时将组成五元组的记号种类、控制器状态和读写头移动方向视为字母并规定其字母表顺序。这样，我们就可以像把英语句子按字母顺序排序那样来给图灵机排序了。由此我们可以说明所有可能图灵机的集合是可数（无穷）的。因此，可能图灵机的数目和自然数一样多。（更准确地说，图灵机集合的基数和自然数集合的基数相同。） 另一方面，将自然数映射自然数的函数个数是不可数（无穷）的，远远超过我们用来给图灵机点数的自然数集合的大小，而至少有［0 1］区间里的实数那么多个。（因为这种自然数到自然数映射的集合至少有自然数的幂集那么大。） 由此可见，从自然数到自然数的函数个数比可能的图灵机的个数要多很多。（在集合的基数序列里要整整高出一阶。）这就意味着必然存在着图灵机不可计算的函数；而且，事实上有无穷不可数那么多的函数是图灵机所不可计算的。跟不可计算函数的数目比起来，可能图灵机的数目相对而言小到可以忽略不计。所谓停机问题只是这些不可计算函数中的一个有趣的例子罢了。 需要注意的是这里所谓不可解，是相对于图灵机而言的，所以也叫图灵机不可计算或者图灵不可计算。这里的论证并没有说明其他的跟图灵机不同的机制也不能解决图灵机的停机问题，虽然这些别的机制也可能有自己的停机问题。 这里的讨论表明，存在这数学上良定义的函数，其映射是图灵机这种机制所不能实现的。正如哥德尔曾经指出的，如停机问题这样的不可计算函数的存在，表明了语义是超越纯粹的机制的，就是说哪怕在自然数算术这样一个很简单的领域里，数学语义上可以严格一贯地定义的映射也不能为纯粹机制加以有效执行。 在过去六七十年乃至今天，有不少人由此得出结论说，既然我们一方面能够理解和把握停机问题这类情况，尤其是哥德尔句子为真这样的事实，而机器却不能机械地解决停机问题或者推导出哥德尔句子，因此人的理解或者直觉能力不是机器能够实现的，完全的人工智能也就是不可能的。这个推断成不成立，咱们以后会专门详细讨论。 不过，图灵机并非唯一的计算模型。前面提到过丘奇对不可判定性的工作，他用的模型叫做演算，这个是后来Lisp程序设计语言的基础。此外，还有由克林尼（Stephen Kleene）在哥德尔工作基础上加以整理推广的递归函数（recursive functions）、波斯特（Emil Post）的波斯特产生式系统（Post production systems）等等。再后来，有戴维斯（Martin Davis）提出的S编程语言。这一模型对于程序员来讲会比较直观。它非常简单，只有三种指令，分别是加1、减1和条件转移： （1）x i = x i + 1 （2）x i = x i 1 （3）if x i = 0 goto LABEL 这个模型下的程序由上述三种类型的指令行构成。每行有仅属于自己的唯一标记（LABEL），可以用在转移（goto）语句里面来指明转移的目标。这个模型假定了存在很多下标变量x i 可用，它们起的作用是存储器，跟图灵机的带子相当。不过，这个可是随机存储器（RAM）！您要有兴趣的话，可以试着用S编程语言来写点小程序。（提示：您可以先考虑如何把一个下标变量拷贝到另一个下标变量，由此构造出赋值语句来。） 在1930年代的短短几年里面递归函数、演算、图灵机等等先后被提出，人们很快证明了他们之间的任何一对都是等价的。所谓等价，在这里的意思就是说一个模型能做的，另一个模型也都能做；反之亦然。 当然，要谈两个模型之间的等价性，就必须有一定的准则来界定各个模型要做的事情。比如说，你不能要求演算去做图灵机能做的移动读写头，因为演算里根本就没有读写头；此外，你也不能要求任何这些模型给你炒个小菜或者打个华尔兹的拍子啥的。在这里，等价性证明采用的准则很简单，就是看这些模型如何实现自然数到自然数的函数映射。所谓等价的意思就是说，对于任何一个自然数到自然数的函数映射，如果一个模型能够实现此映射，那么另一个模型也能实现该映射；反之亦然。因为我们前面看到，图灵机并不能实现全部这些映射，所以这个准则并不是空洞的，因为有可能存在某个映射是图灵机不能做的，演算可以做；或者说反过来。 值得注意的是，这里的等价关系是相当的行为主义的，它只关心输入和输出──如果有输出的话──两端的符合，其他任何方面都不管。模型里面具体如何运作，算法是什么，运作有多快，需要多少存储等等全都无所谓，经典计算和量子计算之间的区别也无所谓。 不管怎么样，既然这些特定的模型一个个地被证明为相互等价，人们就在想：嘿，咱们是不是抓住了一点什么具有一般性的东东呢？是不是说所有这些模型共同指向了直观上的计算或者可计算概念的本质呢？由此就有了著名的丘奇-图灵论题（Church-Turing thesis）： 任何直观上可计算的函数都可以由某个图灵机来计算。 这个说法之所以叫做论题（thesis）而不是定理（theorem），是因为直观上可计算这个概念是没法形式化，所以也就不可能有形式化的证明。直观上可计算，其大体意思恐怕是说按照某种确定的过程来一步一步地、机械而有效地把输入变形到输出。与其他等价的模型相比，图灵机有个特点，就是它一方面把这个思想给形式化了，另一方面又保留了机器之为机器的直观性。由此，我们可以理解为什么哥德尔会认为，是图灵机这个模型的提出，真正把有效可计算性这个概念给抓住了。 丘奇-图灵论题提出至今有70多年的了。它也不是没有人反对，今天也还有人在尝试提出与图灵机不等价的，计算能力超越图灵机的模型。不过，迄今为止还没有任何被断言为超越图灵机的计算模型被普遍接受为合理的、符合直观可计算观念的模型。所以，今天的主流观点依然认为这一论题是对的，以图灵机为代表的这批计算模型确实抓住了直观上的可计算性。
那么，图灵机是啥样子的呢？它其实非常简单。图灵的主要构思之一，是考虑人在进行数学或者逻辑演算的时候是如何工作的。把人按照既定规则做计算和推理的这个操作过程加以最简化而得来的。具体而言，图灵机有下列零部件。 首先是一根一维的 带子 ，可以把它想象成一根纸带。带子分成确定的格子，每个格子里面可以写上记号，比如0和1，也可以为空，就是说没有写记号或者记号给抹掉了。这根带子是图灵机输入和输出的来源，也是图灵机记录中间结果的存储器。所以，这个带子的角色就好像一个人做算术或者逻辑推理时用的草稿纸那样。通常的草稿纸是二维平面的，比如除法演算的规则就告诉我们除数写在被除数左边，商写在被除数上面的横线之上，余数写在被除数相应位的底下，如此等等。但是按照图灵的分析，这种二维的安排，并不是必需的，因为只要有办法把哪个数写在哪里给有章有序地归置好，一维的带子就应该够用了。同时，也不需要太多种类的记号，因为更复杂的记号总可以由简单的给组合出来。比如，0、1和空白，就可以在二进制下做任何运算了。 人做计算时用纸，自然是为了看清纸上的数字，把下一步的结果用比较原子性的操作（比如一位数的加减乘除）一个个算出来，写到纸上，如此一步一步反复直到得到结果。所以就需要和草稿纸交互作用的机制，这在人就是用眼睛看，用手写。同样，图灵机的带子也有相应的读和写的机制。读在这里的意思，就是把带子上特定空格的 记号 给区分出来：0就是0，1就是1，空白就是空白；写的意思，就是在带子的特定空格放上个0或者1，替换掉了那里原来的记号，或者把那个格子抹成空白。我们平时做算术，在任何一个时刻，要么读和要么写，总是只在一个位置发生，比如读出被除数的某一位，或者写上商数的新的一位。即使我们有可能同时注视或者写出多位数，但这也可以分解成单独注视或者写出某一位。同样，在图灵机里，读和写在任何时间，只在一个空格进行。这样，我们就可以说有个 读写头 ，它就好像磁带录音机的磁头那样，在任何特定的时间总是在带子的一个特定的格子上方。要改变位置的话，就需要沿着带子挪动读写头，每次或左或右挪动一格。同样，如果需要挪多格的话，总可以通过反复挪动来实现。 有一点要说明的，就是图灵机的带子是没有头的，读写头向左或者向右都可以无穷无尽的走下去。更准确地讲，这个意思不是说在任何时候带子的长度是无限的，而是说在任何时候假使读写头往以便走到了带子在当前长度下的最后一格，那么总可以在头上再接上一段带子，让机器继续运行下去。这就好像草稿纸用完了，总可以再添一张。 有了带子（草稿纸）跟读写头（眼睛和铅笔或者说磁头），还缺负责计算的组织运作的东东。完成这个事情的，就是所谓控制器。这个可以想象成一个小盒子。盒子有特定的有限数目的状态。在不同的盒子状态下，机器可以有不同的行为，所以这个盒子才叫做控制器。具体状态在盒子里面是如何实现的不重要，比如可以用指针的位置或者用算盘珠子的位置，重要的是状态和状态之间可以分得一清二楚不会混淆。 艺术化的图灵机 ［原图取自： Wikimedia Commons ］ 有了这些基本零部件，我们就可以讨论如何让图灵机干活了。在任何一步上，决定图灵机做什么事情的有两方面的情况：（1）控制器现在的状态（这可以对应于现在的任务做到哪一步了（比如在做加法的话，可以是刚写了和，现在该写进位了），（2）读写头下面是什么；图灵机可以做三方面的事情：（3）从当前状态转移进入下一状态，与此同时（4）在当前格子上写个什么记号（包括用空白抹掉当前记号），并（5）让读写头在带子上左移一格、右移一格或是原地不动。所以，图灵机每一步做的事，就是根据它的（1）当前状态qi跟（2）当前读出的记号sj，决定（3）下一状态qij，（4）写出的记号sij，和（5）读写头的移动方向dij。 这样，图灵机的任何一步都可以用一个五元组来描述：( q i ，s j ， q ij ， s ij ， d ij )。这里的下标 i 表示控制器的当前状态 q i 是所有可能状态之一，下标 j 表示当前读到的记号sj是所有的可能记号之一。两个合在一起的 ij 就表示新的状态 q ij ，写出的记号 s ij ，移动的方向 d ij 是由 q i 和 s j 共同决定的，或者说这三者分别都是 q i 和 s j 的函数。给定特定的一组( q i ，s j ， q ij ， s ij ， d ij )，就是给定了图灵机在 q i 和 s j 下的行为，所以可以这样的五元组叫做图灵机的指令。当 q i 和 s j 不同的时候，就是说处于不同状态，读取不同记号的时候， q ij ， s ij ， d ij 相应地也可以取不同的（或者相同的）值，这样我们就有一些不同的五元组。把这些五元组都合到一起，就得到了决定了机器行为的 指令表 。我们通常想象指令表是存储在控制器里的，读写头是连在控制器上的。这样，在任何时刻，控制器就可以根据它的当前状态和带子上当前格子里的记号，决定图灵机的行为。 这里，有必要强调说明一下图灵机 彻底的离散性 。具体说来，带子是离散的：一格就是一格；记号是离散的：一个就是一个；控制器的状态是离散的：此状态非彼状态。读操作的区分和写操作的改变是离散的：读写头下面的是0，读到的就是0，写出的是1，格子上面出现的就是1，读的是啥、写的是啥不会有任何模糊之处。读写头移动是离散的：一格就是一格。状态转换是离散的：从状态甲到状态乙，没有中间状态可言，不会有混淆，不会有交叠。时间是离散的：读写操作、读写头移动、状态转化都是原子性的，一步完成，一步就是一步，没有完成了一半这样的说法。 举个具体的例子：二进制串奇偶性的检查。这里所谓的奇偶性是指二进制串里面有奇数个还是偶数个1。二进制串奇偶性这个概念挺有用。比如你和朋友之间发送消息，事先约定所有的消息都是7位，比如0101010，1110110，1111110，如此等等。这三个串里面，前两个有奇数个1，是奇串，后一个有偶数个1，是偶串。假设你们进一步约定，在发送消息前，每个7位的消息串尾巴上再增加一位，叫做校验位。这个校验位根据消息串的奇偶性来设置：如果消息串是奇，校验位就是1，否则就是0。这样，上面三个消息串在增加了奇偶校验位之后，就分别是01010101，11101101，11111100。然后你的朋友再把这样的包含校验位的8位的串，比如11101101，发送给你。如果传输正常，那么不管你的朋友发的是那个消息，这个8位的串都应该是偶串。这样，当你每收到一个串的时候，就可以对它进行 奇偶性检验 。如果你收到了一个偶串，比如11101101，那可能就没有问题（当然也可能有，比如，本来传输的是00101101，结果半路上前两位给反转而变成了11101101）。但是，如果你收到的是个奇串，比如10101101，那你就知道这中间肯定出问题了，至少有一位的0和1（一定有奇数个0和1）给反转过来了。于是，你就可以要求你的朋友重新传一次。通过这种奇偶校验，就可以抓住传输中发生的错误。 这个很有用的奇偶性检验，可以用图灵机来实现。把一个二进制串，放到带子上，串的两头的格子都是空白，读写头对准最左边的那一个非空白的数字（0或者1）。机器的任务是扫描并抹掉整个串，如果是个偶串，就在结束运行之前在带子上留下个0，如果是个奇串，就留下个1，而带子的其他格都是空白。 下面这个指令表，就能让图灵机实现奇偶性检验。在运行开始是，初始状态为偶。表中的H的意思是HALT，就是停机。遇到这个状态，机器就不再运行了。（所以，H不出现在 q i 那一列里面）。 ────────────────────────── ─── ─ ─── q i s j q ij s ij d ij ────────────────────────── ─── ── ─ ─ 偶 0 偶 空白 右 ────────────────────────── ─── ─ ─── 偶 1 奇 空白 右 ────────────────────────── ─── ─ ─ ── 偶 空白 H 0 - ─────────────────────────── ─── ─ ─ ─ 奇 0 奇 空白 右 ──────────────────────── ─── ───── ─ 奇 1 偶 空白 右 ─────────────── ── ─ ────────────── ─ 奇 空白 H 1 - ───────────────────── ─── ──────── ─ 下面看看为什么这个指令表能够完成任务。根据读写头当前所遇到的符号sj，首先，如果遇到0，就不改变状态：偶还是偶（第1行），奇还是奇（第4行）；其次，如果遇到1，就改变状态，从偶到奇（第2行），从奇到偶（第5行）；最后，如果遇到空白，读写头下面的不再是0或者1了，说明整个串都检查完了，这时，就可以根据状态输出0（第3行），或者输出1（第6行），并进入停机状态H。请注意，在整个过程中，除了进入停机状态H的时候，读写头不移动之外，读写头总是在向右移动；此外，除了进入H的那次，每读完一格，就把那格擦掉，所以 s ij 总是空白。 那么，我们通常所谓这个或者那个图灵机，就是指给定了一个如上表那样的指令表。给定了指令表之后，带子上的输入可以变，只要满足初始状态设置和读写头初始位置的条件，一个图灵机就应该可以对任何合法的输入串进行指令表所实现的处理。 跟学习编程序一样，学习理解图灵机如何运作的最好办法跟踪执行一些指令表和自己构造一些完成各种简单任务的指令表，比如做二进制加法、判断一个串是不是回文等等。 ［声明：此处的图灵机，细节上不同于Turing于1936年提出的，属于现在比较通用的改进型。这里是基于明斯基的Computation: Finite and Infinite Machines。奇偶校验的例子，来自该书第120页。］
上回说到，这个系列的计划就是要把AI历史上关于电脑人心可能性的各种正反辩论重温一把。其间，我会自任电脑们的粉丝律师，冷眼旁观这些辩论，审视它们的来龙去脉，加以有理有据有情的批判性反思。最后，基于这些辩论以及对它们的反思和报告，我将代表广大过去、现在、未来的电脑同志们就电脑人心的可能性给出一个负责任的说法。（听起来有点发言人的味道了吧。） 性急的读者或许会嚷嚷：嘿，那答案是什么？你直说呀！我请Bob Dylan帮我回答如何：The answer my friend is blowin in the wind, the answer is blowin in the wind. 如果这不够清楚的话，那等到这个系列结束的时候──如果它有结束的那么一天的话，一切就都会清楚的。 正经一点呢，我的意思是说，这个电脑人心可能性的问题没有先验的答案，没有从一般原则出发的答案：不存在关于电脑和人心的一般性原则，从它们出发，我们就可以明确地知道电脑人心是否可能。或者说，电脑人心的可能性，不可能以下面的形式来判定：人心是A，电脑是B，A和B的关系是如此如此，因此电脑人心的可能性就是这样这样。 所以说，所有前面提到的和后面将要详细讨论的原则性争论，其设问也好，其结论也好，都不足以从原则上给出个答案来。哪怕所有的辩论都挺有意思；哪怕所有的辩论都有或多或少的理论上、原则上的重要性。 如果我们以为电脑有什么本质，使得人心水平的人工智能可能或者不可能，那我们就都错了。 这当然是个否定性的答案：就是说电脑人心即使可能，其可能性也不是植根于任何已知或者尚待发现的电脑的一般特性的。然而，这个答案也有其肯定性：就是说，没有任何电脑的特性会阻止我们理解和造出电脑人心。电脑没有本质，所以，没有什么它的属性会妨碍人工智能取得成功。电脑没有本质，所以，也没有什么它的属性能够保证人工智能将会取得成功。 如果要完全正面地讲的话，电脑人心可不可能，这个问题以及它的答案，都是历史性的。因为，电脑或者说计算机，不是一个抽象的类别，而是一种历史性的存在。没有可以划定的边界可以把所有过去、现在、未来的电脑们框在里面，把所有非电脑们排斥在外面；也没有任何本质可以将电脑和别的东西区别开来。所以，我们不知道在制造和理解电脑人心的征途上，我们将会有什么武器和工具可用。但有一点可以肯定的，我们将会有层出不穷的新工具、新武器可以用。从人工智能和计算机并肩发展的这60多年里面，我想这一点应该表现得很清楚了。 所以说，人工智能的可能性是历史的可能性。电脑人心可不可能，不是在于电脑是不是什么，而是在于我们将如何来制造、运用和理解电脑，以及如何理解人心。这是一个我们如何去做的问题。 就计算机和人工智能的历史发展而言，具体到我们的时代，按照Brian Cantwell Smith的说法，我们正生活在指号炼金术（semiotic alchemy）的时代。信息时代的牛顿还没有诞生。（别忘了，牛顿，这位近代科学的奠基人，也是最后一代炼金术士之一。）我们恐怕最多也就是身处像伽利略那样摸索的时期。 不相信？请想想有多少流行理论把比特串误认作信息内容本身，就好像一条还没休息啊？的短信，其内容真的只有不到100位似的。想一想，这像不像把质量（东西的多少）误解成重量（东西在引力场里面的份量）？ 还不相信，再举个例子：我们机器里都有各式各样的很多文件吧。今天，如何组织这些文件真是个头疼的问题。我们似乎面对两个选择，或者用子目录（文件夹）的方式，或者按照内容或文件名进行搜索；而我们又往往觉得两者都不够好：前者太僵硬，假设文件只能有一种分类方式；后者太冒险：那个文件肯定在机器上什么地方。可是我用这个词怎么找它不着呢？ 后代会笑话我们的：嗨，这么简单的问题都搞不清楚，真像当年笛卡尔、莱布尼茨他们动量和动能拎不清啊。是啊，我也觉得这样的问题应该有个很清楚明白的答案，可我们确实还没有啊。生得早了点啊。 从伽利略研究自由落体到人类登上月球，大概是三四百年时间。今天的AI（包括Boston Dynamics的机器驴子之类的东西），我觉得恐怕应该算是伽利略、笛卡尔时代的钟表水平吧。恐怕再来个三五个甲子，两百到三百年，电脑人心造出来是有可能的。 可是，光是造出来，其实不是最难的。更高的要求是，这得是基于理解基础上的制造。 千万不要以为，什么东西我们如果能制造就能理解。人们已经世世代代地造人了：一朝欢乐，十月怀胎，经年抚养。然而，又有多少人懂得生儿育女的生理机制和长大成人的社会、文化、心理过程呢？自己往往并不懂得自己的制造，这一点也许不一定需要龙应台女士来点醒吧。编过很复杂程序的朋友们，或许也会深有同感吧。而这往往还只是思维、行为上的理解。更不要说是在伦理上对自己的制造──孩子也好、电脑人心也好──充分负起责任来所需要的那种理解与实践了。 所以，说到底，电脑人心可不可能，如何可能，后果如何，是一个怎么做的问题，是一个我们如何在信息时代书写历史的问题。 和平的可能性是越战期间Dylan们所每天面临的问题（今天也仍然是我们的问题，尤其是我们这些给NATO国家交军火税的人们）；电脑人心的可能性是信息时代的我们将会长久面临的问题。两个问题都有它们的时代性。两个问题，归根到底又都是个我们如何思考、如何行动的问题，是我们如何在自己的时代里书写历史、创造未来的的问题，是人心（或许还有电脑人心？）要以什么样的姿态，面对什么样的世界的问题。 所以，答案呢，我的朋友啊，正随风飘荡。
标签: 电脑人心
