图灵死机问题和相关理论的局限性以及可如何推翻之

戴榕菁

 

一. 问题的背景

图灵死机问题（Halting Problem）说的是著名的数学家和电脑先驱图灵在1936年证明的这样一个结论：不存在一个可以判断任意一个程序是否会死机（死循环）的一般程序（算法）。

过去几十年里，图灵死机理论的价值在很多时候，尤其是哲学意义上，被过度夸大了一些，常被一些人誉为上个世纪的最伟大的理论发现之一，且认为它的发现揭示了人类的逻辑能力的一种极限性。其实，与哥德尔不完备理论，皮亚诺理论，塔斯基理论等与之类似的理论一样，与其说图灵死机理论所揭示的是人类逻辑能力的极限性，不如说是人类在特定环境下的不现实的梦想与现实之间的差异性而已。

这里特别要注意的是图灵所证明的是不存在一个可以判断任意一个程序是否会死机的一般程序，而不是很多对软件技术缺乏了解的人常误解的那样是无法对任意一个程序是否会死机进行判断的可能性。如果我们对于“是否能对任意一个程序是否会死机进行判断”都不确定的话，那么今天的世界不知要多出多少灾难了。

在现实实践中，我们其实是有能力对任何一个程序在运行中是否会出现死机进行判断的，这是软件工程师们的一个基本技能，也是我当初最拿手的本领之一。图灵的问题出在当初有人想要找出一个万能的算法（程序）来对任意的一个程序是否会出现死循环这一点进行判断，而图灵证明那是不可行的。因此，图灵死机理论其实对于软件工程们的日常的查错活动没有任何的指导意义，它的真实意义是在于唤醒有些人在当时的条件下的过度的梦想而已。

二．图灵理论的破解

如上所述，图灵的死机理论所反映的不过是对于人们在特定环境下的梦想与现实之间的差别而已，而不是人们在日常生活和工作中的能力极限。对于这一点的认识让我们很容易想到一旦人类的技术条件发生了变化，图灵的死机理论是否会如同历史上很多对于当时无法实现的梦想的论断一样而受到挑战呢。

事实上，我们可以合理地证明，图灵的死机理论至少是在他的现有的论述形式上是可以被推翻的。推翻图灵死机理论之结论的逻辑其实很简单：

1）图灵的死机理论并不影响软件工程师们日常工作中对于任意一个软件运行过程中出现死机的可能性及其原因的侦破；2）这个世界上的电脑硬件系统的运行方式，电脑操作系统以及应用编程软件语言的数量是非常有限的；3）尽管在现实世界的无数个软件程序的运行中可能导致运行死机或失败的原因可以是千奇百怪，但是他们的总体的模式却是有限的，不外乎死循环（例如由A点goto B点，然后再回到A点，再无限重复），饥饿等待 (starvation, deadlock)，以及内存泄漏（memory leak）等等一些一般的模式，而这些问题常可反映在运行log或trace中；4）任何计算过程都要最后以机器语言进行，对于高级语言来说，还要先转换为汇编，然后再转换为机器语言，因此如果在运行log以及在trace中找不出原因，就可以直接分析由系统产生的汇编语言或机器语言来寻找其中有限的循环指令，对函数（function）和子程序（subroutine）的调用，公共资源的分享等等可能导致死机的部位所进行的数据交换的逻辑分析，由于这些部位的数目是有限的，所以，一旦存在可能造成死机的因素，一定能够通过这些查找的步骤来找出其中的原因。这就是人类的软件工程师们一直在干的事情，完全不受图灵死机理论的结论影响。

基于上述4点，我们知道，随着人工智能（AI）技术的发展，人们就完全有可能编写一套人工智能（AI）程序来完成软件工程师们所要进行的判断任何一个实际的软件程序能否在所有的目标条件下正常完成运作的工作。

由于这样的人工智能（AI）是一个程序（算法）而且能够对任意一个程序进行判断，因此图灵的死机理论在现有的论述基础上就已经可以被推翻！

图灵的死机问题涉及到三个对象，其一是所谓的图灵电脑，其二是被测试的程序软件，其三是用来进行测试的算法（程序）。人类不可能把任意一个所谓的图灵机器以及被测试的程序软件当作一个黑箱来处理它的运行问题，而一定是深入到包括图灵电脑和被测的具体程序的具体运行来进行查错，而模仿人类软件工程师运作的人工智能（AI）程序也一定不会将所谓的任意的图灵机器及被测的程序软件作为一个黑箱来处理，而是要如同人类软件工程师那样地深入到具体的细节中查错，这就是人工智能（AI）与图灵在他的论证中设想的一般算法之间的根本区别。具有较高的哲学素养的人应该能够看出这里的区别是一种特殊的哲学区别，如果不具有那么高的哲学素养的人就不必往这个方向去考虑了，因为今天的专业哲学界（100%）肯定没有人能够看出这里的哲学意义上的区别来。

为了便于理解上面这些论述，先提醒读者一点：判断死机的问题只对于出现长时间不能正常完成运行的软件程序才有需要。对于短时间内可以正常完成运行的软件程序，答案已经非常明确所以不需要另找软件进行判断。当然，这不等于说正常软件就不能被上述的人工智能（AI）程序来判断，恰恰相反，它们肯定将是软件工程师们在编写上述的人工智能（AI）程序时首先会用到的测试程序。

当然，人们可以对图灵死机理论进行论述上修改，在其中加入“不可使用人工智能AI”这一条件，这样一来人们便可继续维护图灵理论的价值名誉了。

三．与图灵死机理论相关的其它理论的类似问题

前面提到，图灵死机理论的出现是因为有人在当时的环境下想要拥有一个可以对任意的软件程序是否会出现死机进行判断的一般程序（算法）；类似地，因为大数学家希尔伯特有一个类似于找到可以表达所有的数学真理的完备又不自相矛盾的公理体系，所以便有了表明那个梦想不可能实现的著名的哥德尔不完备定理（Incompleteness Theorems）。关于哥德尔不完备定理的论述及其证明网上有很多详细的介绍，这里就不赘述，其基本意思就是说上述的希尔伯特的那样的梦想是不可能实现的。

如果说图灵的死机理论是因为它涉及到很多人都有的梦想而有名，那么哥德尔的不完备理论之所以有名最主要的恐怕还是因为做梦的那个名叫希尔伯特的人太有名了。与希望有一个能够判断所有的软件程序能否正常完成的梦相比，会去做用一个完备又不存在矛盾的公理体系来统一数学理论的梦象的人除了象希尔伯特那种等级的人应该是不多的。

图灵的死机理论与哥德尔的不完备性理论已被证明在逻辑上是一致的。因此，哥德尔的不完备性定理面对的挑战同样是：尽管我们找不到那样一个既完备又无自相矛盾的公理体系，但这与我们日常的逻辑思维没有任何关系。我日常的逻辑思维既不会因为找不到那样的公理体系而出现逻辑上的矛盾，也不会因为找不到那样的公理体系而在我们的思考对象中漏掉任何一个项目。

当然，我们无法象推翻图灵的死机问题的论述那样地来推翻哥德尔不完备性定理，也无法用人工智能（AI）来推翻哥德尔当年创立的用哥德尔数（Gödel numbers）对他的不完备定理的证明。这是因为他的论述不像图灵死机理论的论述那样留有可以被人工智能（AI）推翻的余地。但是，我们也不需要推翻它，只要知道哥德尔不完备性定理并不是如很多人常喜欢指出的那样是反映了人类的逻辑思维的局限，而只不过是反映了顶尖数学家们的一些美好的梦想与人类的现实能力之间的差异而已因此丝毫也不会影响我们日常的逻辑思维这一点就够了。也就是说，我们只需要象对待图灵死机理论一样指出哥德尔不完备性定理的局限性就够了，因为它们的问题的共同特点是它们的论述对人们产生的过度夸大的误导性影响。

与图灵死机理论以及哥德尔的不完备理论类似的还有一些其它的理论，诸如塔斯基理论，皮亚诺理论，以及理发师悖论等，它们都面临着上述的挑战。

四．整体与局部的本质不同及相关理论误导的根源

但另一方面，图灵死机理论，哥德尔不完备性定理，以及其它一些类似的理论也具有另一个重要的哲学意义，那就是提醒我们：人类概括认识整体的能力与处理具体问题的能力之间有着可以被认为是本质的区别。

可惜，它们对于整体与局部的本质不同的一般性的提醒这一贡献却由于对于这些具体理论本身的意义的不恰当的夸大而被实际性的贬低了。其实，人类概括认识整体的能力与处理具体问题的能力之间的区别存在于很多方面，而图灵死机理论和哥德尔不完备性定理以及其它一些类似的相关理论所涉及的人类概括认识整体的能力与处理具体问题的能力之间的区别仅局限于一个非常特殊的状况，那就是当人类的认识对象的整体中包含了这个整体自身时所产生的矛盾，也就是所谓的自我指向性（self-referential）所导致的矛盾性。

而图灵死机理论和哥德尔不完备性定理这一类的自我指向性理论之所以在其后的几十年里在公众心目中产生了严重的误导乃至被夸大为对于人类逻辑缺陷的反映，主要是因为它们各自的论述上所存在的误导性。它们的共同特点是用一般性的表达（如不存在任何符合条件的一般的算法）来描述一个实际上已经明确知道只能证明特殊性（即不能判断包括自己在内的一般性）的结论。这样的做法本身就有很大的误导性。它们让人们以为它们所反映的是非常一般的特性，但实际上所反映的只是由于自我指向性而产生的某一个特殊点的奇异性而已。

对于自我指向性理论所反映的有限的矛盾性的最简明的表述便是那个著名罗素悖论或理发师悖论。对于那个悖论来说，只要规定理发师本人不能包括在问题的讨论之中，便能使该悖论不再是一个悖论。这本身就说明了这是一个语言表达的局限性，而且是不会影响任何人的日常逻辑思维的一种局限性，是对于人们期待语言能够做到它无法做到的事情的梦想与语言本身的能力的局限之间的差别的反映而已。

很奇怪地，当人们已经用理发师悖论或罗素悖论来形象地代表所有的自我指向问题理论，而且也想到了用所谓的元集（metaset），元分析（metaanalysis），元数学（metamathematics）来解决这一问题（这里把meta译为元是网上的一般翻译，我不是很认同这样的翻译，但也找不出更好的。。。这里的meta其实和metaphysics中的meta是类似的）之后，人们却依然过度的夸大包括罗素悖论在内的自我指向问题理论的价值。这实际上反而容易让人们忘记了存在于自我指向问题这个非常局限的现象背后的整体与具体之间的一般性的区别的意义，而使得这些理论原来应有的价值被贬低为“不恰当地夸大某一类局限性很大的理论的哲学价值”的地步。。。。。。

[慕容青草]

虽然这篇文章的显性主题是讨论图灵死机问题，哥德尔不完备性定理以及其它相关类似理论的局限性，但是希望读者能从这篇文章中获得比这显性主题更大的收获，那就是意识到这实际上是一篇社会文化分析的文章。。。如果说这是一篇哲学文章，很多人可能不会意外，因为图灵死机问题和哥德尔不完备定理早已被一知半解的主流哲学界上升为哲学问题了，而图灵和哥德尔本人也早已被誉为是著名的哲学家了。。。但如果说这是一篇关于社会文化分析的哲学文章，很多人听了可能会发懵。。。

其实，这是一个非常明显的社会文化问题：一系列的明明是已知其极端局限性（即涉及单点的自我指向问题）的理论，却被整个学术界，包括科学界，哲学界，数学界，逻辑学界等等奉为整个二十世纪的极为了不起的学术贡献之一类，而这些学术理论不但实际应用价值极其有限，而且它们的共同包装还都言过其实，都是明知问题的本质不过是在单一点上的自我指向产生的很容易通过技术性或语义性的简单处理就排除掉的矛盾性，却用极为一般性的表达（如不存在可以如何如何的一般性的算法）来叙述，而不明确说明这里能够被证明的造成无法得到一般性的结果的原因其实就是因为多包含了已经被认定因而可以轻易被排除的一点。。。虽然业内的人都对这一现实明戏，但却对世界上绝大多数的公众造成误解。。。这种状况如果发生在今天的商业活动中，可能会被告上消费者保护法庭，但是在被视为是人类文明的象牙塔的精英学术界居然可以就这么糊弄了大半个世纪，而其中的小三分之一的时间还是高科技高度发达的网络时代。。。当然，除了那些理论的夸张的表述方式之外，它们之所以会造成公众对它们的价值的夸大的误解也离不开希尔伯特，爱因斯坦这些学术大咖们为之背书。。。。。。所以，这是一个非常特殊的，对于了解人类作为一个文明的整体社会文化心理来说很值得研究的现象。。。。