以前曾打算详细介绍一下哥德尔定理，但一是时间不多，再加上这个定理不太好理解，需要的准备知识比较多，结果一直拖着没动。不过最近还是多次看到坛中有人引用这个定理，但是对其意义模糊，做出了很多错误推论。感到还是有必要介绍一下，特别是对常见的错误理解。
哥德尔定理是数理逻辑中的一个定理，1931年奥地利逻辑、数学家克尔特.哥德尔(Kurt Godel)发现并证明的，这个定理彻底粉碎了希尔伯特的形式主义理想。为理解这个定理及其意义，需要相当的数理逻辑和集合论知识。要把这些预备知识都在这里整理出来，工作太繁重了，这也就是我一直没敢动手写这篇东西的原因之一。这里仍然也不打算详细介绍这些东西，只是在必要的时候给些简单的说明，要想更深刻地理解，有兴趣的朋友可以自学相关课程。
哥德尔定理其实是两个定理，其中哥德尔第一不完备性定理是最重要、也是误解最多的，从这一定理的版本众多就可以看出。如：
“如果一个形式理论T足以容纳数论并且无矛盾，则T必定是不完备的。”
“任何一个相容的数学形式化理论中，只要它强到足以在其中定义自然数的概念，就可以在其中构造在体系中既不能证明也不能否证的命题。”
“任何一个足够强的一致公设系统,必定是不完备的”
第二不完备性定理是第一定理的一个推论：“任何相容的形式体系不能用于证明它本身的相容性”
如果没有相关的知识基础，要理解这个定理真的是比较难。至于证明就更不容易看懂了。我偷点懒，跳过这些直接介绍其意义吧。
哥德尔定理是一阶逻辑的定理，在形式逻辑中，数学命题及其证明都是用一种符号语言描述的，在这里我们可以机械地检查每个证明的合法性，于是便可以从一组公理开始无可辩驳地证明一条定理。上世纪初，以希尔伯特为代表的形式主义派，希望能通过形式逻辑的方法，构造一个有关数论（自然数）的有限的公理集合，推出所有数论原理（完备性），且无矛盾（相容性），并以此出发构造整个形式主义的数学体系。而哥德尔第一不完备定理，粉碎了这一设想。这两个定理实际上表明，这样的公理系统要么不完备，要么有矛盾。数论的相容性为根茨（G.Gentaen，1909-1945）在1936年使用蕴涵着非演绎逻辑的超限归纳法所证明。
因而，该定理揭示在多数情况下，例如在数论或者实分析中，永远不能找出公理的完整集合。你可以在公理体系不断加入新的公理，甚至构成无穷的公理集合，但是这样的公理列表不再是递归的，不存在机械的判断方法判断加入的公理是否是该公理系统的一条公理。这对于计算机科学意义重大，在计算机语言中，一阶逻辑的定理是递归可枚举的，然而哥德尔第一不完备定理表明，无法编制这样的程序，通过递归的定理证明，可在有限时间内判断命题真假。彭罗斯的《皇帝新脑》中用停机问题描述了这一点，他甚至认为由此可知电脑永远不能超越人脑，甚至不可能达到人脑的水平。当然这点还不是定论，存在很大争议。
想说的简明一些，看来还是不行。还是结合对常见误解的分析，尽量来澄清模糊认识吧。
常见误解一：“所有的公理系统都是不完备的”。这是最常见的，甚至有人用这点来否定逻辑学，这是错误的。拿欧氏几何来说，就可以被公理化为一个完整的系统。
常见误解二：“所有包含到自然数的公理系统都是不完备的”。这个错误从上面的有些哥德尔定理的描述中都能看得出来。该定理仅假设公理系统能“定义”自然数。很多包含自然数的系统，例如“实数”和“复数”都有完备的公理化系统。
常见误解三：“因为不完备，我们永远无法证明一个公理系统无矛盾”。不，我们可以用其他方法证明，如上面提过的超限归纳法。其实该定理只表明我们不能从系统的内部证明相容性，不排除我们可以通过其他系统给出证明。例如，数论中的皮亚诺公理不能单独在数论范围内证明，但可在集合论中证明。
看起来长篇大论一大堆，可我的感觉却是太单薄了，这只能算是简而又简的简介，呵呵。抛砖引玉吧，希望对大家有所帮助。
二
哥德尔定理主要还是在数学领域中应用的，至于在实际中的运用，很多都是基于错误的理解在盲目套用，论坛中的某些传教贴子中就多次出现。要想避免错误，还是应该真正的弄懂这个定理的意思，但矛盾的是，这的确需要相当的数学知识为基础，才可能，对于很多人来说，实在太难了。所以在文中我指出一些错误理解，进行了简单的分析，大家如果加以注意，就可以避免很多错误。下面我介绍一些实际运用的例子，只是我个人认为比较正确的应用，也许对帮助大家理解这个定理有帮助，
既然是数学定理，最直接的应用领域还是在数学里，尤其是数论。很多数论中的命题的证明，都需要用到哥德尔定理。这我就不多介绍了。这个定理表明，有些关于自然数的命题，本身可能是真命题，但是不能仅从自然数公理系统内证明或证否，需要其他的手段或者方法，如集合论等，才可以证明。曾经有人猜测，“哥德巴赫猜想”可能就是这样的一个命题。因此即便对于极为抽象和形式化的数学，数学家的直觉――也就是大量实践经验的积累――比纯形式的数学逻辑推理更基本，更可靠。但并不能就此说逻辑就毫无用处了，后者可以用来验证前者是否正确，也可以推导出一些新正确的命题，只是不能代表全部。而如前文所说，即便不能在形式系统内证明，还可以通过其他方法，或从其他系统中证明。另外，再次强调，“该定理仅假设公理系统能‘定义’自然数”，是一阶的逻辑定理，不要任意扩大。这里经常发生错误理解，还是建议有兴趣的朋友多了解掌握有关的基础知识。
该定理的另一个主要应用领域，是数学的一个应用分枝――计算机和人工智能。现在把我文中提过的停机问题简单介绍一下。计算机到现在有了极大的发展，但是基本原理还是冯?诺依曼提出来的，只是速度和效率大大提高了。从根本上说，计算机的程序，就是一种基于2进制数字运算的命题演算系统。其中给出的公理是有限的，规则是可计算，而判定出命题的真伪时，输出结果，停机并转向下一个命题的处理。这就符合了哥德尔第一不完备定理的条件。可如该定理所说，这样的系统必然是不完备的，也就是说至少有一个命题不能通过这样的“程序”被判明真伪，系统在处理这样的命题时，就无法“停机”，用俗话说就是被“卡”住了，永远不能绕过。无论你怎样扩充公理集，只要是有限的，这个现象就始终存在。而无限的公理集对于计算机来说，就意味着无限大的存储空间，这显然是不可能的。因此，有些数学家，如我提过的彭罗斯就认为，这表明了计算机是有致命缺陷的，而人类的“直觉”不受该定理的限制，所以计算机永远不可能具有人脑的能力，人工智能期望中的真正具有智慧的“电脑”，只不过是如“皇帝的新衣”那样的“皇帝的新脑”。关于这个问题的详细情况，可阅读彭罗斯的《皇帝新脑》。
为什么人脑与电脑有这样的根本差别呢，彭罗斯认为可能是量子力学不确定性和复杂非线形系统的混沌作用共同造成的。但也有的数学家并不这样认为，他们指出，人脑就基本意义和工作原理来说，与人工智能原理的“图灵机”无根本差别，电脑也存在上述两种作用，这就说明人脑也要受到哥德尔定理的限制。两者间的差别，可用包含非确定性的计算系统说明，就是所谓的“模糊”处理。人脑正是这样的包含了非确定性的自然形成的神经网络系统，它之所以看上去具有电脑不具备的“直觉”，正是这种系统的“模糊”处理能力和效率极高的表现。而传统的图灵机则是确定性的串行处理系统，虽然也可以模拟这样的“模糊”处理，但是效率太低下了。而正在研究中的量子计算机和计算机神经网络系统才真正有希望解决这样的问题，达到人脑的能力。
对于电脑是“真脑”还是“皇帝的新脑”，还存在很大的争议，有很多的问题需要解决，很多都是现在世界上的顶尖科学家研究的尖端课题。我没有能力判断孰对孰错，但是我个人认为“人类思维也受哥德尔定理的限制”这点很有意思，很可能是正确的。各方面研究都表明，人脑在“运算”时，的确与电脑的基本原理是一样的，只不过电脑是用电子元件的“开、闭”和电信号的传递体现，人脑则表现为神经原的“冲动、抑制”和化学信号（当然也包括电信号）的传递。这与哥德尔定理的条件没有本质上的差别。而认识过程中的“思维是客观实在的近似反映，语言是思维的近似表达”这点，正是受哥德尔定理限制的结果。就拿语言（指形式上的）来说，完全可以转化为有限公理和一定规则下的符号逻辑系统，也就是一种符合定理条件的形式公理系统。该定理恰恰说明，这样的系统中不完备，存在不能用该系统证实的命题，对于这个系统来说，就是语言对思维的表达不完全，也就是我们常说的“只可意会，不可言传”。这也与我们经常感觉到的“辞不达意”是相吻合的，任何形式上的语言都不能完全准确的表达我们的思想。还有另一个事实也说明这点，就是翻译。文对文的形式语言翻译虽然不难，可是如实地表达原来语言中的准确蕴义就非常难了，甚至可以说是不可能的事情。如果能证明人类的思维也可以转化为这样的形式公理系统，那人脑也一定受哥德尔定理的限制。
但正如我一开始就说过的，就算受哥德尔定理的限制，也并不说明这样的系统就没有意义，就不能正确反映客观实在。就人类的思维来说，就是通过实践不断总结归纳从中获得的经验，加深对客观世界的认识，不断逼进“客观真理”的过程。这也就是辨证唯物主义的认识论。
还是那句话，这个定理虽然意义重大，但确实不好理解。上面是我个人的看法，不保证都对，只是希望通过探讨，共同澄清认识。
三
对哥德尔定理问题，丁丁虫提出了以下问题：
看来楼主对哥德尔不完备性定理的研究颇有深度，我一直对此定理有许多不解之处，还望楼主指点。
首先，哥德尔定理究竟对公理化体系有什么样的影响？
哥德尔定理证明了一个足够强的公理化系统必然会存在内在的矛盾，那么数学中的公理系统是否还有意义？就以数论而言，哥德巴赫猜想确实有可能是一个无法证明的问题，但如果我们拓展数论的公理集合，甚至直接将哥德巴赫猜想作为公理接受下来，岂不是就可以证明它了吗？
我想这个问题的实质应该是，谁来规定公理应该有哪些？为什么数学界将某些命题作为公理，却将另一些作为定理来证明？
第二个问题，哥德尔定理对人工智能的研究有什么影响？
彭加勒的《皇帝新脑》中提出，由于哥德尔定理的限制，所以电脑永远不可能拥有意识；同时他提出，人脑之所以能够摆脱哥德尔定理的限制，是因为人脑中存在无法研究无可复制的“微管”结构（好像是叫这个名字，具体我记不太清了，不过概念应该是没弄错的）。但是这种说法比起“人工智能不可实现”的断言更让人无法接受。毕竟“微管”也好、别的什么也好，只要它具有物理上实在性，就没有任何限制能够迫使人类无法复制它；而如果说“微管”不具有物理实在性，那和宗教上的灵魂说又有什么区别？
我以为的是，哥德尔定理仅仅证明了“在形式系统内”某些命题无法证实其真假，但是该定理并没有说命题的真假“无论如何”都不可知。实际上只要我们跳出形式系统的限制，那么许多问题都可以迎刃而解。楼主给的例子“数论中的皮亚诺公理不能单独在数论范围内证明，但可在集合论中证明”，显然就说明了这一点。
所以我的问题是，为什么人脑可以轻而易举地摆脱形式系统的限制，而电脑（或者说冯诺伊曼结构的电脑）就不可以？差异究竟在哪里？是物理结构上的，还是知识积累程度上的？楼主说到人类的“直觉”，但是我以为很多自指性悖论并不需要直觉参与就可以解决。比如“我说的这句是谎话”，对于人类来说，一眼就可以看出前面这句话是自相矛盾的，然后人脑就会简单地将它废弃，但是电脑为什么看不出这一点？是积累的知识不足，还是电脑所利用的数学体系本身的缺陷？
胡乱提了两个问题，自己恐怕都没有把意思表述清楚，楼主莫要见怪，呵呵。
对此，我回答如下：
下面先看您的第一个问题，就是公理是如何设定的。这里您有个错误理解，“哥德尔定理证明了一个足够强的公理化系统必然会存在内在的矛盾”。可能是我介绍的不够清楚，这个定理是比较专业，不好理解，几句话确实说不太清。不过从我的文中也能看出，第一定理说的是“不完备”，第二定理说的是“不能从内部证明相容性”。所谓“相容性”，就是没有内在的矛盾。这个定理并不否认这样的公理系统的相容性，只是说不能仅从内部证明，而事实上最典型的这样的系统――数论的公理系统已被证明是无矛盾的。所谓“公理”或“公设”，指的是“不证自明”的客观前提，也就是从长期实践中总结出来的客观规律。而且这样的规律不能由系统内其他公理推出――也就是独立性。拿欧氏几何来说，平行公设，就是这样的一条“公理”。它既符合实践所发现的现象，也不能由其他几条公设推出。但是如果有新的事实被发现，公理或公设也不是不能改变的。正是通过对平行公设的质疑，而发展出了非欧几何，并成为了相对论的助产士。而您提到的“公理系统”的扩展，就是通过实践，添加新公理或修正旧公理。然而哥德尔定理证明有些公理系统，无论怎样添加，只要是有限条公理的系统，都不能避免不完备。这就否定了希尔伯特派希望用形式化的有限公理系统建立数学大厦的基础的设想，而无限的不可递归的公理系统，是不能形式化的。如果从哲学意义上来说，我认为这正是“实践是检验真理的唯一标准”这一哲学命题的数学表述。
接着讨论第二个问题，人工智能。这是个尖端课题，还没有大家所公认的定论。我也只能从自己的理解出发，做些猜测而已。其实“直觉”这个词有时候很容易让人产生神秘感，好象是没有任何基础，突然就冒出来的。我认为这样理解并不正确。从我5楼的介绍和刚才的讨论中也应该看出，所谓的“直觉”，应该是通过大量实践，经验积累到一定程度而产生的阶段性总结。人脑的神经网络构造，其学习总结实践经验的效率要远比现在的人工智能系统高得多，而其所包含的不确定性――也就是我们常说的“模糊”分析――就是这种高效率的动力原因。人工智能虽然也能模拟这样的过程，但是由于技术等原因，其效率十分低下。但原理是一样的，要想解决这样的问题，就应该如您所说，“跳出形式系统的限制”，引入包含随机处理的不确定性。现在很多顶尖的科学家正在研究相关课题，要说定论，我看还早，也许等模拟的神经网络系统成型了（可能需要相当长时间，因为象人脑这样的系统实在是太复杂了），也就快有眉目了吧。
至于物理实在性问题，我认为没有考虑的必要，人类的思维也是人脑这样的“实在的”物质系统的功能和现象而已，这也就是我不大赞同“皇帝新脑”的原因。