其他
数学与计算，孰先？
The following article is from 水木逻辑 Author 摩西·瓦迪
加星标，才能不错过每日推送！方法见文末动图
数学和计算都是人类为了对自然世界进行推理而发展出来的工具。
于是，让我们考虑考虑自然数。在非洲莱邦博山的一个洞穴中人们发现了一块由狒狒胫骨制成的骨质工具，上面有刻痕，人们称其为莱邦博骨。这块骨头有四万多年的历史，人们推测它是用来计数的，上面的29个凹槽也许对应着月相的变化。它被认为是最古老的数学工艺品。但我们不应该称它为最古老的计算工艺品吗？毕竟，计数是计算最基本的形式。
在数学史上，演绎论证大约在 2,500 年前由希腊人发现，这一发现也被称为“希腊之谜”。毕达哥拉斯（Pythagoras）认为他对其定理的证明是“神的恩赐”。演绎证明提供了某个命题成立不容置疑的证据 —— 它是通向真理的康庄大道。
希腊人还发现了说谎者悖论。对于一个指涉自身的句子，我们可能无法判断其真假。十九世纪，格奥尔格·康托（Georg Cantor）用自指性的思想证明了存在无穷多个不同的无穷——克罗内克对此结果则不予理会，他认为“那里没有数学”。随后，伯特兰·罗素（Bertrand Russell）又运用类似的思想证明了集合论是不一致的。集合论作为数学的基础理论竟会推出矛盾，这引发了所谓的数学基础危机。数学证明为数学真理提供了不容置疑的证据，但到底什么构成了证明？
作为对该危机的回应，大卫·希尔伯特（David Hilbert），二十世纪上半叶最具影响力的数学家之一，发起了希尔伯特计划。该计划主要包含三个方面，其目标是证明数学是一致的（不能同时证明一个数学命题及其否定），数学是完备的（所有为真的数学陈述都可以被证明），数学是可判定的（存在一种机械的算法来判定一个给定的数学陈述为真还是为假）。
上世纪三十年代，库尔特·哥德尔（Kurt Gödel）摧毁了希尔伯特计划的前两个目标，他证明了基础算术不是完备的，且其一致性也无法在算术本身中得到证明。不久之后，阿隆佐·邱奇（Alonzo Church）和艾伦·图灵（Alan Turing）的工作让最后一个目标也成了幻梦。他们定义了可计算性，并说明了数学真理是不可计算的。人们可以将该结论理解为数学的领域超越了可计算的领域。
然而，计算机科学是在希尔伯特计划的废墟上诞生的：我们从此有了可计算性的定义、硬件与软件的区分、以及通用计算机的概念。在这惊人的历史交汇中，真正的计算机很快就被建造出来：1941 年由楚泽（Zuse）制造的 Z3，1942 年的阿塔纳索夫-贝瑞计算机（Atanasoff-Berry Computer，ABC），以及 1946 年的ENIAC——第一台数字、电子、可编程的计算机。
上世纪五六十年代，随着计算的价值在科学和商业中逐渐凸显，我们很快发现仅仅了解可计算性是不够的。解决某些计算问题似乎需要大量的时间和空间资源。某些问题似乎只能通过穷举搜索来解决，而随着问题参数的增加，这将很快变得不切实际。计算复杂性理论就是为了理解这些现象发展起来的学科。
上世纪七十年代初出现的 NP 完备性理论正是旨在理解穷举搜索的困难程度。若一个问题属于 NP，则我们可以非常有效地检验该问题一个可能的答案是否是正确的。NP 完全的问题是那些在某严格意义上属于 NP 的最难的问题。史蒂芬·库克（Stephen Cook）和列昂尼德·列文（Leonid Levin）证明了处于演绎推理核心的布尔可满足性问题是 NP 完全的。然而，目前我们仍不知道是否真的无法有效解决 NP 完全的问题。
1979 年，基于 NP 完备性理论，库克和罗伯特·雷克豪（Robert Reckhow）终于回答了这一最基本的问题，即数学证明是什么：它是某种极其严格的证据，以至于可以通过计算对其正确性进行检验。如此看来，数学终究没有超越计算。相反，计算始终位于数学的核心。
那么，数学和计算孰先？都不是！它们都是人类为了对自然世界进行推理而发展出来的工具。数学和计算已经交织在一起四万多年了，今后也仍将继续如此。
本文经授权转载自微信公众号“水木逻辑”，原标题为《清华逻辑随笔 | 摩西·瓦迪：数学与计算，孰先？》，本文英文原文发表于 Communications of the ACM, Nov. 2023, Vol. 66 No. 11, Page 5，中文文稿经由“水木逻辑”翻译整理而成。
相关阅读
5 为什么要证明？
近期推荐
特 别 提 示
1. 进入『返朴』微信公众号底部菜单“精品专栏“，可查阅不同主题系列科普文章。
2. 『返朴』提供按月检索文章功能。关注公众号，回复四位数组成的年份+月份，如“1903”，可获取2019年3月的文章索引，以此类推。
找不到《返朴》了？快加星标！！
长按下方图片关注「返朴」，查看更多历史文章