苏州应用技术学院-观察记录

哥德尔不完备性定理浅释

【数学故事】哥德尔不完备性定理浅释 哥德尔不完备定理的本质与自然数的性质紧密相连，如果计算机使用离散形式的算法(也就
是图林机 )，则计算机的任何复杂、高妙的算法，比如并行运算，都超不过图林机操作的范
畴，也就跑不脱自然数 的性质，因此也就不能解决不可计算问题。
要理解哥德尔定理，先得理解集的概念。
(一) 集合
集合或集的描述：集这个概念，是不可以精确定义的数学基本概念之一，故只能作描述：
凡具有某种特殊性质对象的汇集，其总合被称为集。
例：一组数(可能是无限的)，一群人，一栏鸡蛋。
在作数学上具体研究时，组成集的个体， 被称为元的其他特殊属性，如鸡的特性，人的特
性，数的特性，都不再考虑。于是，一个集合就被抽象成 A，它的元被抽象成x。我们有：x
属于 A
我们也归定：A 不能属于 A
即 A不能是A自己的一元，这个规定不是不合理的，例如，所有的书所组成的集不是书！所
以所有书的集合 不能是这个集合的一元。
A 的某一部份B也可自行构造出一集，被称为A之子集。
我们有：B 含于 A
特殊情况：B可以等于A，B也可以没有元素，被称为空集，我们称这 样两种情况叫A的
平凡子集。
定义：对等设A，B分别为两个集，如果A和B之间能建立1-1的对应关系，则我们称：A 对
等于 B。反之亦然。
对等是集与集之间最基本的关系。若A和B都含有限个元，则两集之 间要对等，当且仅当二
者的元的数目相等。
如果A和B都是无限的，则也能不能建立对等关系，如两个无限数列A和B：
A：1，2，3，。。。
B：2，4，6，。。。
就能建立1-1对应，故
A 对等于 B
可以证明，任何两个无限数列的集合都能对等。
但是，有些无限集之间却不能对等。
例：设实数轴0到1之间的所有有理数所组成的集为R， 又设0到1之间所有的无理数所组
成的集为I，则可证明(略)：
1。R和I之间不对等；
2。R对等于I中的一个非平凡子集，在这样的情况下， 综合1。，我们说 R 小于 I
3。R 对等于 一个自然数序列
数目在无限大时候的推广。我们称上述A有势为可数势，意 味着，A的元数目可以一个一
个地数下去，虽然不一定能数完。于是，自然数序列集具有可数势，任何有 限集合也有可数
势，而且，由上面的3。可知有理数集也有可数势。
再从1。的结论可知，无理数的集有大于可数势的势，我们称这个势为不可数势！
(二) 康脱悖论
设M是一个集，这个集的元是由集合X所组成，其中，X 不属于 X。

康脱悖论：M 不属于 M 同时 M 属于 M
事实上，如果M属于M，则 由定义，M不属于M；反过来，如果M不属于M，则同样由定义，
M属于M。这就出现了悖论，这个悖论 首先由康脱提出来，它类似于塞维尔村理发师悖论，
1902年，罗素又把它在叙述上修改了一下，把它 作为一种悖论，用来说明集合论的形式公
理体系建立的必要。康脱悖论的发现，引起了十九世纪末的数学 界很大的震动，原因在一切
数学的推理和由推理得出的结论最终可以由与、或、非三种基本逻辑运算所构 成的组合操
作，而这些组合操作的集合本身构成了矛盾，于是所有数学成就的整个大厦开始动摇！ 其后，罗素等人提出了形式(逻辑)公理体系，试图甩掉那些悖论，让数学在无悖论的情况下
发展( 事实上，至今数学里还没有这样的悖论的干扰)。办法就是，如怀特海所说，当一个形
式逻辑体系出现康 脱悖论时，就用一个更大的逻辑体系去把它包了，换句话说，就是让原先
那个逻辑体系作为更大的逻辑体 系的子集合。当然这样做的结果，新的母体系又产生了不可
避免的矛盾。怀特海问：就这样一层一层地包 下去，以致于无穷，是否就可避免了矛盾？
(三) 哥德尔不完备性定理浅释
哥德尔不完备 性定理的提出和证明就是为了解决怀特海上述猜想，它指出：使用层层外延法
扩张形式逻辑体系并不能清 除其总和的矛盾！
哥德尔最妙的想法就是把一切逻辑运算视作一种二进制代码(CODE)，就例如， 与可对应为
1，或可对应为10，非可对应为11。但这些二进制数却被他再转换成小数，如0.1，0 .01，
0.11，组合逻辑运算不过是这三种码的组合，也就是更复杂的小数。
递归：逻辑 运算里有一种调用自身的运算，称为递归。递归术语今天是编程算法里最基本
的运算方法之一。递归有两 种结局：1。终止于有限次数的操作；2。无限递归下去，在编程
上被称为死循环。
当逻辑体 系按照怀特海的办法延拓到一个新的，更大的逻辑体系时，旧的逻辑体系中的操作
如果被新的体系调用， 就会出现递归，递归有时是无限次数的(这是允许的，不象计算机运
算不允许)，在此情况下，由二进制 代码所代表的逻辑运算将出现无限循环的小数。
这样，哥德尔就用递归把每一次形式逻辑体系的外延后 的操作，用有限小数和无限循环小数
代表出来，而且他还证明了，这种代表是唯一对应的，也就是说，每 一二进制有限小数或无
限循环小数皆唯一对应于怀特海意义下的无限扩张逻辑体系下的某一逻辑操作。
二进制与十进制：二进制数与十进制数之间能建立起唯一对应关系，因之，实轴上0-1的一
端 (剃除掉两个端点，0、1)的所有小数都可以由二进制小数表出，而且，两种进位制里的有
限小数和无 限循环小数都对应。
有理数和无理数：任何有限小数和无限不循环小数都属于0-1之间的有理数。0 -1数段的实
数除了全部含于其中的有理数以外，还存在着无理数，例如2分之2的平方根。如果我们表
0-1数段的所有有理数集合为Ro，表剩下的所有无理数集合为Io，则可证明：
Ro 对等于 R;
Io 对等于 I
这里的R、I见(一)中例的定义。因此，我们遂有
Ro有可数势，而Io有不可数势。
哥德尔证明了：怀特海意义下的无限延拓形式逻辑体系的 所有逻辑操作所组成的集合与Ro
之间能够建立起1-1的对应关系，也就是说，这两个集合对等，因此 ，它们有相同的势。即
都具有可数势。
但是，如果我们把0-1间任意一个无理数对应成一个 逻辑操作，因为它无限不循环，这个操
作是我们不能确定的，但却能有限截断后知道的，我们就可以理解 成不能用确定的逻辑操作
去解决的，或者换个口吻，说成是矛盾。
于是，哥德尔就得出了结论 ，形式逻辑分析不能用来解决认识中的所有出现的矛盾，更有甚

者，我们由Io的不可数 势的性质看到，这样的矛盾远多于形式逻辑分析所能解决的数量！
哥德尔定理证明的独到之处，在于用 数学反过来证明逻辑分析问题，前面我们已经看到，数
学上已经确定了的推理本来是可被拆成基本逻辑操 作来推理的。罗素曾有个想法，认为所有
数学的推理都可拆开成基本的逻辑运算去实现，好象是数学可以 变成逻辑学似的，今天的哲
学界数学界摈弃了罗素这个想法，认为这是不可能的。
下面文字转 自《意识的困惑》的第三节，该文讨论了人造意识的实现的可能性，所转部分基
本按照英国数学物理学家 彭罗斯的名著《皇帝的新脑》的思路写的。彭罗斯主要使用哥德尔
不完备定理论述意识的不可计算性，论 述严谨，引起了西方哲学界和计算机人工智能界的震
动和争论，目前争论还在继续。下面这段文字的推理 和论述的理解需要有一定的现代数学知
识，有兴趣的朋友有什么问题请提出来，看我能否解答，：）（按 ，该文写于2001年，共
七节，所录参考文献一部分在国内没有出版）
(四) 人工智能能制造出意识吗？--彭罗斯的否定(1)
也许当代自然科学家们忙忙碌碌在高度专业化的研 究和思考之中，几乎完全被自己狭窄领域
上的实证方法所征服，使他们无暇考虑AI后面更深层的哲学涵 义。在哲学家瑟尔提出中文
屋实验以前，很少有从事自然科学研究的科学家，使用自然科学的理论和实践 结果对强AI
提出质疑(参4)，直到1989年，英国数学物理学家罗杰.彭罗斯出版了他的第一本反 驳强AI
的书《皇帝的新脑》(The emperor‘s new mind)，以后又出版了《思想的阴影》(Shadows of
minds)，才第一次有了自然科学家对强AI有力度的挑战。
彭罗斯是当代罕见的在多种 科学领域里做出突出贡献的科学家，1965年，他的以著名论文
《引力坍塌和时空奇点》为代表的一系 列论文，和著名数学物理学家斯蒂芬.霍金的工作一
起创立了现代宇宙论的数学结构理论。除了精通相对 论和量子力学以外，彭罗斯还在理论数
学上做出过骄人的成绩，在几何拓扑方面，他和父亲L.S.彭罗 斯的论文解决了著名的埃契
尔的不可能图形问题(Escher‘s
无限平面非周期拼图(aperiodically tiling)的研究工作给这个领域带来了鼓舞 的动力。很
少有当代自然科学工作者能像彭罗斯那样，在跨学科的领域里取得如此不错的成绩。现在，< br>彭罗斯又以他坚实的数学物理基础，向强AI猛烈开火。
彭罗斯对强AI质疑的论点主要基于两 个方面，第一个方面来自数学和逻辑学，他使用著名
的哥德尔不完备定理(Godel Incomplete Theorem)和图林的停止问题(Turing‘s Halting
Problem)证明了帕拉图理念世界(Platonic World)里存在着大量不可计算的问 题，即不能使
用计算机算法获得由人类直觉天才取得的大多数数学成果，而这，尚不包括人类对艺术等领
域的认知和理解。
第二个方面来自他对当代物理学里几个最深刻，悬而未决难题的思考，这些 问题大约包括了
宇宙起源短瞬间量子引力如何引入问题、宇宙时空结构的基本拓扑结构问题、三个令物理 学
家困惑的难题：贝尔定理联系到的量子时空非局部性问题；薛定锷之猫联系到的多世界问
题； E-V炸弹实验联系到的反真实(counterfactual)问题，这些问题使得当代物理学在微观
物理世界的最重要成果：量子力学和量子场论与经典的牛顿力学、广义相对论之间存在着冲
突。彭罗斯 感到必须对量子力学里的波函数进行约化(reduction)，这样的观察导致了彭罗
斯认为深入的 物理学客观实体的不可计算性，由此，他联系到最新脑神经科学的结果，认为
大脑在意识和思维时具有非 局部性和非计算性，而且他认为，只有把大脑的这种非计算性性
质与量子理论联系起来，才能解决现今的 矛盾，从而得到一门新的量子力学。
彭罗斯还把他的数学成果-- 无限平面非周期拼图命题的证明用来联系到材料科学的新发现
上，即八十年代末期发现的铝-锂- 铜合金的拟结晶过程(参5)上，提出了大脑用可塑性构造
进行思维的猜想。

为了省略篇幅和避免艰涩的数学推演，我将简单介绍一下彭罗斯推理的大意。
首先介绍一下哥德尔不完备性定理(参6)。哥德尔不完备性定理是奥地利逻辑、数学家克尔
特.哥德尔 (Kurt Godel)于1931年针对希尔伯特第十公开问题所获得的答案。哥德尔不完备
性定理 的第一部分说，任何形式化数学公理规则体系都能够被编码成四则运算的操作；哥德
尔不完备性定理的第 二部分是回答希尔伯特(David Hilbert)第十问题，那就是：是否存在
一个形式化数学公 理规则体系，使用这个体系来表示的任何由字符串(string of symbols)
所代表的数 学命题不是能够证明，便是能够证伪？哥德尔的答案是，只要这个体系至少存在
着一个真命题，即不是能 证明，便是能证伪的命题，则这个体系也必将包含另一个既不能
证明，也不能证伪的命题！这就是说，任 何形式化数学公理规则体系都是不完备的，因为
它总是存在着一个不能证明，也不能证伪的命题。 假设我们已经发现了这个矛盾命题，按照不完备定理，我们不能使用我们工作的形式化数学
公理规则 体系去决定它的真伪，但是，我们可以由直觉定义它是真或者假，然后把它作为
一个公理加在原来的体系 里，于是便形成了新的体系，但是，按照不完备定理，这个新体系
又出现了一个不能用新体系的规则决定 真伪的命题，我们又用直觉决定它是真或是假，然
后又把它作为一个公理塞进我们现在工作的体系中，如 此反复，以至无穷(参14)。
从上两段讨论，可以得出三个结论：1。人类的任何数学公理规则体系 都可以编码成四则运
算与逻辑规则操作；2。每一数学体系都是不完善的；3。每一数学体系里必然存在 的矛盾命
题可以通过直觉把它变成一个新公理，从而构成一个新数学体系。
彭罗斯强调了上述 第3条结论的直觉性。然后，彭罗斯转向了图林的停止问题。图林停
止问题说，任何一个图林机都一定有 不可解的问题，就是说，一定存在一个数学问题，不可
能找到一个算法使得这个问题有解。形象地说，即 图林机在计算这个问题时的纸带走纸不可
能停止下来，因为停止下来就意味着这个问题不是0(假)就是 1(真)的结果(参13)。图林证
明了图林停止问题和哥德尔定理是等价的，换句话说，它们俩能够互 相推出。
彭罗斯利用结论1证明任何数学问题可以用编码算法操作，然后又用哥德尔定理与图林停止< br>问题的等价说明了图林机不可解的数学问题等价为哥德尔定理的不能决定真伪的命题。然
而，对于 给定的数学体系，不能决定真伪的命题可以依靠人类的大脑在体系之外去洞察它的
真伪，可是图林机本身 却没有洞察能力决定这个运算该不该停止下来给纸带末端打印一个0
还是1？
进一步，为了说 明确实存在计算机不能解决人脑的数学思维问题，彭罗斯举了哥德巴赫猜想
为例，所谓哥德巴赫猜想，就 是给定任何一个偶数，证明它一定可以写成两个素数之和。这
个问题直到现在还没有被数学家解决，既不 能证明它是真的，也不能证明它是假的。如果把
这个问题拿给计算机做，真想不起计算机怎么证明或证伪 它，很可能计算机只能一个一个偶
数地试下去，如果在人类寿命的时间里，计算机都找不到一个偶数不能 表成两个素数的和，
也就不能说明它已经证明或证伪了这个命题，所以彭罗斯认为哥德巴赫猜想是一个不 可计算
问题，它只能通过人类数学天才脑袋瓜的灵感去解决。另外，彭罗斯还举了费马最后定理和
丢番图问题(即不定代数方程组的整数解存在问题)，说明它们对计算机也是不可解的。上面
这些例子 只是说明它们的解决太困难，所以被认为是不可计算的，从严格意义上说，还不
是证明。彭罗斯举的最好 的例子就是1966年美国数学家罗伯特.伯格尔(Robert Berger)所
证明的一个无限平 面上能够按某些给定的基本图形拼图(tiling)的多米诺问题(Domino
Problem) ，却不可能有预先的计算程序给出来，也就是说，只能一步一步用人的脑筋去拼合，
这实际上就是直接证 明了存在一个不可计算的数学方法(参1)。
然后彭罗斯指出数学真理含于柏拉图理念世界(Plato‘s Ideal World)里。所谓柏拉图理念
世界，是古希腊哲学家柏拉图(BC 380)针对欧几里德几何(Euclidean Geometry)里抽象的点、
线、面及其命题的 真实性提出的一个哲学观念。这个观念认为：欧几里德几何里的抽象数学

目标和证明的结 果属于一个纯粹理念世界里。物理世界的东西，比如用笔在纸上划一个点，
划一条线，都只是相应的抽象 点、线的近似。柏拉图认为，虽然这个理念世界里的东西和规
律在客观世界里不存在，却可以通过人的思 想和人交流，而且这个世界里的真理控制着客观
世界的数学规律(参11)。
柏拉图的这个观 点实际上假设了存在一个独立于人脑的客观理念世界，而彭罗斯坚信数学概
念含于柏拉图理念世界中，这 种看法和当代西方许多数学家的看法并不一致，那些数学家认
为，数学，特别是现代纯粹数学中的许多概 念并不是独立于人脑存在的，而是数学家大脑里
的观念产物。为了说明数学的客观真实性，彭罗斯举了一 个有趣的例子，这个例子很简单，
似乎不需要某个数学家在脑瓜里把它创造出来，这就是数学家曼德布拉 特(B.B.
Mandelbrot)在1986年发现的一个十分奇怪和有趣的图形(参9)，但我 觉得，彭罗斯举的这
个例子并不恰当。
其实，只要举一个简单的数学上的例子就可以说明数学 真理含在柏拉图理念世界中，这就是
学数学的人都知道的高斯的代数基本定理algebra)，它是< br>这样陈述的：
每一个复数域上的多项式都有一个根。
证明的方法有微积分方法(参见 苏：菲赫金哥尔茨的《微积分学教程》)，也可使用抽象代数
的方法(参7)，最简单地，就是使用复变 函数论里关于解析函数的刘维尔定理证明。所有这
三个来自数学不同分枝的证明方法都导致了了一个结论 ，说明数学的真理是绝对的，可以理
解成含在柏拉图理念世界中，类似的例子在数学里还不少，例如使用 解析数论和代数数论这
两个来自不同体系的方法解决同样的数论问题。
我本人倾向于两者的综 合，就是说，虽然数学家可以创造出某些纯粹数学概念，然而这些概
念却受柏拉图理念世界的规律所控制 ，因为假如不存在一个独立于人类大脑的纯粹理念世
界，这个世界将因为没有数学规律而变得毫无研究和 探索的必要，事实上，我们早已在研究
和探索，而且取得了统一的数学真理标准。
但是，彭罗 斯却对物理世界后面的真理和规律是否全部含在柏拉图世界里有疑问(参15)，
这是因为他怀疑人类的 意识是由于其在进化过程中靠了自然选择实现的(参10，见第五
节)，彭罗斯断然排除了计算机和柏拉 图理念世界交流的能力，他认为只有人类才能和柏拉
图世界交流，因此也就排除了计算机解决数学问题所 需要具有的直觉和洞察。
诚然，柏拉图相信日常生活现象都通往一个领域(realm), 这个领域 里有更永久和更安全的
真理，这就隐含了领域里的东西是被人脑加工后的纯粹概念，在他那个时代自然没 有人造
思维机器，他不可能把他的理念世界延拓到机器能否抽取这些抽象概念上面去，彭罗斯实际
上帮他做了这件事，这就使得彭罗斯的推导多含了一条先验假设。
其实，如果假设了柏拉图理念世界 的存在，而且假定计算机和人脑都要服从这个世界的控制，
这样，数学推理及其产物对计算机和人脑的作 用等同，而计算机不具备人所有的数学洞察能
力，它只具备了逻辑算法能力，因此计算机不能构成人类意 识里所特有的数学推理能力。
由此我们看到，彭罗斯一步一步地把严密的数学推理用到证明计算机不能 代替人脑作数学思
维。彭罗斯这一推理虽然只用在数学直觉上，却也可以同样用在人的其他意识经验上面 ，例
如，领会特征(sensory qualia)、痛苦和快乐的感受、意志的感情(feelings of volition)、
意 向性(intentionality)等上，只是因为这些意识特征不象数学直觉一样，有与逻辑较明显
划分的界线和符号推理工具，能够被彭罗斯拿来作为有力的武器罢了。彭罗斯的这部份数学
推理中使用 哥德尔不完备定理想法的最早提出者是英国哲学家卢卡斯(J.R. Lucas) (参8)，
但卢卡斯并未象彭罗斯那样作出一步一步的严密论断。
哥德尔不完备定理的本质与 自然数的性质紧密相连，如果计算机使用离散形式的算法(也就
是图林机)，则计算机的任何复杂、高妙 的算法，比如并行运算，都超不过图林机操作的范

畴，也就跑不脱自然数的性质，因此也 就不能解决不可计算问题。
和提出中文屋实验的瑟尔一样，彭罗斯以这样的身份站出来攻击强AI，犹 如一石击起了千
层浪，惹火了西方一大堆靠AI吃饭的工程师和科学家，许多反驳其实看起来就像诡辩一 样，
好像这些人并没有真正理解彭罗斯的数学推理。
例如，哲学家丹尼尔.丹尼特(Daniel Dennett)指出，既然彭罗斯说，数学真理只能由 优秀
的数学家得到，而不能由计算机的算法得到，那么我们就可以把上面彭罗斯的论述换成：国
际象棋比赛的胜利只能由深思得到，因为深思战胜了无数国际象棋高
手，这里的深思是一个计算机程序， 它由美国卡内基.梅龙大学的计算机科学家编制成功，
于1988年战胜了国际象棋大师本特.拉森(B ent Larsen)(参2)，而不能由计算机的算法得
到。照彭罗斯的推理，则计算机就不能代替 深思的思维，然而深思是一部计算机，这就
造成了明显的悖论。这里，丹尼特的推理里面把数学成果的创 造偷梁换柱地对等于棋类竞赛
的胜利，由此得到了他的悖论，他避开彭罗斯明确指出的非计算性和可计算 性的本质差别，
显然是一个假命题，却被有成绩的AI科学家斯坦.富兰克林(Stan Franklin)视为有力的反
驳(参3)。
美国哲学家希拉里.普特兰(Hilary Putnam)则认为彭罗斯的推理是不完全的，因为它忽视了
了图林机程序的能力，可能某个程序的复 杂性在实践上，甚至连人类的思维都不能理解(参
12)。这个论断简直把问题玄学化了，仿佛此中竟有 神给计算机输入了人类不能理解的程序。
稍微清醒一点的人都会看到，计算机程序是由程序员编出来的， 哪怕它再复杂，都是由一段
一段指令构成的算法所组成，而彭罗斯的推理中并未涉及程序的复杂性。
总的看来，批评彭罗斯推理的人都在玩些小把戏，并未抓住彭罗斯推理的要害。
但是，彭罗斯 除了严密的数学推理以外，在我看来，他的推理中有一个前提并不属于严密的
数学推理，这一个前提就是 ，直觉或者洞察只属于人类所有，它不可能为机械装置，例如计
算机所掌握。这一条多少带有一种形而上 的意思，人类具有直觉的能力确实是我们的实践经
验之一，所以按照这个前提，单纯执行逻辑算法的AI 不能进行人类的意识理解活动，然而，
是否人类能够造出非逻辑运算的计算机来呢？彭罗斯在他的几本书 里都没有涉及到这个问
题。
因此，反驳者都没有看到，彭罗斯的推理实际上证明了执行单纯算 法的AI不可能具有人类
的数学推理能力，而数学推理仅是人类意识的一小部分，结果这样的AI技术不 可能具有人
类的意识，就这个前提来说，彭罗斯是正确的，但他的推理结论却是局限的。