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

一、萊布尼茲： 推理和計(jì)算都是符號(hào)演算

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

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

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

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

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

布爾的工作表明邏輯可以成為一個(gè)數(shù)學(xué)分支。在弗雷格看來，這是用邏輯來發(fā)展邏輯，產(chǎn)生了循環(huán)。因此，弗雷格認(rèn)為，他的邏輯系統(tǒng)是不能用邏輯來發(fā)展的，而是要采用精確的語法規(guī)則或句法規(guī)則把他的概念文字發(fā)展成一種人工語言，進(jìn)而把邏輯推理表示為機(jī)械的演算——即推理規(guī)則，這就是所謂的形式系統(tǒng)。1879年，弗雷格出版了他的小冊(cè)子《概念文字》，副標(biāo)題就是“一種模仿算術(shù)語言的純思維的形式語言”，其中完善地發(fā)展了一階邏輯系統(tǒng)（通常記作FOL）。FOL揭示了，人的演繹推理過程是連續(xù)執(zhí)行某些簡單的推理規(guī)則的過程。我們只需注意規(guī)則的執(zhí)行，而無須理解各種符號(hào)的含義。哥德爾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ù)理論、微積分乃至整個(gè)數(shù)學(xué)都可以被看做邏輯的分支，這就是被后人稱之為邏輯主義的觀點(diǎn)。弗雷格關(guān)于算術(shù)基礎(chǔ)的著作闡述了如何利用他所提出的邏輯發(fā)展算術(shù)理論。弗雷格的思想是把自然數(shù)看成集合的“集合”，例如，3這個(gè)數(shù)等同于所有恰含有3個(gè)元素的集合的“集合”。然而在1902年，正當(dāng)弗雷格的《算術(shù)基礎(chǔ)》第二卷馬上就要出版時(shí)，他收到了英國哲學(xué)家羅素的信，信中指出了弗雷格的系統(tǒng)是矛盾的，這就是著名的羅素悖論。這對(duì)弗雷格來說是一個(gè)沉重的打擊，可他不得不接受這個(gè)現(xiàn)實(shí)，直到1925年去世，他都認(rèn)為自己的工作毫無結(jié)果。更不幸的是，弗雷格的工作當(dāng)時(shí)也不為同事們所認(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)使得通過符號(hào)演算來實(shí)現(xiàn)數(shù)值運(yùn)算和推理成為可能。

四、哥德爾：符號(hào)演算與算術(shù)運(yùn)算

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

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

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

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

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

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

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

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

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

六、新的計(jì)算模型研究

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

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

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

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

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

我們與國外學(xué)者合作提出量化邏輯的模型理論，這一理論使得我們?cè)诹炕壿嬐评淼挠?jì)算復(fù)雜性研究方面取得了突破。對(duì)于度量空間緊集及其算子，我們提出了新的表示方法和新的計(jì)算模型，這為分析它們的計(jì)算復(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é)任編輯 李小娟付洪泉]

“本文中所涉及到的圖表、公式注解等形式請(qǐng)以PDF格式閱讀原文?！?/p>