梅尔文·亨里克森——哈维·玛德学院荣誉数学教授——对此进行了解释
库尔特·哥德尔因1931年发表他的不完备性定理而闻名。 |
对于几乎所有不是数理逻辑专家的读者来说，用数学上精确的语言陈述哥德尔不完备性定理只会掩盖其重要的直观内容。因此，我将用计算机语言重新措辞并简化它。
关于支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道： 订阅。通过购买订阅，您正在帮助确保未来能够继续发布关于塑造我们今天世界的发现和想法的有影响力的报道。
想象一下，我们可以访问一台非常强大的计算机，名为 Oracle。与我们熟悉的计算机一样，Oracle 要求用户“输入”遵循精确规则的指令，并以同样遵循这些规则的方式提供“输出”或答案。相同的输入将始终产生相同的输出。输入和输出都写成整数（或自然数），Oracle 只执行通常的加法、减法、乘法和除法运算（如果可能）。与普通计算机不同，无需担心效率或时间。Oracle 将执行正确给出的指令，无论需要多长时间，并且只有在指令执行完毕后才会停止——即使需要超过一百万年。
让我们考虑一个简单的例子。记住，如果一个大于 1 的正整数（我们称之为 N）除了 1 和 N 之外不能被任何正整数整除，则称为素数。您将如何要求 Oracle 判断 N 是否为素数？告诉它将 N 除以 1 到 N-1 之间的每个整数，并在除法结果为整数或达到 N-1 时停止。（实际上，如果达到 N 的平方根，您可以停止。如果在该点之前 N 没有被任何数整除，则 N 是素数。）
哥德尔定理所说的是，存在一些仅涉及整数算术的、正确提出的问题，Oracle 无法回答。换句话说，有些陈述——尽管输入正确——Oracle 无法评估以判断它们是真还是假。这样的断言被称为不可判定的，并且非常复杂。如果您将其中一个问题带给哥德尔博士，他会向您解释，这样的断言将永远存在。
即使您获得了一个“改进”的 Oracle 模型，称之为 OracleT，其中一个特定的不可判定语句 UD 被判定为真，也会生成另一个不可判定语句来取代它。更令人困惑的是，您也可能获得另一个“改进”的 Oracle 模型，称之为 OracleF，其中 UD 会被判定为假。无论如何，这个模型也会生成其他不可判定语句，并且可能会产生与 OracleT 不同的结果，但同样有效。
您是否觉得这令人震惊且接近悖论？当哥德尔在 1931 年公布他的不完备性定理时，数学界更加震惊。哥德尔没有用计算机语言表达他的结果。他是在一个确定的逻辑系统中工作的，数学家们希望他的结果取决于该系统的特殊性。但在接下来的十年左右，包括斯蒂芬·C·克莱恩、埃米尔·波斯特、J.B.罗瑟和艾伦·图灵在内的许多数学家证明并非如此。
对这项伟大定理的后果的研究一直持续到今天。任何可以使用互联网并通过 Alta Vista 等搜索引擎访问信息的人都可以找到数百篇关于哥德尔定理的文章，质量参差不齐。不过，最值得阅读的书籍之一是欧内斯特·内格尔和詹姆斯·R·纽曼合著的《哥德尔证明》，该书于 1958 年出版，并于 1983 年由纽约大学出版社发行平装本。