TUhjnbcbe - 2023/9/16 19:24:00
在17世纪，德国数学家戈特弗里德·莱布尼茨提出了一种机器，它可以读取任何作为输入的数学陈述，并根据数学公理决定它是对还是错。但是每个陈述都可以判定吗？这个问题被称为决策问题。两个世纪后，另一位德国数学家大卫·希尔伯特乐观地宣称，决策问题问题的答案必须是：是的，我们能够而且将会知道任何数学问题的答案。年在德国哥尼斯堡的一次演讲中，他说了一句名言，Wirmussenwissen-Wirwerdenwissen。(我们必须知道，我们将会知道”)但真的吗？数学的极限希尔伯特的乐观是短暂的。同年，奥地利数学家哥德尔通过证明他著名的不完全性定理，证明了我们在数学方面的知识是有限的。下面是理解哥德尔定理的一种简化方法：命题S：此命题不可证。现在，假设在数学的背景下我们可以证明S是真的。但是，这种说法本身就是错误的，导致了不一致。让我们假设相反的情况，我们不能在数学的范围内证明S。但这意味着S本身是正确的，数学中至少有一个命题是正确的，但不能证明它是正确的。因此，数学要么不一致，要么不完整。如果我们假设它是一致的（陈述不可能同时是真的和假的），这只会留下数学是不完整的结论，也就是说，有真实的陈述根本不能证明是真的。哥德尔对不完全性定理的数学证明，比我在这里概述的要复杂得多，从根本上改变了希尔伯特宣扬的完整知识是可行的观点(“wirwerdenwissen”)。换句话说，如果我们假设数学是一致的，我们一定会发现无法证明的真实陈述。以哥德巴赫猜想为例，根据哥德巴赫猜想，每个偶数都是两个素数的和：6=3+38=3+=3+=7+5，以此类推。还没有人找到一个反例。因为哥德尔的存在，我们知道有些真实的陈述是没有证据的，但不幸的是，我们没有办法识别这些陈述。哥德巴赫猜想可能是其中之一，那么试图找到证据将是浪费时间。哥德尔和图灵计算的极限当艾伦·图灵第一次学习哥德尔不完全性定理时，他还是剑桥大学的一名研究生。在那段时间里，图灵致力于设计出能够处理任何输入并计算结果的机器的数学设计，就像莱布尼茨几个世纪前设想的那样。这些概念化的机器今天被称为图灵机，并被证明是现代数字计算机的蓝图。简单地说，图灵机可以比作一个现代计算机程序。图灵正在研究所谓的停机问题，可以提出如下问题：是否有一个程序可以决定另一个程序是否会停止（完成执行）或不（永远循环）？图灵证明了停机问题的答案是“不”，这样的程序不可能存在。与哥德尔的工作相似，他的证明是一个“矛盾的证明”。假设存在一个程序halts()，它决定给定的程序是否会停止。然后我们还可以构建以下程序：defg():ifhalts(g):loop_forever()return看这里发生了什么？如果g成立，g不成立，如果g不成立，g成立。不管怎样，都有矛盾。因此，程序halts()不能存在。哥德尔证明了数学是不完整的，图灵证明了计算机科学在某种意义上也是“不完整的”。某些程序根本无法存在。这不仅仅是一个理论上的好奇：中止问题在今天的计算机科学中有许多实际的含义。例如，如果我们想让编译器为一个给定程序找到尽可能快的机器码，我们实际上是在尝试解决停机问题——而我们已经知道这个问题是不可解决的。一个复杂的蛋白质结构-预测蛋白质如何折叠是一个NP问题。知识的实际极限：PvsNP问题哥德尔和图灵通过展示一些根本无法解决的问题，证明了我们所知道的东西在理论上是有限的。但除此之外，还有一些问题我们可以在理论上解决，但不能在实践中解决，因为计算解太耗时了。这就是我们要区分P问题和NP问题的地方。P问题是可以在“合理时间”内解决的问题，而“合理”在这里意味着“多项式（polynomial）”（简化为P）。为这些问题寻找解决方案的计算复杂度随着问题输入的大小而增加。想想乘法或排序问题。NP问题是指不能在合理时间内解决的问题。NP是non-deterministicpolynomial的缩写，意思是一个解可以被确定，但不能被找到，计算复杂度为多项式。求解NP问题的复杂性是指数型的，而不是多项式型的，这在实际中产生了巨大的差异。NP问题的例子有最优调度、预测蛋白质如何折叠、加密消息、解决数独难题、最优包装（又名背包问题）。有些问题，比如寻找一个函数的离散傅里叶变换，从NP开始，但最终以P结束，因为新的、聪明的算法的发展简化了求解过程。今天计算机科学中最大的未解问题之一就是P与NP的问题：P是否等于NP？也就是说，对于我们能够在合理的时间内确定解决方案的问题，我们是否也能够在合理的时间内找到解决方案？PvsNP问题如此重要，以至于它被列入了“千禧奖问题”的名单中，如果你找到了答案，你将获得万美元的奖金。很难再夸大这个问题的重要性：一个P=NP的世界与一个P≠NP的世界将有根本不同。如果P=NP，那么我们可以肯定地说，有一种更快的方法来解决数独游戏，或者预测蛋白质如何折叠，只是我们还没有找到那种方法。不用说，了解蛋白质如何折叠可能会对现实世界产生各种各样的影响，比如了解阿尔茨海默氏症或治疗癌症。今天的大多数科学家认为P不等于NP，但我们能确定吗？P对NP问题本身可能类似于希尔伯特的决策问题或图灵的停止问题，这个问题可能根本没有答案。