邏輯大結局——直覺、復雜度和終極悖論，統治一切的程式

在古希臘法庭上既沒有直接證據也沒有目擊證人會怎樣？陪審團不能依賴亞里士多德的邏輯，因為原告和被告都不使用邏輯來揭示真相。亞里士多德描述了以下一個案例：

一個小個子X指責一個大個子Y襲擊了他。一個陪審員問X一個假設性的問題：如果是你先挑起的爭斗呢？

• X可以爭辯說，一個更小更弱的人“不可能”挑起戰斗，因為他“肯定”會吃虧。
• 另一方面，Y可能會反駁說，他看起來比X大得多、強壯得多，“不太可能”發動戰斗，因為他在法庭上“肯定”百口莫辯。

陪審團需要決定哪一方的“推理”更“可信”，有趣的是，這種推理和數學家解決問題的原理是一樣的，

波利亞（George Pólya）：直覺作為似然推理

• 波利亞，1887 – 1985

波利亞，匈牙利數學家，現代數學教育問題之父，認為數學直覺的背后是似然推理，這與龐加萊關于邏輯和直覺的觀點一致，他的名言膾炙人口：

數學家創造性工作的結果是演示推理，但證據是通過似然推理和猜測發現的。

波利亞沒有贊美偉大的數學家的直覺，或者嫉妒他們的運氣，而是使用一本推理手冊來揭開他們的猜測藝術的神秘面紗，下面的圖表顯示了如何從一個一般的三角形開始，遵循不同的似然推理模式得到一個等邊三角形，通過類比得到一個四面體或多面體，通過概括來得到一個一般的多邊形。

• 似然推理模式

關于類比，波利亞說：

類比貫穿于我們所有的思維，我們的日常講話和我們得到瑣碎的結論，以及藝術的表達方式和最高的科學成就，

似然推理適用于解決問題，也適用于所有層次的科學發現。例如，圖靈在停機問題的不可解性和形式系統的不完備性之間進行了類比，哥德爾將其與德國數學家康托爾提出的關于實數是否多于自然數的問題進行了類比，

回顧希爾伯特的判定問題

現在，讓我們回顧希爾伯特的判定問題來看看似然推理或直覺在其中扮演了什么角色。由于判定問題產生于計算機發明之前，希爾伯特和他的同事們肯定不了解計算機科學，他們可能“直覺地”認為，“數學直覺”可以用簡單的蠻力搜索代替，在所有可能的證明步驟中，他們幾乎肯定忽略了這種搜索的運行時間，這是有問題的。為了理解這一點，如果我們換個方式問問題呢？考慮到我們只對比N短的證明感興趣，對不同的N，我們有計算判定問題。對于這樣一個計算判定問題，肯定有一個解決方案，那就是簡單地循環所有可能的比N短的證明。現在的問題從可能性變成了可行性：當N變大時，這種蠻力搜索可行嗎？

這就是計算復雜度的來源。根據計算復雜度理論，運行時間主要有多項式和指數兩種。給定一個規模為N的問題，前者的運行時間以N的多項式速度增長，如2N或3N^2，后者的運行時間以N的指數形式增長，如2^N或3^N，一個以指數增長的問題被認為是“不可行的”，因為對于這樣的問題，即使使用一臺消耗了宇宙中所有資源的計算機，也要等待宇宙的年齡那樣長的時間才能得到答案，

人類vs.機器證明

如果已經有一個證明，我們可以寫一個多項式時間程式來檢驗它的可行性，然而，這并不意味著一個程式“找到”一個證明是多項式時間。可以用多項式時間程式求解的復雜度類別稱為P，而通過“猜測”一個答案并在多項式時間內驗證它可以解決的問題稱為NP。我們可以看到，機器驗證是NP，復雜度類別P包含所有在多項式時間內可解的問題，它包含在NP中。一個問題是根據已知的解決它的最快程式分配一個復雜類別（如P或NP），因此，當發現一個更快的程式時，問題可能會改變類別。目前，計算判定問題被考慮在NP類中。對于機器證明多項式時間解是否存在有多大意義？

哥德爾預見到了計算復雜性理論的重要性，并在1956年寫給約翰·馮·諾依曼（1903-1957，數學家，物理學家，以馮·諾依曼結構而聞名）的信中寫道：

如果真的有一臺機器具有[運行時間]kN（或者甚至只有kN^2）[對于某個與N無關的常數k]，這將產生巨大的后果。也就是說，它將清楚地表明，盡管判定問題是不可解的，但數學家在是或否問題上的腦力勞動可以完全被機器取代，人們確實需要選擇一個如此大的N，如果機器沒有產生結果，那么也就沒有理由進一步思考這個問題，

“數學家的腦力勞動”是什么？根據龐加萊和波利亞，數學家解決問題分兩個階段：第一階段，使用似然推理（直覺），或猜測藝術，形成猜想；第二階段，使用邏輯來證明猜想，同樣，機器證明分為兩個階段：尋找證明和邏輯驗證證明。希爾伯特最初的問題是，是否存在一種普遍的證明機制來消除使用直覺的必要性。哥德爾有效地將問題重新表述為，是否存在多項式時間的“智能”搜索或相當于直覺的“巧妙”猜測。

• 機器證明vs人類證明

斯蒂芬·庫克和列奧尼德·列文：統治一切的程式

布爾可滿足性（SAT）問題詢問是否對布爾公式中的變量賦值為0 （FALSE）或1 （TRUE），例如(x1 ∨ ¬x2) ∧ (¬x1 ∨ x2 ∨ x3) ∧ ¬x1，它的值為1。斯蒂芬·庫克和列昂尼德·列文，美國-加拿大計算機科學家和數學家，俄裔美國數學家，分別獨立證明了SAT在P時，即具有多項式時間解，那么“所有”NP問題可以簡化為SAT，并在多項式時間內求解。換句話說，這意味著P=NP，因為所有NP問題都可以在多項式時間內被解決！

判斷這樣一個超級程式是否存在被稱為P vs NP問題，這被認為是現代科學中最大的開放性問題，正如我們現在所看到的，哥德爾所認為的“巨大的后果”實際上是P=NP。多項式時間SAT解算器是“一個程式來統治所有的程式”，就像《指環王》中的“一個環”，還有一些像SAT這樣的問題，它的答案是P=NP，所有這些問題統稱為NP完備問題，

今天的SAT解題器已經被用于解決數學難題、芯片設計、軟體檢查等許多領域，為什么我們仍然關注P vs NP？如果“一個程式”出現了，并由此證明了P = NP，那么它將與停機問題和普遍證明機制一樣具有破壞性。數學上的獨創性和創造力將變得微不足道，數學家們將不再需要在合理推理方面的訓練，事實上，它甚至會完全消除人工智能和機器學習領域充滿活力和激動人心的研究的必要性，從本質上說，這將是對數學家和計算機科學家的精神努力的最后一擊，今天，人們普遍認為“一個程式”不存在，即P != NP，就像圖靈證明停機問題無解一樣，證明P != NP是極其困難的，這種P與NP之間的屏障，似乎是“人類的守護者”。

人工智能與人類

如今，人工智能研究人員正試圖讓計算機學會我們如何利用直覺，而不是像形式主義者所希望的那樣，試圖取代人類的直覺。正如邏輯研究的是邏輯推理如何獨立于其應用的環境，現代AI研究的是相對獨立于其使用和產生的數據的直覺。

問題是，我們是想讓人工智能模仿我們每個人，還是跨代地模仿我們所有人？為了回答這個問題，讓我們來看看過去我們是如何解決難題的，

最長的證明（200tb）是對布爾畢達哥拉斯三元組問題的證明

有沒有可能把每個正整數都涂成藍色或紅色，這樣就不會有滿足勾股定理a^2+b^2=c^2的整數三聯體a、b、c是完全相同的顏色？

這個問題是在20世紀80年代提出的，然而，直到2016年Heule等人證明，到7824之前，用這種方式為整數著色是可能的，但從7825開始就不可能了，證據如此之長，人類要花100億年的時間才能讀取全部200tb的數據。

至于解決一個問題所需的時間，人類證明四色定理花了125年，費馬大定理更是花了358年！

關于人類能否成為人工智能的“榜樣”，可能有兩個問題：

1. 人類證明者在他們的證明中使用了計算機
2. 前面提到的這些問題在數學界被廣泛研究和討論了幾十年甚至幾個世紀之后才被解決，

對于第一個問題，人類將乏味的任務交給計算機就像一個程式調用子例程或庫，關于第二個問題，如果人類可以隨著時間的推移積累數學知識，那么人工智能使用互聯網的速度也可以快一個數量級，事實上，人工智能最近取得突破的原因之一是，它消耗和消化人類的思維。

看來，我們不是試圖讓人工智能成為一個數學天才，而是讓它遵循人類的集體思維，然而，人工智能是否能在辯論、頭腦風暴和交換想法方面模仿人類的智力合作還有待觀察，

最后一個悖論

讓我們回顧一下到目前為止所討論的內容：

1. 亞里士多德為正確的推理建立了邏輯，而用直覺建立了第一原則。
2. 從亞里士多德到希爾伯特，數學家和邏輯學家已經發展了從心理和語言技能到符號操作科學的高級邏輯，
3. 相信邏輯是基礎和唯一的驅動力，形式主義者努力“機械化”數學，以消除使用直覺和（對人類）有意義的必要性。
4. 哥德爾和圖靈表明，形式主義者的夢想是無法實現的“可計算性”，因為不可避免的自我參照悖論在他們的系統中；計算機被認為是一種證明直覺必要性的工具。
5. 從“計算復雜度”的角度來看，由于指數時間的蠻力搜索，判定問題的不可解性可以被視為不可行的，
6. 與形式主義者的直覺方法相反，人工智能研究人員正試圖模仿人類利用直覺解決問題的方式，

有朝一日人工智能會完全取代數學直覺嗎？哥德爾，一個自我承認的柏拉圖主義者，相信人類永遠優于計算機，而且永遠不會被計算機程式取代，他談到了人類思維的發展：

思維在使用中不是靜止的，而是不斷發展的，也就是說，隨著我們不斷地使用抽象術語，我們對它們的理解也越來越準確，越來越抽象的術語進入了我們的理解范圍。

顯然，他并沒有把人類優于機器的原因歸結于個人，而是歸結于集體的、跨代的人性。矛盾的是，如果人類如此優越，為什么它不能在足夠的時間內寫出能思考的程式？隨著我們的發展，人類的思維一直在不斷進化，在電腦發明后，我們不再強調用算盤計算，也不再使用紙和鉛筆計算，事實上，我們仍處在發現我們為計算機編程的潛力的早期階段，

另一方面，圖靈相信機器最終可以超越人類：

不可能同時戰勝所有的機器，簡而言之，可能會有人比任何機器更聰明，但也可能會有其他機器更聰明，以此類推。

然而，圖靈認為，人類將是決定機器是否比人類更聰明的最終裁判。在他具有里程碑意義的論文《計算機器與智能》中，圖靈描述了圖靈測試，在這個測試中，一臺計算機試圖以智慧戰勝一個人類審問者，使其相信自己是人類，他提出，如果人工智能能夠通過這樣的測試，它就應該被認為是能夠思考的，

發展中的思維和更聰明的AI之間的自我參照關系如下所示：

另一方面，如果人類和人工智能在這樣一個正反饋循環中相互提升會發生什么？那么，接下來要問的問題就是：人類和人工智能是否會融合在一起，成為科幻小說和推測性未來預測中經常描述的那種類似上帝的實體？例如，在艾薩克·阿西莫夫的科幻短篇小說《最后一個問題》中，人類一直在詢問全球人工智能計算機Multivac，如何逆轉熱力學第二定律，使宇宙免于熱死，故事以萬能的進化人，Multivac的后代與人類融合，點燃了下一個宇宙的大爆炸而結束。

在現實中，根據圖靈的說法，隨著我們不斷發展人工智能，我們對自己的了解也越來越多：

整個思考過程對我們來說仍然相當神秘，但我相信，制造一臺思考機器的嘗試將極大地幫助我們“發現我們是如何思考自己的”，

然而，人工智能預測的準確性必須得到重視，它推理的優雅必須得到贊賞，它模仿我們的程度必須令人敬畏。最終，在沒有人工智能的情況下，大腦將如何保持優越性？誰將驗證人工智能是否更聰明？這也許是最后一個悖論。

邏輯的極限與數學的困境，羅素用了362頁才推導出1+1=2

機器人之死——邏輯、直覺和悖論，決策者的困境