“我向库尔特·哥德尔教授提问海森堡不确定性原理和他的不完备性定理有何联系，教授登时大怒，将我轰出办公室”
——约翰·惠勒
“设想一支强大的外星军队，以摧毁地球要挟我们交出R（5,5）的准确值，安全起见我们应动用一切人力物力以求解该值。然而，如果外星人要的是R（6,6），只好兵戎相见了。”
——保罗·厄多斯
尽管哥德尔的不完备性定理常被认为是对大卫·希尔伯特宏伟计划的沉重打击，而且，常被引申为“不存在求解一切数学问题的万能钥匙”“纯粹抽象的领域也存在着不确定性”以“限制”人类的认知，甚至于被哲学爱好者用于同量子力学的不确定性原理一起说明不可知论的主张。哥德尔本人却从没因此觉得数学中存在什么不确定性，在他看来，不完备性只能说明我们应该不断地（基于非形式逻辑的依据）向既有的体系中添加新的公理，假以时日，任何合理的数学问题还是都能得到解答：
Namely, it turns out that in the systematic establishment of the axioms of mathematics, new axioms, which do not follow by formal logic from those previously established, again and again become evident. It is not at all excluded by the negative results mentioned earlier that nevertheless every clearly posed mathematical yes-or-no question is solvable in this way. For it is just this becoming evident of more and more new axioms on the basis of the meaning of the primitive notions that a machine cannot imitate.（Kurt Goedel，1961）
不难看出：添加新公理的时候，原体系中肯定还有尚未被我们证明的定理（我们不知道它们是定理），怎么保证我们不会误把蕴含着这种定理的否定的命题当成新公理添加进去呢？一旦这种事情发生就意味着新的体系中包含了矛盾——一种似乎绝对应该避免的情形。
避免矛盾的办法，是设法保证添加的新公理总是和先前的体系独立。然而，恰如哥德尔自己提出不完备性定理一样，阿兰·图灵和阿伦佐·丘奇带来了看来十分扫兴的结论：对足以容纳当前数学的有效形式体系，这种独立性是不可判定的。
虽然有这些不利的结果，哥德尔依然对“将数学机械化”这个目标抱有信心，认为像图灵机这样的机器不能完全取代数学家，但却另有大用。
哥德尔致冯·诺依曼的信件节录
1956年，哥德尔在与约翰·冯·诺依曼的私人通信中提及，一台能快速判定命题在给定形式体系中是否存在长度n以下的证明的计算机，将可能彻底改变整个数学的面貌。
不难看出，这种计算机实际上以另一种方式实现了希尔伯特的梦想。只须将需要判断真假的命题和它的否定一并输入计算机，选取很大的n对正反两命题进行判定，只要不是双方证明都存在的情形，就以在证明长度n以内未发现矛盾为据，假定我们的体系是可靠的。这样，若是只有一方存在证明，我们就成功判断了命题的真假。若是双方证明都不存在，那么，也有充分的理由放弃这种问题了，因为命题要么是独立的，要么就需要作出不现实的复杂证明才能解决。
当然，如果在双方证明不存在的情形中选择坚决不放弃，出路也是存在的，那正是哥德尔所期望的，将适当的新公理加入到原体系中，加强现有的理论。这既可以允许证明原本独立的真命题，也可以使原有定理的过度复杂证明得到大幅简化（由知名度略低但思路相仿的哥德尔加速定理）。
读者可能会质疑，希尔伯特原本希望的是所有数学问题都有满意的答复，不期待这种可能会出现含糊的情形。这是因为没有注意到，即使那种完备且无矛盾的体系真的可以实现，其中依然会存在无限多证明长度高得不现实的定理的，而由于现实时间限制，还是有很多问题的解答必须放弃——想想R（100,100）。考虑到这点后，会发现哥德尔的计划与原版的差别是可以忽略的。
一旦这种计算机实现，则改变的不止是数学，因为在实际科学和工程领域也是存在大量能被约化成这种判定的问题的，它们也因此得到了统一的解法，参数n可以根据问题在实际学科中的价值来选取。哥德尔与诺依曼的通信在20世纪80年代被重新提出来，正是因为计算理论家认为，哥德尔在没有NP复杂类概念的时代，“预见”了NP完备问题的这种意义。
因为只涉及有限长度的证明，不可判定性完全不是障碍。会成为障碍的是计算的时间，如果用暴力法逐步检查所有长度n以下的证明，原则上能达到目的，但由于步骤数随n指数增长，一旦n>203则连基本物理定律都不允许这种计算完成。这么小的n显然不能满足我们的需要。
哥德尔用线性或平方时间作为这种计算可行的标准，向诺依曼询问其可能性。遗憾的是，我们现在可以说：哥德尔设想的计算机应该是不可能的——很可能对于NP完备的问题，不止是线性或平方，甚至任意高阶的多项式时间算法都是不存在的。尽管因为相关的猜想还悬而未决，给哥德尔与希尔伯特的构想留下了最后一丝希望。
NP完备问题发现者之一，Leonid Levin的网站配图
网友评论