邏輯與計算

圖靈指出：“我希望數字計算機能夠最終激起人們對符號邏輯的極大興趣……人與這些機器的交流的語言構成了一種符號邏輯。”[1]（Ｐ122）圖靈所暗示的就是：程序設計語言不過是一種邏輯語言，而程序（或稱算法）不過是用該語言表示的一列推理規則。蒯因也曾寫道：“證明理論中的基本概念與機器計算理論中的基本概念相一致……（使得）關于數學證明的純理論與關于機器計算的技術理論在底部合二而一。”[2]（Ｐ41）但是，邏輯和計算究竟是如何關聯的？本文主要從邏輯學演進的角度探討這一問題，并簡要介紹我們的相關工作。

一、萊布尼茲： 推理和計算都是符號演算

對邏輯推理的形式化處理可以追溯到亞里士多德。早在公元前350年，亞里士多德就通過對各種推理模式的分析，提出了三段論。它曾一度被認為是推理的唯一邏輯范式，即使現在，它也是邏輯的重要組成部分。現在看來，亞里士多德的貢獻還在于，人們可以把推理看成是對符號的操作。不過，最早看到這一點的應當是萊布尼茲，在他青年時期，數學研究迅速發展，處理代數表達式的方法已經系統化。笛卡爾和費馬的工作表明，通過引入直角坐標系，可以把幾何還原為代數。特別是，萊布尼茲（與牛頓）獨立地創立了微積分，并成功地引入微積分運算符號，使得人們能夠很容易地理解微積分。這些成功范例，激發了萊布尼茲建立一個通用語言的信念，尋找一個可以表達人類思想的符號系統，其中每個符號都以一種自然的方式表示一個確定的概念，進而發展出一種語言以及操縱這些符號的工具，使得僅憑符號演算，就可以確定用這種語言寫成的哪些句子為真。萊布尼茲或許把人類所有的思維活動（包括推理與計算）都看成了符號演算。

二、布爾：邏輯推理即代數運算

布爾早期只是把代數方法應用于那些被稱為微分算子的對象上，蘇格蘭邏輯學家威廉·哈密爾頓與德·摩根之間的一場爭論，使得布爾的思想靈光閃現，即邏輯關系也許可以表示成一種代數。如果用x，y表示兩個類，布爾就用xy表示既在x中又在y中的對象的類，顯然應該有xx=x。布爾用記號xy暗示普通代數中的乘法，于是只有當x為0或1時，xx=x才成立。進而，布爾用x+y表示或在x或在y中的對象的類， 1-x表示不在x中的對象，從而x+(1-x)=1。下面我們通過一個例子來看布爾是如何把推理轉換成代數運算的。我們知道如下是一個有效的三段論的例子：

這個三段論是有效的， 即無論x，y，z被代之以什么樣的性質，只要前提是真的，結論就一定是真的。那么如何證明這是有效的呢?布爾是這樣做的：說所有x都是y，即指x的每個東西都屬于y，因而可表示為x=xy。類似的，所有的y都是z可以表示成y=yz。從而x=xy=x(yz)=(xy)z=xz， 即所有的x都是z[3]（P37）。

三、弗雷格：一個真正的符號演算系統

布爾的工作表明邏輯可以成為一個數學分支。在弗雷格看來，這是用邏輯來發展邏輯，產生了循環。因此，弗雷格認為，他的邏輯系統是不能用邏輯來發展的，而是要采用精確的語法規則或句法規則把他的概念文字發展成一種人工語言，進而把邏輯推理表示為機械的演算——即推理規則，這就是所謂的形式系統。1879年，弗雷格出版了他的小冊子《概念文字》，副標題就是“一種模仿算術語言的純思維的形式語言”，其中完善地發展了一階邏輯系統（通常記作FOL）。FOL揭示了，人的演繹推理過程是連續執行某些簡單的推理規則的過程。我們只需注意規則的執行，而無須理解各種符號的含義。哥德爾1930年的博士論文證明了弗雷格的規則是完備的，這就表明，弗雷格是第一次給出了能夠解釋人的所有演繹推理的形式系統。

弗雷格認為一階邏輯只是朝著他的目標邁進的第一步。在19世紀，人們已經把數學基礎研究歸結到了為自然數理論提供基礎。弗雷格希望為自然數理論提出一種純邏輯的理論，進而證明算術、實數理論、微積分乃至整個數學都可以被看做邏輯的分支，這就是被后人稱之為邏輯主義的觀點。弗雷格關于算術基礎的著作闡述了如何利用他所提出的邏輯發展算術理論。弗雷格的思想是把自然數看成集合的“集合”，例如，3這個數等同于所有恰含有3個元素的集合的“集合”。然而在1902年，正當弗雷格的《算術基礎》第二卷馬上就要出版時，他收到了英國哲學家羅素的信，信中指出了弗雷格的系統是矛盾的，這就是著名的羅素悖論。這對弗雷格來說是一個沉重的打擊，可他不得不接受這個現實，直到1925年去世，他都認為自己的工作毫無結果。更不幸的是，弗雷格的工作當時也不為同事們所認同，所以他從未晉升為正教授。雖然如此，弗雷格的工作還是產生了深遠的影響，他的《概念文字》被后人譽為“也許是自古以來最重要的邏輯學著作”[4]（Ｐ1）。后來的皮亞諾算術系統被認為是算術理論的形式化，集合論公理系統（如Zermelo-Frankel系統）被認為是數學的基礎。這些形式系統使得通過符號演算來實現數值運算和推理成為可能。

四、哥德爾：符號演算與算術運算

在弗雷格看來，邏輯原則總是永真的，因而建立在其上的數學定理也總是永真的，只可惜弗雷格的努力失敗了。后來羅素等人繼承了弗雷格的思想。然而他們毫無顧忌地使用無窮對象，這遭到了以布勞維爾為代表的直覺主義者的批判。同時羅素等人把某些原則（如無窮公理）看成是邏輯原則的思想也不能被多數人所接受。一方面，希爾伯特不能容忍直覺主義者把無窮對象從數學中驅逐出去；另一方面，通過研究羅素和懷特海的《數學原理》，希爾伯特也認為弗雷格和羅素的方法是行不通的。不過， 希爾伯特仍認為建立數學和邏輯的形式系統是十分重要的，但他區分了形式系統的“內部”和“外部”。從內部來看，它就是數學，各種數學計算和推理都可以進行，且每一種數學方法都可以不加限制地應用，但從外部看，它不過是一些公式和符號的操作，這些操作可以在無須考慮意義的情況下進行演算，那么最重要的任務就是證明形式系統是無矛盾的。為了回應直覺主義者的批評，希爾伯特要求，當從外部研究形式系統時，所有的方法必須遵從所謂的“有窮性”，無矛盾性的證明應該是在形式系統外部完成，這樣，就可以“在直覺主義的基礎上把古典數學建立起來”[５]（P168）。

哥德爾的不完全性定理宣告了希爾伯特計劃的破產。哥德爾的編碼在他的不完全性定理的證明中起著舉足輕重的作用，同時也使我們看到，符號演算也可轉化成算術運算。例如，在皮亞諾算術系統中，首先對其中的每一個符號進行編碼，如下表：

五、圖靈機：一個計算模型

實際上，萊布尼茲的夢想可分為兩部分：首先把人類的思維活動還原為符號演算，然后，設計制造強大的計算設備來執行這些演算。萊布尼茲本人曾于1673年訪問倫敦時展示了一個能執行加減乘除運算的機器（之前的帕斯卡的機器只能進行加減運算）。之后，萊布尼茲還描述了一種能解代數方程的機器。然而，在建立“通用語言”的夢想實現之前，奢望實現萊布尼茲夢想的計算機是不現實的。到了1879年，弗雷格第一次給出了包含所有的演繹推理的符號演算系統，從而實現了萊布尼茲所憧憬的通用語言。那么，萊布尼茲夢想的計算設備是否存在呢？用希爾伯特話來說即是：是否存在一個這樣的計算程序，只要給定用一階語言寫出的任意兩個公式A和B，那么通過這個程序總是可以判定，弗雷格的規則是否足以保證能夠從A推出B？這個問題后來被稱做希爾伯特的“判定問題”。

有些數學家憑自己的直覺對希爾伯特“判定問題”作了否定的回答。例如劍橋大學的哈代曾評論說：當然不存在這樣的算法，否則，我們就可以用一套機械的規則來解決一切數學問題，數學家的活動也將壽終正寢了[3]（P164）。特別是在哥德爾證明不完全性定理之后，人們更不相信希爾伯特所設想的算法是存在的。圖靈則思考如何證明它的不存在性。

通過弗雷格的一階邏輯使我們對推理過程有了清晰的認識。推理過程就是從前提出發不斷使用幾個簡單的推理規則，最后得出結論的過程。那么什么是計算過程呢？我們可想象中小學生是如何作算術運算的。只要掌握了個位數的加法，我們就有一套方法來求任意兩個數的和，甚至可以計算出任意多個數的和。進一步，只要我們掌握了個位數的乘法，就可有一套方法計算出任何兩個數的積。實際上，復雜的算術運算被分解成若干步驟，每一步我們進行的都是簡單的工作（如移位、個位數加法或乘法等）。但我們必須清楚每一步該做什么——這就是所謂的心靈狀態，圖靈正是這樣來分析計算過程的，他設計一種現在被稱為圖靈機的裝置。圖靈機包括一條紙帶、一個讀寫頭和一個狀態控制器來指示當前所處的狀態。圖靈機只能執行4個基本操作：左移、右移、讀、寫。我們必須指明當圖靈機處于什么狀態、讀到什么符號時它應該執行怎樣的操作，比如：

當機器處于狀態R， 讀寫頭所在的方格中的符號為a時，把符號b寫入該方格，然后向右移動一個方格，并轉到狀態S。

上面描述的實際是一條指令，程序就是有窮多條指令組成的集合，所謂計算，指的就是圖靈機按照程序的運行過程。簡單地說，稱一個函數是圖靈機可計算的，如果有一個程序來計算這個函數。進而，圖靈利用康托對角線方法證明了不存在希爾伯特所設想的判定程序。不過，圖靈想不到的是，在他研究“判定問題”的過程中，普林斯頓大學的丘奇也得出了類似的結論。丘奇發表在《美國數學雜志》的文章“一個不可解的初等數論問題”提及了兩個可計算性的概念：一個是?姿-可定義函數的概念，一個是一般遞歸函數的概念。這兩個概念實際上是等價的。圖靈很快證明了，?姿-可定義性與他的可計算性也是等價的。1936年，美國邏輯學家坡斯特提出了產生式系統，產生式系統導出的函數恰好就是圖靈可計算函數。因此丘奇和圖靈提出了他們的論題：即直觀的能行可計算函數等都是圖靈機可計算函數（λ-可定義函數）。

圖靈對計算的分析（以及丘奇-圖靈論題）使得我們對計算的本質有了清晰的認識：計算過程就是從輸入的符號開始執行一系列基本操作得到另一個符號串的過程。再來回顧我們對推理的認識：推理就是從前提開始連續使用簡單的推理規則得出結論的過程。不難發現，二者是多么的相似。實際上，使用推理規則的過程都可以通過執行一系列基本操作來完成。而圖靈機所執行的基本操作也可以由推理來完成（見哥德爾的表示定理）。因此，我們有理由認為，推理和計算本質上是一個概念，換句話說，計算可以由推理來完成，推理也可以轉化為計算。

六、新的計算模型研究

通用圖靈機是現代電子計算機的理論模型，圖靈機的基本操作是通過電子線路來實現的。但是，圖靈對計算的分析使我們認識到，不管什么裝置，只要它能執行某些簡單的操作，并且有辦法控制這個裝置使得它在相應的狀態下執行相應的操作，那么這個裝置就可以進行計算。我們也可以稱它是計算機。

1994年11月，美國計算機科學家阿德勒曼(L.Adleman)在美國《科學》上公布DNA計算機的理論，并成功運用DNA計算機解決了一個有向哈密頓路徑問題。在雙螺旋的DNA中，分子鏈是由互補的核苷酸配對組成的，兩條鏈依靠氫鍵結合在一起。由于氫鍵鍵數的限制，DNA的堿基排列配對方式只能是A對T或C對G。這樣，DNA分子鏈就可以用來表示信息。我們可以通過不同的酶對DNA分子鏈進行剪切、連接、復制等簡單操作，DNA計算就是通過酶對DNA分子鏈進行一系列的操作[6]（Ｐ１６）。不過，目前DNA計算機能夠處理的問題，還僅僅是利用分子技術解決的幾個特定問題，通用DNA計算機的理論模型至今還未建立。

引起計算方式重大變革的遠不止DNA計算機。細胞自動機、神經網絡、光學計算機、量子計算機、蛋白質計算機等新型計算機模型層出不窮，隨著科學的不斷發展，還可能會出現更多計算模型。

然而，就可計算性而言，所有這些計算模型都與圖靈機是等價的，也就是說，凡是這些機器能夠計算的，圖靈機也可以計算，反之亦然。那么研究這些新的計算機又有什么意義呢？

首先，所有這些計算模型都是等價的事實說明，由丘奇—圖靈論題所揭示的計算的本質是普適的。其次，從不同的觀點出發，提出的計算模型卻是等價的，這一事實促使不同觀點的相互融合。例如，聯結主義認為，人類的認知是從大量并行的神經元的相互作用中產生的。因此聯結主義不是以符號演算來模擬認知過程，而是通過神經網絡來模擬發生在神經系統中的過程。不過，坡拉克（J.Pollack）于1987年證明了，神經網絡與圖靈機只是形式上的差別，二者是等價的。最后， 尋找新的計算模型是為了制造更加高效的計算機。例如，量子并行操作技術使得量子圖靈機能在同一帶上將大量的輸入信號進行編碼并同時對它們進行演算，從而增強運算能力。

我們與國外學者合作提出量化邏輯的模型理論，這一理論使得我們在量化邏輯推理的計算復雜性研究方面取得了突破。對于度量空間緊集及其算子，我們提出了新的表示方法和新的計算模型，這為分析它們的計算復雜性提供了理論工具[7](P３８５－４０２)。

參考文獻

[1] A. TURING.Collected Works: Mechanical Intelligence[M]. North-Holland， 1992.

[2] W. V. QUINE. The Ways of Paradox and Other Essays[M]. Random House， 1966.

[3] MARTIN DAVIS. Engines of Logic Mathematicians and the Origin of the Computer[M]. W. W Norton Press， 2000.

[4] VAN HEIJENOORT. From Frege to Goedel[M]. Harvard University Press， 1967.

[5] P. MANCOSU. From Brouwer to Hilbert[M]. Oxford University Press， 1998.

[6] P. CLOTE， R. BACKOFEN. Computational Molecular Biology[M]. John Wiley Sons Ltd， 2001.

[7] XISHUN ZHAO， NORBERT MUELLER. Complexity of Operators of Compact Set[Z]. International Conference on Computability and Complexity in Analysis ， Siena， 2007.

[責任編輯 李小娟付洪泉]

“本文中所涉及到的圖表、公式注解等形式請以PDF格式閱讀原文。”