首页科技快讯计算机不是只会“计算”，图灵机也不是一台“机器”

计算机不是只会“计算”，图灵机也不是一台“机器”

来源：晰数塔互联网快讯时间：2020年06月03日 09:58

文章来自微信公众号：返朴（ID：fanpu2019），作者：王培，题图来自：电影《普罗米修斯》

人们往往根据自己的理解对一个概念下断言，其实对方使用的概念并不是你所以为的含义。要想避免这种误会，就不该对自己没有认真研究过的问题下结论。

在讨论人工智能的潜力和限度时，常常有人拿 “图灵机” 和 “可计算性” 说事。其论证大致是这样几步：

（1）既然人工智能是在计算机中实现的，其能力自然在计算机能力范围之内；

（2）现有计算机的计算能力都和图灵机相同；

（3）那些图灵机不能解决的问题当然也就是人工智能所无法解决的。

有些人会进一步主张：

（4）人脑不受这些限制，因此不等价于图灵机；

（5）所以人工智能的根本能力永远低于人类智能，尽管在某些具体能力上可以超过人。

由于人类智能或人脑的能力范围本身尚未有明确界定，4、5两步仍有争议（不少人相信人类的计算能力也受同样的限制），但前面三步却罕有反对意见。我下面要说的就是：这事不是这么简单。上面的论证，尤其是（３），在其通常解释下是错的。

“图灵计算”到底是什么意思

由于这个问题直接涉及对计算机科学核心概念的理解，我们不可避免地要从概念的定义开始。鉴于本文的性质，我会试图用日常语言把这事说得足够明白。

图灵近年来成了个广为人知的名字，这里就不介绍了。他在1936年的一篇文章中提出了一种抽象的 “计算机器”（computing machines），并用它来定义“可计算的数” (computable numbers）。请注意：在那时计算机 (computers) 尚未出现，而图灵的本意也不是要设计这样的机器，而是要为在数学中广泛使用的 “可计算” 这一概念提供一个严格的定义。

由于人们（甚至以严谨著称的数学家们）往往对同一个概念有不同理解，图灵试图用一个想象的机械装置来避免歧义。简单地说，如果满足某个特征的数字都可以在有限时间内被这样一个机械装置生成或识别，那么这类数就是可计算的。

在电子数字计算机（即今天所说的“计算机”）出现后，计算机科学中的 “计算” 概念沿用了数学中的传统意义，图灵机也被广泛用于刻画计算机中的各种过程，因而成为理论计算机科学的核心概念。在专业文献中图灵机的定义大同小异，下面的 “科普版” 改编自Introduction to Automata Theory, Languages, and Computation [1]——这个领域里最常用的教科书之一。

图灵机是一台可以逐个处理一列符号的装置，如下图所示。

对图灵机的完整描述包括七个成分：

1. 一个有限的输入符号集；

2. 一个有限的内部符号集（输入符号集的扩充）；

3. 一个特殊的空白符号（用来标记被处理的符号序列的边界）；

4. 一个有限的状态集；

5. 一组状态变换规则，根据当前状态和所关注的符号的组合决定新的状态和符号，然后将关注点前移或后移至另一个符号；

6. 一个特定的初始状态（初态），此时所有待处理符号都是输入符号，且关注点在第一个符号处；

7. 一组终止状态（终态），至此停止运行。

当且仅当存在一个图灵机，可以将一个问题的每个实例作为输入，并在有限的变换后停止运行，这时我们称这一个问题是 “图灵机可计算” 的。如果停止运行是由于达到了一个终止状态造成的，输入就算是被 “接受” 了。如果停止运行是由于没有变换规则可以应对当前情况，输入就算是被 “拒绝” 了。这个图灵机对输入符号串所作的 “接受还是拒绝” 的判定就叫一个“计算”。

下面我们描述一个简单的图灵机，叫它“机器甲”。它用0和1做输入符号，而内部符号是0，1，外加空白符 #。机器甲的状态只有A和B，外加一个终态Z，其中A是初态。其变换规则是：

• 如果当前关注的符号是0，把它改成 #，状态不变（A还是A，B还是B），后移至下一个符号；

• 如果当前关注的符号是1，把它改成 #，状态改变（A变成B，B变成A），后移至下一个符号；

• 如果在状态A下所关注的符号是 #（所有输入符号都处理完了），进入终态 Z。

不难看出，给机器甲一个01符号串（如0110111）做输入，它会逐个抹去其中的符号（把0和1都变成 #），最后用是否进入了终态来判定输入中1的个数是否为偶数。

现在让我们定义一个“机器乙”。它和机器甲完全一样，只是初态为B。机器乙所完成的计算也是确定输入中的1的个数的奇偶性，但 “接受还是拒绝” 的判定恰好与机器甲相反。

这两个图灵机尽管简单，但却已经揭示了一个普遍的误解：一个 “图灵机” 不是指一台“机器”，而是指一台机器的一个特定的运行过程或使用方式，包括对初态和终态的划分。上述的机器甲和机器乙是同一个装置，但完成的计算不同。同理，对任何其它图灵机，只要修改其初态或终态的划分，它就成了不同的图灵机，所完成的计算也就不同了。

计算与智能

一个系统的 “初态” 和 “终态” 的划分并不像看上去那么无关大局。现在让我们考虑 “机器丙”，它和机器甲基本相同，只是取消了状态 Z和最后一条变换规则。这样一来，当所有符号都成为 #，机器不再有适用变换规则，就会停在当前状态，而这个状态同样可以代表输入中1的个数的奇偶性（A对应于偶数，B对应于奇数），因此也可以被用作机器丙的计算结果。这台机器在处理完一个输入序列后，只要将状态重新初始化为A，即可以处理下一个序列。

一个有趣的问题是：如果不做状态重新初始化，情况会怎样？显然，如果机器丙在一次计算之后状态停在B，则下次计算这个机器就变成机器乙了，并且后面会不断在机器甲和机器乙之间转换，而不再完成一个确定的计算。这个机器的处理结果不仅仅取决于当前输入，还取决于开始处理这个输入时的系统状态，而这个状态是系统的历史决定的。

这种可能性乍看起来没有讨论价值。一个符号串里面有多少个1，与处理机制的历史和状态不应该有任何关系，所以对应的计算当然必须从同一个初始状态开始，这才能保证过程和结果的确定性，或者说可重复性。

但 “计算” 的概念不足以涵盖所有与智能、认知、思维等有关的过程（见参考文献 [2] 中的讨论）。尤其像那些和“学习“、”适应“、“灵机一动”有关的现象，根据定义，它们不是对问题的可重复解决。严格说来，一个不断学习的系统是不重复先前的内部状态的，因此即使是相同的输入，处理过程和结果都未必相同。在这种情况下，相对于这个输入而言，这台装置就不是一个图灵机，尽管它可以具有图灵机定义中的前面5个成分，就像机器丙那样。

图灵机模型。来源：Wikipedia，by Rocky Acos

当然，如果我们把这个装置的 “出厂” 状态看作初态，“报废” 状态看作终态，那么其整个“生命周期” 仍可以被看成是一个图灵计算过程，其输入由它历史上所经历的所有输入符号串衔接组成。但问题是，这个周期和我们平常关心的 “解题周期” 不是一回事。如果这个系统在学下棋，那么我们通常会把每盘棋看作一个要解决的问题，而这和把整个 “学下棋过程” 当作一个问题是非常不同的。

相对前者而言，系统的解题行为应该是随着时间而变的（否则何谈学习），因此不是一个 “下棋图灵机” 。这种变化是因为前面解题周期的终态成为了后面解题周期的初态，而不需要引入其它因素（如“自由意志”、“量子效应”、“随机选择”等等）来解释。

那么能不能说 “这个系统仍是图灵机，只不过在下每盘棋时它是一台不同的图灵机”？

如果硬要这么说也不能算错，只不过没有任何实际价值。在数学和计算机科学中，可计算性的研究都是以严格可重复的解题过程为研究对象的，其结论的价值也正在于为未来的解题过程提供可靠预测。如果一个解题过程不可重复，说它 “每次都是个图灵计算，但说不准是哪个” 和说这个过程 “不是图灵计算” 就没有实际差别了，反正也不知道它会怎么做。

类似地，说这个系统的解题过程仍是可重复的，但这个过程要包括系统从 “出生” 开始的全部历史，这也没错，但即使如此，它的下棋过程也是不能看成图灵计算的。

既然图灵机指的不是某类装置，而是（装置中的）某类过程，就不能用它对应于一台计算机，而是对应于（一台计算机中的）某个程序或过程。图灵机在计算机科学中的重要性也就在于，严格、清晰地表达出一个符号（数据）处理过程——这样我们就可以用一种统一的术语刻画到底哪些过程是“可计算” 的，而不再依赖直观或模棱两可的语言。

前面的讨论也说明，并不是计算机中的所有过程都可以或应该看成“计算“，并等价于图灵机的。这里最重要的是那些由于包含了学习、适应、进化等机制而成为不可重复的过程，尽管它们仍和计算有关。这有点像搭积木：每个积木块都是预制的，但如何把它们组合在一起却是可以临时起意，不循常规的。这样的系统的计算能力并没有超过图灵机，但可以完成一些不能被称为“计算”的功能。

我设计的纳思系统就是这样：其中每个基本步骤都是提前编好的程序，或者说都是图灵机。但面对一个具体问题时，如何把它们组合起来使用，却是靠系统现场发挥，没有预先写好的脚本的，因此对一个问题的处理是依赖于系统当前状态的。

在一个 “生命周期” （以记忆的初始化为界限）中，其内部状态不重复，因此它对同一个问题的处理也不一定是严格可重复的，即不是图灵计算。当然，这不说明系统在任何问题上都没有稳定答案。

人脑是个图灵机吗？根据上面的讨论，我们会发现，这不是个有意义的问题。人脑中的某些相对简单的过程可能被近似地被图灵机（计算机程序）模拟，但仍有大量过程是不能这样处理的。这可能是由于我们对这些过程的了解还不够，也可能是它们本来就不是严格可重复的。至于这些功能是否可以由人工智能中的非计算性的过程所再现，则不是本文要讨论的了。

“顾名思义”的功过

本文的讨论还涉及一个普遍的现象。对不熟悉的概念，顾名思义是个有效的认知策略，但也是误解的常见来源。对科学概念尤其如此。我在《新理论该怎么为概念下定义？》中讨论过这个问题。当我们将一个新概念引入一个理论中的时候，为了促进其传播，常会选用一个含义接近的日常词汇。但这样做的危险就是：圈外人会按照他们的固有观念来理解相关的科学结论。

比如说，人们往往认为 “计算”是包含了计算机所能做的一切，但在计算机理论中，这个词仅指使用计算机的一种常见的（但并非唯一的）方式。把这二者搞混，就会得出“人工智能的能力范围仅限于可计算的问题” 这种错误结论。

至于把图灵机看作一种计算装置，则是典型的顾名思义了。甚至很多计算机专业出身的人在学过图灵机的概念之后，仍没有意识到其定义中包含初态、终态所造成的限制，而理所当然地认为这是描述一个装置时所必须的。

造成这个混淆的更深层原因就是计算机科学中的数学遗产。什么是“问题”？怎样算是“解决”？在数学中，“解决”总是相对于一个问题类而言的，解题过程和结果都必须是严格、精确、可重复的。而在数学之外的生活中，由于必须迎接新的太阳，踏进不同的河流，所以不能以同样的标准论成败。

最后一个例子就是“通用人工智能”了。一个常见的意见是：“显然不存在能解决所有问题的通用智能”，但稍微读些文献就会发现，真正在这个领域中工作的人，并不是在这一意义下使用“通用”这个词的，而是把它作为“专用”的对立面。所以，在这里，“通用系统”不是“万能”的意思，而是“可以合理应对意料之外的问题”的意思。

这种误会在科学讨论中并不罕见：根据自己的理解对一个概念下断言，其实是攻击了一个稻草人——因为别人不是在这个意义下使用这一概念的。要想避免这种误会，就不该对自己没有认真研究过的问题下结论。

“顾名思义”是不可靠的，尤其针对那些“显然”的问题而言。如果真是那么显然，别人怎么会看不到呢？对人工智能类似的误会不少。我在参考文献[3]中对此有进一步讨论。

参考文献

[1] John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd edition, 2006

[2] Peter Kugel, “Thinking may be more than computing”, Cognition, 22:137–198, 1986

[3] Pei Wang, “Three Fundamental Misconceptions of Artificial Intelligence”, Journal of Experimental & Theoretical Artificial Intelligence, 19(3), 249-268, 2007

文章来自微信公众号：返朴（ID：fanpu2019），作者：王培