邏輯與計算

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

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

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

二、布爾：邏輯推理即代數(shù)運算

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

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

三、弗雷格：一個真正的符號演算系統(tǒng)

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

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

四、哥德爾：符號演算與算術(shù)運算

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

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

五、圖靈機(jī)：一個計算模型

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

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

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

當(dāng)機(jī)器處于狀態(tài)R， 讀寫頭所在的方格中的符號為a時，把符號b寫入該方格，然后向右移動一個方格，并轉(zhuǎn)到狀態(tài)S。

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

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

六、新的計算模型研究

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

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

引起計算方式重大變革的遠(yuǎn)不止DNA計算機(jī)。細(xì)胞自動機(jī)、神經(jīng)網(wǎng)絡(luò)、光學(xué)計算機(jī)、量子計算機(jī)、蛋白質(zhì)計算機(jī)等新型計算機(jī)模型層出不窮，隨著科學(xué)的不斷發(fā)展，還可能會出現(xiàn)更多計算模型。

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

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

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

參考文獻(xiàn)

[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.

[責(zé)任編輯 李小娟付洪泉]

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