數學和計算都是人類為了對自然世界進行推理而發展出來的工具。
撰文 | 摩西·瓦迪（Moshe Vardi）（計算機科學家，美國萊斯大學教授）
數學到底是由人類發現還是發明的，這是數學哲學中最根本的難題之一。一方面，對於如不可達基數之類高度複雜的數學物件，似乎很難論證說它們是被發現的。但另一方面，正如愛因斯坦也曾問道：“數學作為人類思維的產物，與經驗無關，其如何能如此完美地適用於自然物件呢？”19世紀的數學家利奧波德·克羅內克（Leopold Kronecker）作出了妥協，他說：“上帝創造了整數，其他一切都是人思想的產物。”
於是，讓我們考慮考慮自然數。在非洲萊邦博山的一個洞穴中人們發現了一塊由狒狒脛骨製成的骨質工具，上面有刻痕，人們稱其為萊邦博骨。這塊骨頭有四萬多年的歷史，人們推測它是用來計數的，上面的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，中文文稿經由“水木邏輯”翻譯整理而成。
特 別 提 示
1. 進入『返樸』微信公眾號底部選單“精品專欄“，可查閱不同主題系列科普文章。
2. 『返樸』提供按月檢索文章功能。關注公眾號，回覆四位陣列成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。
