算法、图灵机、哥德尔定理与知识的不确定性

来源：人机与认知实验室

作者：王荣江

摘要：知识论一直在寻求对知识的确定性作一般算法式的逻辑证明的辩护。然而，即使在处理抽象的数量概念的数学基础研究中，也不能达到最终逻辑证明的确定性。图灵对停机问题的算法步骤的否定回答、哥德尔定理对真理的“不可证明性”的确立，使我们不得不面对知识中逻辑证明背后不确定性的东西。

知识论中，一般地把知识定义为“被证明为合理的真信念”[1](justified true belief)，知识被描述为同时满足三个条件的陈述：S知道P当且仅当：①P为真；②S相信P；③S有充分的理由相信P。这里知识的定义指的是命题知识(knowledge that P)，它不是定义像“我知道柏拉图”句式中通过熟知而得到的知识，也不是定义“如何的知识”(knowledge-how)，而是强调它必须有充分的理由让人相信。即信念不仅仅由它是真的这一事实证明为合理的，它还必须有充分的理由，才能称之为“知识”；它要求的不仅仅是被结果证明为正确的，还必须是事前的正当理由。

知识论从古希腊将“知识”与“意见”严格区分开始，一直在寻求那确定无疑的绝对真理的证明主义道路上发展。知识论家的工作就是要思考真正的知识应该符合的标准，通过什么样的方法能达到真正知识的标准，如何能将知识与真正的信念相区别，驱除或然性而达到确定性。这样的研究在现当代，以研究科学理论知识的科学哲学的形式表现出来。科学哲学家感兴趣的是，对特定发现方法所获得的科学知识在多大程度上是确定的，即科学哲学家想知道科学知识是否有那么一部分是确定无疑的，不会在任何可设想的条件下被修正，以及它是如何达到这样的确定性的。今天，这样的知识论努力似乎已不可能，科学知识不但没有我们人类想要达到的确定性，仿佛又走向了它的反面——不确定性。科学哲学走过了从基础论到整体论再到相对主义的发展过程，直至后现代主义，实践着认识论的不可能主义——“一种无处不在的、极端的、无法克服的不确定性，一种认识论上的虚无主义。”[2]我们如何来理解这一点？

当然，知识论者并不关心我们是否认识某个特定的可靠的真理性知识，而是关心我们是否有理由能要求认识整个某一类的真理性知识。在知识论中，我们似乎不能直接回答上述问题，有关算法、图灵机和哥德尔定理却能为我们提供一种有效的理解途径。

1

算法是一个古老的数学概念。它由9世纪波斯的一位数学家提出。当然，在古希腊就有算法的实例，比如，现在被称为欧几里德算法的，找两个数的最大公约数的步骤就是一例。算法事实上是解题的系统步骤。一般算法概念的准确表达只是从本世纪起才有记载，特别是30年代给出了这一概念的不同描述。阿伦·图灵在1936年提出的“图灵机”概念，是一般算法的典型代表。其目的是为了解决“希尔伯特第十问题”——数学问题的一般算法步骤问题，也就是在原则上是否存在一般数学问题的解题步骤的判决问题。希尔伯特的规划是要把数学置于无懈可击的牢固的基础上，其中的公理和步骤法则一旦确立就不再改变。他想一劳永逸地解决数学的可靠性问题。1931年，库尔特·哥德尔提出的定理证明了希尔伯特规划的不可能。图灵关心的判决问题超出任何按公理系统的特殊的数学形式，他的问题是：是否存在能在原则上一个接一个地解决所有数学问题的某种一般的机械步骤。图灵发现，他可以把这个问题重述成他的形式，即决定把第n台图灵机作用于数m时事实上是否停机的问题。因而被称为停机问题。于是，图灵机的问题是这样的问题：存在某种完全自动地回答一般问题，即停机问题的算法步骤吗？图灵的回答是：这根本不存在。图灵是通过证明不存在决定图灵机停机问题的算法来证明不存在判定所有数学问题是否可解的问题。

当然，这不是说，在任何个别的情形下，我们不可能决定某些特殊数学问题的真理或非真理，或者决定某一台给定的图灵机是否会停止。我们可以利用一些技巧或者仅仅是常识，就能在一定情况下决定这种问题。但是，不存在一个对所有的数学问题，也不存在对所有图灵机以及所有它们可能作用的数都有效的一个算法。也就是说，这不是一个单独问题的不可解性，而是关于问题的族的算法的不可解性。在任何单独的情形下，答案或者为“是”或者为“非”它肯定存在一个决定那个特定情形的算法。当然，困难在于我们可能不知道用这些算法中的哪一个。这就是决定一个单独陈述而不是决定一族陈述的数学真理的问题。正如罗杰·彭罗斯所说：“重要的是要意识到，算法本身不能决定数学真理。一个算法的成立总是必须由外界的手段来建立起来。”[3]希尔伯特的希望，是对于任何一串代表一个数学命题的符号，譬如P，人们应能证明或者P或者非P，依P是真的还是伪的而定。如果这一希望能被实现，这甚至使我们不必为这些命题的意义忧虑。P仅仅为一语法正确的符号串。如果P为一定理（也就是可在系统内证明P），则符号串P的真值就可被赋予真；另一方面，如果能证明非P为定理的话，则可被赋予伪。为了使这些有意义，我们除了完备性外还需要一致性。也就是说，不应有P和非P都为定理的符号串P，否则P会同时是真的和伪的。

哥德尔定理指出，不管任何精确（形式化）数学公理和不同法则系统，如果它足够宽广于包容简单算术命题的描述并且其中没有矛盾，则必然包含某些用在该系统内所允许的手段既不能证实也不能证伪的陈述。也就是说，公理系统本身的协调性的陈述被编码成适当的算术问题后，必然成为一道“不能决定的”命题。

哥德尔定理所要说明的问题，在罗素发现的集合悖论中已经存在。在开始的时候，罗素并没有认识到集合悖论的根本性，他还是和他的合作者怀特海着手发展一种高度形式化的公理和步骤法则的数学系统，试图要把所有正确的数学推理翻译到他们的规划中去。当然，他们非常仔细地选择法则以防止导致罗素悖论那样的推理类型，但是他们的计划也必然在哥德尔定理面前破产。

哥德尔定理说，甚至在良定义（没有悖论）的数学公理系统中，存在着根据这些公理所无法证明的一些问题。即在这个系统中存在着既不能证明也不能否证的明确命题。即使我们求助于可能解决这一问题的更大的公理系统，在这个新的系统中也同样存在不可判定的命题。用波兰尼的话说，“这就表明我们从来没有完全知道我们的公理意味着什么，因为如果我们知道的话，我们就可以避免在一个公理中断言另一个公理所否定的东西的可能性。对于任何特定的演绎体系来说，这种不确定性是可以通过把它转换成一个较广泛的公理体系而消除的，这样，我们就可以证明原来的体系的一致性。但是，任何这样的证明也还是不确定的，也就是说，较广泛的体系的一致性将总是不可判定的。”[4]这样，用什么方法能确定数学真理或逻辑真理就变得有些茫然了。最为根本的一点是，那种原有的从古希腊哲学开始就已形成的，并在近代科学中得到充分应用的科学知识观——设计一组公理并通过逻辑论证的方式从中推出自然界的一切现象——确定性信念必须抛弃。

2

事实上，哥德尔确立的“不可证明性”的真理和罗素悖论的论证之间的相似性，与图灵解决停机问题的图灵机不存在的论证有相似性。这些相似性不是偶然的，它们之间存在有内在的历史连接的脉络：图灵是在研习哥德尔工作之后才找到它的论证的；哥德尔本人非常熟悉罗素的悖论，并能把这一类将逻辑延伸得这么远的悖论的推理转化成有效的数学论证。

为什么我们应该接受哥德尔和图灵的论证，而必须排斥导致罗素悖论的推理呢？事实上，前者更直接明了得多，并且作为数学论证更为有力而出人意料，罗素悖论则依靠牵涉到“巨大”集合的更为模糊的推理。但是必须承认，其差别并不真像人们以为的那么清楚。弄清这些差别的企图是整个形式主义观念的强大动机。哥德尔的论断表明，严格的形式主义者的观点是不能成立的，但他没有向我们指出另外完整的可信赖的观点。这问题仍未得到解决。当代数学中为了避免导致罗素悖论的“巨大的”集合的推理的类型所实际采用的步骤是不能完全令人满意的。而且，它仍然试图以明晰的形式主义的术语来表达，换句话说，按照我们并不完全相信不会出现矛盾的术语来描述。

彭罗斯认为，无论情况如何，哥德尔论证的清楚推论是，“数学真理的概念不能包容于任何形式主义的框架之中。数学真理是某种超越纯粹形式主义的东西。甚至即使没有哥德尔定理，这一点也是清楚的。”[5]在我们试图去建立任何一个形式系统时，我们在决定采取什么公理和法则的指导，总是在给定系统的符号的“意义”下对何为“自明正确”的直觉理解。并且，根据关于“自明”和“意义”的直观理解，我们如何决定采用哪个形式系统是有意义的，哪个是没意义的，以自身具有一贯性的概念来决定也是不够的。“人们可以有许多自身具有一贯性但在含义上没有‘意义’的系统，它们的公理和步骤法则具有错误的意义，或者根本没有意义。甚至在没有哥德尔定理时，‘自明’和‘意义’的概念仍然是需要的。”[6]

对科学知识而言，其真理性不能完全容纳在纯粹逻辑证明的形式主义之中，它是超越逻辑证明和规范性的运作的。只有在科学世界观信念的意义确定了的情况下，才有对科学假说的自明性的理解及其逻辑的真理证明。

如果没有哥德尔定理，人们可能想象：“自明”和“意义”的直觉概念只要在开始建立形式系统时用一次就好了，而此后就与决定真理的清楚的数学论证不相干。这样，按照形式主义者的观点，这些直觉概念在发现适当形式的论证时，作为数学的初步思维或导引而起作用，而在实际展示数学真理时不起作用。彭罗斯指出，哥德尔定理表明，上述观点在数学基本哲学中不能真正站住脚。他说：“数学真理的观念远远超越形式主义的整个概念。关于数学真理存在某些绝对的‘上帝赋予’的东西。”“任何特定的形式系统都具有临时和‘人为’的品格，在数学的讨论中，这类系统的确起着非常有价值的作用。但是它只能为真理提供部分（或近似）的导引。真正的数学真理超越于人为的构造之外。”[7]这一关于数学真理的观点，完全适应于科学知识真理。

按照哥德尔定理，无论我们构造出多么复杂的理论，它都有一个表述的形式系统，但在这个系统内都有一个不可证的公式，这个公式不能作为定理在该系统内被推导出来。但是这种形式化（人类不可避免的认识形式）的不能证明性，是否就意味着认识本身的不可能和不正确呢？

彭罗斯持一种“人心超过计算机”的观念。认为从哥德尔定理可以得出，人类判定数学真理的过程是超越任何算法的。因为，意识是我们赖以理解数学真理的关键，这种意识是我们能够借直觉的洞察力“看出”某些在数学形式系统中不能证明的数学命题的真理性，而意识是不能被形式化的，它必定是非算法的。计算机只能处理有算法的东西，因而计算机不过是强人工智能专家所钟爱的“皇帝新脑”而已。

在哥德尔本人看来，他的不完全定理并未给出人类理性的极限，只揭示了数学中形式主义的内在局限性[8]。这是任何形式主义的内在局限性，知识论中的主流学派的证明主义也不能例外，它并不能完成其自身提出的为知识真理作辩护的任务，甚至这样的努力还会掩盖和扼杀科学知识中的智慧和创造性的特征。

人类能否超越自身——或者，计算机程序能否跳出自身，这可能是一切认识的根本性的问题。哥德尔定理是说，数论形式系统能谈论自身，但不能超越自身。一个计算机可以修改自身的程序，但不能违背自身的指令——充其量只能通过服从自身的指令来改变自身的某些部分。在科学认识与其认识成果——知识——之间也存在这样的关系，科学认识是一个极为复杂的过程，它的结果不能因其结果的形式表达系统的不完全性而得以否定。

3

科学知识的基础无疑是数学，从近代科学对自然的数学化努力以来，可以说正是数学为我们有效地描述现实世界提供了可能，也正是数学的确定性确保了科学理论的确定性。爱因斯坦说过，令他幼年时代难忘的两件事情中的一件事是他看了一本欧几里德几何学的启蒙教科书。书中都是些确定的论断，并且都达到了非常精确的证明而让人无法怀疑。正是这种明澈和确定性给他留下了不可泯灭的印象。罗素也有同样的经历并在晚年说过：“渴望确定性就像大多数人需要宗教信仰一样的重要。”事实上，两千多年来，欧几里德几何学代表了认识追求确定性的不可抗拒的尊严。毕达哥拉斯说“数是万物的本原”，数是完美和谐的，因而由数所组成的世界也是完美和谐的；柏拉图相信上帝就是用几何学来创造世界，因而研究世界就不能不懂几何学；伽利略干脆就说，宇宙这本书就是用数学语言写成的，认为如果没有数学语言，人们只能在黑暗的迷宫中徒劳地徘徊；牛顿就是这种数学主义的坚决执行者。自牛顿以来，这种观点几乎变成一种教条，为知识确定性辩护的哲学知识论，总是把不确定性排除在知识之外。

但是数学理论自身是确定的吗？由数学定律建立起来的科学理论是对世界的客观描述吗？或者它还是像康德所说的，思维可能把欧几里德式的东西强加给外部世界，甚至于人类的“思维法则”就是按照欧几里德的模式构作的。非欧几何和相对论的出现使这一问题显得突出，数学中的基础主义各派的争论使问题更加尖锐化。

哥德尔不完全定理说明，不确定性是人类认识的形式逻辑思维本身固有的，即使在纯粹数学里我们也无法彻底达到确定性。进一步，如果把这些数学的概念和理论与人们的实际经验和科学观察接触，就会产生更大的不确定性。原因在于在纯粹的逻辑观念与现实之间并不是一一对应关系。哥德尔在与王浩的谈话中说，“由于涉及‘概念’、‘命题’和‘证明’等一般概念在它们最一般的意义上的不可解内涵悖论的存在，不存在使用这些概念的自指性的论证在逻辑发展的现阶段能被看成是具有确定性的”。“关于‘证明’这个一般概念的境况是与‘概念’这个一般概念的境况相类似的，这是由于我们不能消除围绕着这些概念的那些矛盾。否则，一旦我们理解了证明这个一般概念，我们也就凭借心智有一个关于它自身一致性的证明。假定容易些，我们也就能够真正从证明的这个一般概念导出矛盾，包括证明的自我应用。我们对证明概念的理解是不完全的，……某些事情与我们的逻辑观念是不符合的，这一点是极端明显的。”[9]因而，在任何认识中绝对的确定性是没有的。

爱因斯坦说：“就涉及现实的一些数学命题而言，它们是不确定的……；就它们是确定的来说，它们却又不涉及到现实。”[10]黑洞理论学家S.霍金认为，上帝不仅掷色子，而且有时还把它们扔到看不见它们的地方去。数学中，非欧几何导致了对公理性的研究，其结果使人震惊。在许多数学分支里发现公理具有一种任意性，而且由它导出的证明往往是有缺陷的。更糟糕的是，数学家们试图按顺序整理自己的理论并没有产生如此做法的、普遍赞成的程序。今天，我们有许多数学“学派”，例如构造主义学派、逻辑主义学派、形式主义学派和直觉主义学派，它们在基本原则上往往存在激烈的争执。

王浩认为，哥德尔定理使那些进行数学形式化努力的人，“从此深深感到了形式处理与直觉处理相互制约的中心意义，尽管这个部门是研究形式侧面的。”[11]哥德尔定理还以不同方式施加影响于数学哲学的三大学派：形式主义、逻辑主义和直觉主义。王浩指出，它“毁掉了形式主义者找出完全形式系统及有穷主义一致性证明的期望，也毁掉了逻辑主义者找出一套清澈而广博的‘大逻辑’形式系统的期望。这些定理对直觉主义者来说不那么令人吃惊，但它们和它们的证明是构造性的。所以是直觉主义者能接受的；此外，这项工作向他们证明适当运用形式方法会产生用他们的眼光看不全也看不准的大型准确结论。”[12]

王浩说：“哥德尔直言不讳地说过，我们没有任何绝对确定的知识。言外之意，哪怕极其简单的事情，我们也无绝对把握说自己完全捕获了堪称终审法庭的客观实在。他提出他所谓‘基于成功的论证’作为有利于实在主义的证据。”[13]

这样，试图建立一个绝对可靠的数学根基的企图必然是不能成功的，数学的基础从根本上看来是有问题的。克莱因把这一点总结在《数学——确定性的丧失》一书中，他认为，哥德尔关于相容性的结论表明：“我们使用任何数学方法都不可能借助于安全的逻辑原理证实相容性，已提出的各种方法概莫能外。这可能是本世纪某些人声称的数学的一大特征，即其结果的绝对确定性和有效性已丧失。”[14]

数学家S.李柯克幽默地说，科学、哲学和神学现今都凑到一块了，在某种意义上表明，它们就像一起参加葬礼的三个人那样凑到了一块，这个葬礼就是确定性的死亡。

当然，追求绝对确定性知识的不可能，也并不意味着我们在知识的可靠性上，一定要采取一种彻底怀疑主义的态度。确定和怀疑只构成我们对我们所获得知识的两种极端态度（一种是始终坚持我们能获得具有确定性的知识并努力追求不动摇，一种是因对追求具有确定性的知识的怀疑而走向相对主义和不可知论。）。虽然怀疑主义给我们提供了更深更广的思想空间（确定论者只是在预先假定有确定性知识的前提下，在寻求确定性知识的根基中兜圈子），但它的假设性要求（除非我们对任何事物的认识有绝对的把握，除非我们绝无犯错误的可能性，否则我们就不应该要求对任何事物有知识。）也是不现实的。因为，虽然我们对任何事物的认识没有绝对的把握，我们随时都会犯错误，但是我们的认识毕竟在这样的易谬论中真的前进了。知识论的历史，是哲学家不懈追求知识的绝对确定性而逐步显现知识的不确定性的历史。知识论的历史说明，没有那种不容置疑的绝对确定性知识，知识也不是非要有这种不容置疑的绝对确定性不可。如果我们把认识看作我们对客体世界的反映，那么，客体世界经过主体上升为理论知识的过程，是主体在理想性目标指导下，人为建构合理性的过程，其间存在着非理性的、不合理和不合法的因素。在过去，认识总是在思维中舍弃对象世界和自身的不确定性的因素，通过思维中的确定性来建构对象世界的确定性从而达到对对象世界的确定性认识。现在，原有简单的是与非的线性思维方式，已不能满足我们深化认识的需要，我们不得不面对对象世界和主观思维中的、不可人为排除的不确定性，它构成我们知识论甚至是我们新的认识方式和思维方式的核心。绝对确定性知识的不可能与知识不确定性的凸现，不是知识论的“死亡”，而是知识论的“新生”。在这样的知识论中，我们真正触及到对象世界和我们思想思维的深处。

参考文献：

[1] Robert Audi.Epistemology:A contemporary introduction to the theory of knowledge[M].Routledge,London,1998.214.J.丹西当代认识论导论[M].中国人民大学出版社，1990.25.

[2] 波特·罗斯诺.后现代主义与社会科学[M].上海译文出版社，1998.161.

[3][5][6][7] 罗杰·彭罗斯.皇帝新脑——有关电脑、人脑及物理定律[M].湖南科学技术出版社，1995.72,128,129,129.

[4] 波兰尼.个人知识[M].贵州人民出版社，2000.396.

[8][9] 转引自刘晓力.哥德尔对心—脑—计算机问题的解[J].自然辩证法研究，1999(1).

[10] 转引自J利特尔.数学的不确定性[J].New Scientist,4,Dec.,1980.

[11][12]][13] 王浩.哥德尔[M].上海译文出版社，1997.390,391,402.

[14] M克莱因.数学：确定性的丧失[M].湖南科学技术出版社，1997.269.

未来智能实验室的主要工作包括：建立AI智能系统智商评测体系，开展世界人工智能智商评测；开展互联网（城市）大脑研究计划，构建互联网（城市）大脑技术和企业图谱，为提升企业，行业与城市的智能水平服务。每日推荐范围未来科技发展趋势的学习型文章。目前线上平台已收藏上千篇精华前沿科技文章和报告。