2018年02月27日 08:19 來源：中國社會科學網-中國社會科學報 作者：陳曉華 譚浩
字號內容摘要：終極算法無法超越哥德爾不完全性定理?筵陳曉華譚浩哥德爾不完全性定理被譽為「邏輯和數學史上的一座裡程碑」。由它產生的對「可證明」與「真」的討論，直到圖靈所產生的「可計算」與「不可計算」的討論，再到如今「計算」與「超計算」、「可計算」與「可學習」的討論，構成了對心靈、智能研究的一條線索。佩德羅·多明戈斯《終極算法》一書提出的「終極算法」理想，對於解決上述主題的問題提供了一定的思路。「終極算法」超越局限的可能性在多明戈斯的書中，「終極算法」是指通用學習算法，這也是「終極算法」的中心假設：所有知識，無論是過去的、現在的還是未來的，都有可能通過單個通用學習算法來從數據中獲得。
關鍵詞：
作者簡介：
哥德爾不完全性定理被譽為「邏輯和數學史上的一座裡程碑」。由它產生的對「可證明」與「真」的討論，直到圖靈所產生的「可計算」與「不可計算」的討論，再到如今「計算」與「超計算」、「可計算」與「可學習」的討論，構成了對心靈、智能研究的一條線索。佩德羅·多明戈斯《終極算法》一書提出的「終極算法」理想，對於解決上述主題的問題提供了一定的思路。
哥德爾不完全性定理視域下早期人工智慧的局限性
基於哥德爾不完全性定理的推論，可以得出形式算數本身的不可判定，即給定在形式算數中任意的公式，不存在統一的遞歸方法來確定它是不是其中的定理或者它是否恆真。在這裡，形式算數指初等數論的遞歸形式化，包括此形式化的形式系統都存在不完全性。
早期的人工智慧基於物理符號系統假設，一是任意合理的物理符號系統可以充分地獲取智能，二是表現一般智能的主體都必須是物理符號系統的一個實例。也就是說物理系統表現一般智能行為的充分必要條件是一個物理符號系統，這也是人工智慧符號學派建立的基礎。由此看出，無論對於機器的計算還是人工智慧的構建來說，如果包含了初等數論，由於形式化方法原則，它們都要受到哥德爾不完全性定理的制約。也就是說，從符號學派的觀點，哥德爾不完全性定理所引發的人工智慧的局限性在於人工智慧的不完全性。
當前機器學習對人工智慧局限性的解答
不可計算問題類的存在，同樣也表明人對於此類問題的不可計算。一方面，人類對於不可計算問題的真的確認，可能可以不通過計算的方式到達；另一方面，以上所講的計算都屬於遞歸計算問題，可能可以找到超越遞歸計算的計算方法。而對於人工智慧而言，物理符號系統假定所展示的智能可計算觀點及其局限，或許可以從以上兩個方面突破。
機器學習作為當前人工智慧研究的熱門內容，已經在某些方面突破了固有的局限。連接學派通過模擬生物神經網絡來構建人工智慧的神經網絡系統，通過正向傳播算法來獲取神經網絡每一個神經元的激勵節點的值，通過反向傳播算法來獲取每個激勵節點的值的平均誤差的下降梯度，通過梯度下降算法來獲取每個節點的最優參數（使平均誤差最小），最後這一切在最終輸出神經元的帶領下以獲得輸出函數的值。輸出函數在輸入數據作為訓練用例的基礎上，通過以上方法成為一個能正確預測未知數據的函數，它並不完全依賴於對明確推理和描述世界的符號的預解釋。人工智慧中的知識不在特定符號中而在整個神經網絡的參數中，物理符號系統所假設的知識到符號的必要性映射，在這裡就行不通了，因為知識到神經網絡參數的映射有可能一對多，也就是說對網絡中的參數可以有不同的解釋。
神經網絡超越物理符號系統假設是可能的，但是它沒有在實質意義上超越圖靈計算的局限。智能等同於計算，而計算已經不僅僅是圖靈計算而是超計算的問題。但是在現實物理世界中，在超計算的指導下製造出來的計算機沒有一個能超越通用圖靈機。而在超越圖靈計算的意義上，自然計算指導下的進化學派從進化論的觀點獲得啟示，主要利用的是遺傳算法的湧現模型。遺傳算法把問題的候選解決方案之間的關係看作競爭關係，而不是簡單組合陳列；通過適應函數評估決定是否對下一代方案的形成作出貢獻；最後通過類似染色體基因轉換的方法，產生下一代候選解。這是一種對於多個主體間的交互機制的最簡單的表達。而湧現模型也探討單個主體內的達爾文自然選擇機制。最簡單的表達是細胞自動機，即細胞的下一狀態是前一狀態和輸入數據的函數。顯然，已有的狀態會產生新的狀態，新的狀態會產生另一個新的狀態，直到無盡。但是如果我們加入適應函數來評估它，單個主體也會受到進化的限制。以上兩者加一塊便是我們想要的基於遺傳與湧現的社會智能模型，在模型中主體自身進化、主體間的交互都受到自然選擇機制約束。自然選擇機制，不是說它們都按照全局優化的目標去做，而是說在不同的各自目標下，以類似社會的方式湧現智能。
當前機器學習對於上述局限的回答還不盡如人意，卻已經產生了新的問題。PAC（probably approximately correct）學習理論表明，對機器可學習的定義不像圖靈可計算那樣是由算法定義的，而指由從合理數量的訓練數據中通過合理的計算量可靠地學習到知識。PAC更是指出機器學習存在訓練數據不是非典型的概率和算法找到符合要求的知識的概率，它們之間在機器學習得以成功的概率關係就被稱之為「可能近似正確」（PAC）學習理論。這表明，一方面，機器學習如果要達到超越圖靈計算的效果可能只是近似的結果；另一方面，對先驗知識與正確度期望值的設定將一直影響你的機器學習，從語義上講，你得到的超越性結果可能也只是你已經為機器設立的目標，而機器自己往上靠的結果。這一結果已經在人的心中存在，而機器並沒有證明它，只是承認它。