Migarated from here at ‘2012-05-22 17:35:03’.
哥德尔不完备定理的本质与自然数的性质紧密相连，如果计算机使用离散形式的算法(也就是图林机)，则计算机的任何复杂、高妙的算法，比如并行运算，都超不过图林机操作的范畴，也就跑不脱自然数的性质，因此也就不能解决不可计算问题。
要理解哥德尔定理，先得理解集的概念。
(一) 集合
“集合”或集的描述：集这个概念，是不可以精确定义的数学基本概念之一，故只能作描述：凡具有某种特殊性质对象的汇集，其总合被称为集。
例：一组数(可能是无限的)，一群人，一栏鸡蛋。
在作数学上具体研究时，组成集的个体，被称为”元”的其他特殊属性，如鸡的特性，人的特性，数的特性，都不再考虑。于是，一个集合就被抽象成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 “impossible” pictures)。在双曲几何方面，他的关于无限平面非周期拼图(aperiodically tiling)的研究工作给这个领域带来了鼓舞的动力。很少有当代自然科学工作者能像彭罗斯那样，在跨学科的领域里取得如此不错的成绩。现在，彭罗斯又以他坚实的数学物理基础，向强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证明任何数学问题可以用编码算法操作，然后又用哥德尔定理与图林停止问题的等价说明了图林机不可解的数学问题等价为哥德尔定理的不能决定真伪的命题。然而，对于给定的数学体系，不能决定真伪的命题可以依靠人类的大脑在体系之外去洞察它的真伪，可是图林机本身却没有洞察能力决定这个运算该不该停止下来给纸带末端打印一个0还是1？
进一步，为了说明确实存在计算机不能解决人脑的数学思维问题，彭罗斯举了哥德巴赫猜想为例，所谓哥德巴赫猜想，就是给定任何一个偶数，证明它一定可以写成两个素数之和。这个问题直到现在还没有被数学家解决，既不能证明它是真的，也不能证明它是假的。如果把这个问题拿给计算机做，真想不起计算机怎么证明或证伪它，很可能计算机只能一个一个偶数地试下去，如果在人类寿命的时间里，计算机都找不到一个偶数不能表成两个素数的和，也就不能说明它已经证明或证伪了这个命题，所以彭罗斯认为哥德巴赫猜想是一个不可计算问题，它只能通过人类数学天才脑袋瓜的灵感去解决。另外，彭罗斯还举了费马最后定理和丢番图问题(即不定代数方程组的整数解存在问题)，说明它们对计算机也是不可解的。上面这些例子只是说明它们的解决太困难，所以被认为是”不可计算的”，从严格意义上说，还不是证明。彭罗斯举的最好的例子就是1966年美国数学家罗伯特.伯格尔(Robert Berger)所证明的一个无限平面上能够按某些给定的基本图形拼图(tiling)的多米诺问题(Domino Problem)，却不可能有预先的计算程序给出来，也就是说，只能一步一步用人的脑筋去拼合，这实际上就是直接证明了存在一个不可计算的数学方法(参1)。
然后彭罗斯指出数学真理含于柏拉图理念世界(Plato‘s Ideal World)里。所谓柏拉图理念世界，是古希腊哲学家柏拉图(BC 380)针对欧几里德几何(Euclidean Geometry)里抽象的点、线、面及其命题的真实性提出的一个哲学观念。这个观念认为：欧几里德几何里的抽象数学目标和证明的结果属于一个纯粹理念世界里。物理世界的东西，比如用笔在纸上划一个点，划一条线，都只是相应的抽象点、线的近似。柏拉图认为，虽然这个理念世界里的东西和规律在客观世界里不存在，却可以通过人的思想和人交流，而且这个世界里的真理控制着客观世界的数学规律(参11)。
柏拉图的这个观点实际上假设了存在一个独立于人脑的客观理念世界，而彭罗斯坚信数学概念含于柏拉图理念世界中，这种看法和当代西方许多数学家的看法并不一致，那些数学家认为，数学，特别是现代纯粹数学中的许多概念并不是独立于人脑存在的，而是数学家大脑里的观念产物。为了说明数学的客观真实性，彭罗斯举了一个有趣的例子，这个例子很简单，似乎不需要某个数学家在脑瓜里把它”创造”出来，这就是数学家曼德布拉特(B.B. Mandelbrot)在1986年发现的一个十分奇怪和有趣的图形(参9)，但我觉得，彭罗斯举的这个例子并不恰当。
其实，只要举一个简单的数学上的例子就可以说明数学真理含在柏拉图理念世界中，这就是学数学的人都知道的”高斯的代数基本定理”(The fundamental theorem of algebra)，它是这样陈述的：
每一个复数域上的多项式都有一个根。
证明的方法有微积分方法(参见苏：菲赫金哥尔茨的《微积分学教程》)，也可使用抽象代数的方法(参7)，最简单地，就是使用复变函数论里关于解析函数的刘维尔定理证明。所有这三个来自数学不同分枝的证明方法都导致了了一个结论，说明数学的真理是绝对的，可以理解成含在柏拉图理念世界中，类似的例子在数学里还不少，例如使用解析数论和代数数论这两个来自不同体系的方法解决同样的数论问题。
我本人倾向于两者的综合，就是说，虽然数学家可以创造出某些纯粹数学概念，然而这些概念却受柏拉图理念世界的规律所控制，因为假如不存在一个独立于人类大脑的纯粹理念世界，这个世界将因为没有数学规律而变得毫无研究和探索的必要，事实上，我们早已在研究和探索，而且取得了统一的数学真理标准。
但是，彭罗斯却对物理世界后面的真理和规律是否全部含在柏拉图世界里有疑问(参15)，这是因为他怀疑人类的意识是由于其在进化过程中靠了”自然选择”实现的(参10，见第五节)，彭罗斯断然排除了计算机和柏拉图理念世界交流的能力，他认为只有人类才能和柏拉图世界交流，因此也就排除了计算机解决数学问题所需要具有的直觉和洞察。
诚然，柏拉图相信”日常生活现象都通往一个领域(realm), 这个领域里有更永久和更安全的真理”，这就隐含了领域里的东西是被人脑加工后的纯粹概念，在他那个时代自然没有人造思维机器，他不可能把他的理念世界延拓到机器能否抽取这些抽象概念上面去，彭罗斯实际上帮他做了这件事，这就使得彭罗斯的推导多含了一条先验假设。
其实，如果假设了柏拉图理念世界的存在，而且假定计算机和人脑都要服从这个世界的控制，这样，数学推理及其产物对计算机和人脑的作用等同，而计算机不具备人所有的数学洞察能力，它只具备了逻辑算法能力，因此计算机不能构成人类意识里所特有的数学推理能力。
由此我们看到，彭罗斯一步一步地把严密的数学推理用到证明计算机不能代替人脑作数学思维。彭罗斯这一推理虽然只用在数学直觉上，却也可以同样用在人的其他意识经验上面，例如，领会特征(sensory qualia)、痛苦和快乐的感受、意志的感情(feelings of volition)、意向性(intentionality)等上，只是因为这些意识特征不象数学直觉一样，有与逻辑较明显划分的界线和符号推理工具，能够被彭罗斯拿来作为有力的武器罢了。彭罗斯的这部份数学推理中使用哥德尔不完备定理想法的最早提出者是英国哲学家卢卡斯(J.R.Lucas) (参8)，但卢卡斯并未象彭罗斯那样作出一步一步的严密论断。
哥德尔不完备定理的本质与自然数的性质紧密相连，如果计算机使用离散形式的算法(也就是图林机)，则计算机的任何复杂、高妙的算法，比如并行运算，都超不过图林机操作的范畴，也就跑不脱自然数的性质，因此也就不能解决不可计算问题。
和提出中文屋实验的瑟尔一样，彭罗斯以这样的身份站出来攻击强AI，犹如一石击起了千层浪，惹火了西方一大堆靠AI吃饭的工程师和科学家，许多反驳其实看起来就像诡辩一样，好像这些人并没有真正理解彭罗斯的数学推理。
例如，哲学家丹尼尔.丹尼特(Daniel Dennett)指出，既然彭罗斯说，数学真理只能由优秀的数学家得到，而不能由计算机的算法得到，那么我们就可以把上面彭罗斯的论述换成：国际象棋比赛的胜利只能由”深思”(Deep Thought)得到，因为”深思”战胜了无数国际象棋高手，这里的”深思”是一个计算机程序，它由美国卡内基.梅龙大学的计算机科学家编制成功，于1988年战胜了国际象棋大师本特.拉森(Bent Larsen)(参2)，而不能由计算机的算法得到。照彭罗斯的推理，则计算机就不能代替”深思”的思维，然而”深思”是一部计算机，这就造成了明显的悖论。这里，丹尼特的推理里面把数学成果的创造偷梁换柱地对等于棋类竞赛的胜利，由此得到了他的悖论，他避开彭罗斯明确指出的非计算性和可计算性的本质差别，显然是一个假命题，却被有成绩的AI科学家斯坦.富兰克林(Stan Franklin)视为有力的反驳(参3)。
美国哲学家希拉里.普特兰(Hilary Putnam)则认为彭罗斯的推理是不完全的，因为它忽视了了图林机程序的能力，可能某个程序的复杂性在实践上，甚至连人类的思维都不能理解(参12)。这个论断简直把问题玄学化了，仿佛此中竟有神给计算机输入了人类不能理解的程序。稍微清醒一点的人都会看到，计算机程序是由程序员编出来的，哪怕它再复杂，都是由一段一段指令构成的算法所组成，而彭罗斯的推理中并未涉及程序的复杂性。
总的看来，批评彭罗斯推理的人都在玩些小把戏，并未抓住彭罗斯推理的要害。
但是，彭罗斯除了严密的数学推理以外，在我看来，他的推理中有一个前提并不属于严密的数学推理，这一个前提就是，直觉或者洞察只属于人类所有，它不可能为机械装置，例如计算机所掌握。这一条多少带有一种形而上的意思，人类具有直觉的能力确实是我们的实践经验之一，所以按照这个前提，单纯执行逻辑算法的AI不能进行人类的意识理解活动，然而，是否人类能够造出非逻辑运算的计算机来呢？彭罗斯在他的几本书里都没有涉及到这个问题。
因此，反驳者都没有看到，彭罗斯的推理实际上证明了执行单纯算法的AI不可能具有人类的数学推理能力，而数学推理仅是人类意识的一小部分，结果这样的AI技术不可能具有人类的意识，就这个前提来说，彭罗斯是正确的，但他的推理结论却是局限的。
参考文献：
Berger, R. (1966), The undecidability of domino problem, Memoirs. Amer. Math. Soc., No. 66, p.70.
Dennett, D. (1989), Murmurs in the Cathedral, Times Literary Supplement, September 29-Oct. 5, 1055-56.
Franklin, S. (1995), Artificial minds, A bradford book, MIT Press, Cambridge Mass, Lond. Eng., pp.111-2.
Gardner, M. (1958), Logic machines and diagrams, University of Chicago Press.
Gayle, F. W. (1987), Free-surface solidification habit and point group symmetry of a faceted icosahederal Al-Li-Cu phase. J. Mater. Sci. 2, 1-4.
Godel, K. (1931), Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systems I. Monaschefte fur Mathematik und Physik, 38, 173-98.
Hungerford, T. W. (1974), Algebra, Springer-Verlag, New York, Heidelberg, Berlin, pp.265-7.
Lucas, J. R. (1962), Minds, machines and Godel, Philosophy 36, 120-4; reprinted in Alan Ross Anderson (1966). Mind and machines, Englewood Cliffs.
Mandelbrot, B. B. (1986), Fractals and rebirth of iteration they, In the beauty of fractals: images of complex dynamically systems, H.-O. Peigen and P. H. Richer, Springer-Verlag, Berlin, pp.151-60.
Penrose, R. (1989), The empiror‘s new mind, Oxford Press, pp.429-30.
Plato, M. (380 BC), The Dialogues of Plato, In Oxford: Clarendon, 1892, trans. B. Jowett, Vol. 39-47.
Putnam, H. (1994), Review of “Shadows of the mind”, The New York Times Book Review, Nov. 20 1994, p.1.
Turing, A. M. (1937), On computable numbers with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc.(ser.2), 42, 230-65, a correction 43, 544-6.
Turing, A. M. (1939), Systems of logic based on ordinals, P. Lond. Math. Soc., 45, 161-228.
Wigner, E. P. (1960), The unreasonable effectiveness of mathematics, Commun. Pure Appl. Math., 13. 1-14.
- 作者： 尘净难 2005年04月21日