知识的极限

Posted on In

在 17 世纪，德国数学家戈特弗里德·莱布尼茨（Gottfried Leibnitz）提出了一种机器，该机器可以读取任意数学陈述，并根据数学公理来判断其是否正确。但是，每个陈述都可以这样判定么？或者我们所能知道的东西是否存在着极限呢？这个问题被称为 Entscheidungsproblem（判定性问题）。

两个世纪后，另一位德国数学家戴维·希尔伯特（David Hilbert）乐观地宣布，判定性问题的答案必须是，是的，我们能并且会知道任何数学问题的答案。他于 1930 年在德国柯尼斯堡（Königsberg）的一次讲话中曾说：

Wir müssen wissen — wir werden wissen.（“我们必须知道 —— 我们会知道。”）

但是我们会知道吗？

数学的极限

历史表明希尔伯特的乐观主义是短暂的。同年，奥地利数学家库尔特·哥德尔（Kurt Gödel）通过证明他著名的不完备定理（incompleteness theorem）表明我们的数学知识是有极限的。

下面是理解哥德尔定理的简单方法。请考虑以下陈述。

命题 S：此命题不可被证明。

现在，假设在数学中我们可以证明 S 为真。但是这样一来，命题 S 本身将为假，从而不一致。好吧，那么让我们假设相反的情况，即我们无法在数学中证明 S。但这将意味着 S 本身为真，并且数学中包含至少一个无法证明为真的真命题。因此，数学要么不一致，要么不完备。如果我们假设它是一致的（命题不能同时为真和假），这只能得出数学是不完备的结论，即存在不能完全证明是真命题的真命题。

哥德尔（Gödel）对不完备定理的数学证明比我在此概述的要复杂得多，这从根本上改变了希尔伯特（Hilbert）所宣称的完整知识是可行的观点（“我们会知道”）。换句话说，如果我们假设数学是一致的，那么我们必然会发现无法证明的真命题。

例如，哥德巴赫猜想（The Goldbach conjecture），根据该猜想，每个偶数都是两个素数的和：

6 = 3 + 3 8 = 3 + 5 10 = 3 + 7 12 = 7 + 5，依此类推。

至今还没有人发现反例，如果猜想是真的，那也就不存在反例。得益于哥德尔的贡献，我们知道有无法证明的真命题，但不幸的是，我们没有办法找出这些命题。哥德巴赫猜想可能就是其中之一，如果是这样，那么尝试证明它就是浪费时间。

Kurt Gödel（左）和 Alan Turing（右）

计算的极限

艾伦·图灵（Alan Turing）第一次了解哥德尔不完备定理时还是剑桥大学的研究生。在那段时间里，图灵忙于做一种机器的数理设计。这种机器可以处理任何输入并计算结果，与莱布尼茨几个世纪前所设想的相似。今天这些概念化的机器被称为图灵机，是现代数字计算机的蓝图。简单来说，图灵机可以看作现代计算机程序。

图灵当时在研究所谓的停机问题，可以描述如下：

是否有一个程序可以确定另一个程序会停止（停机）还是不停（死循环）？

图灵证明了停机问题的答案是“否”，即不存在这样的程序。与哥德尔的工作类似，他也是用“反证法（proof by contradiction）”证明的。假设存在一个程序 halts()，它能确定给定程序是否将停止。但是，我们还可以构建以下程序：

1
2
3
4
def g():
    if halts(g):
        loop_forever()
    return

看看这里发生了什么？如果 g 成立，则 g 不成立；如果 g 不成立，则 g 成立。无论哪种方式，我们都将得到一个矛盾。因此，程序 halts() 不存在。

哥德尔证明了数学是不完备的，而图灵证明了在某种意义上计算机科学也是“不完备的”。某些程序根本不存在。这不仅是理论上的好奇：停机问题在当今的计算机科学中具有许多实际意义。例如，如果我们希望编译器为给定的程序找到最快的机器码，那么我们实际上是在尝试解决停机问题 —— 而我们已经知道该问题是无法解决的。

一个复杂的蛋白质结构 —— 预测蛋白质如何折叠是一个 NP 问题（NP-problem）

知识的实际极限：P 与 NP 问题

哥德尔和图灵通过揭示存在着的一些根本无法解决的问题，证明了我们所能知道的在理论上存在极限。但是此外，还有其他问题是理论上可以解决，但是因为求解的时间太长了，而我们实际上无法解决的。这里我们将会说明 P 问题和 NP 问题的区别。

P 问题是可以在“合理的时间”内解决的问题。在这里，“合理的时间”的含义是“多项式（polynomial）时间”（因此称为 P）。求解这些问题的计算复杂性随问题输入规模的增长而倍数增加（想想乘法或排序问题）。

另一方面，NP 问题是无法在合理时间内解决的问题。NP 是非确定性多项式（non-deterministic polynomial）的英文缩写，它的含义是可以用多项式级的计算复杂度验证问题的一个解，但不能用多项式级的计算复杂度求解。求 NP 问题的解的复杂度是指数级的，而不是多项式的，这会产生巨大的实际差异。NP 问题的例子包括最佳调度，预测蛋白质的折叠方式，加密消息，解决数独难题，最佳包装（又称背包问题）或最佳路由（又称旅行商问题）。一些问题（例如找到函数的离散傅立叶变换）最开始属于 NP 问题，但由于开发了新的、巧妙的算法来简化求解，最终变成了 P 问题。

当今计算机科学领域中最大的未解之谜之一就是 P 与 NP 问题：P 是否等于 NP？换句话说，对于所有我们可以在合理时间内验证一个解的问题，我们是否能在合理的时间内求解？

P 与 NP 问题非常重要，因此被列入“千禧年大奖难题（Millenium prize problems）”。如果找到答案，你会赢得一百万美元。再怎么夸大这个问题的重要性也不为过：P=NP 的世界与 P≠NP 的世界有着根本的不同。如果 P=NP，那么我们可以肯定地说，有一种更快的方法可以解决数独难题，或者预测蛋白质的折叠方式，我们只是还没有找到这种方法。毫无疑问，了解蛋白质的折叠方式会对现实世界产生全方面的影响，例如理解阿兹海默症的病理或治愈癌症。

如今，大多数科学家相信 P 不等于 NP，但是我们能确定吗？P 与 NP 问题本身可能类似于希尔伯特的 Entscheidungs 问题或图灵的停机问题：这个问题可能根本没有答案。

参考资料和进一步阅读

  • 《复杂》梅拉妮・米歇尔
  • P vs NP 和动物园的复杂性（视频）
  • 哥德尔不完备定理（视频）

如果你喜欢本文，也可以查看以下内容：

本文发布于掘金：https://juejin.im/post/6874475968325484552