weidagang2046的專欄

什么是計(jì)算與計(jì)算的類型

    在大眾的意識(shí)里，計(jì)算首先指的就是數(shù)的加減乘除，其次則為方程的求解、函數(shù)的微分積分等；懂的多一點(diǎn)的人知道，計(jì)算在本質(zhì)上還包括定理的證明推導(dǎo)。可以說(shuō)，“計(jì)算”是一個(gè)無(wú)人不知元人不曉的數(shù)學(xué)概念，但是，真正能夠回答計(jì)算的本質(zhì)是什么的人恐怕不多。事實(shí)上，直到1930年代，由于哥德?tīng)枺↘.Godel，1906-1978）、丘奇(A.Church，1903-1995)、圖靈(A.M.TUI-ing，1912-1954)等數(shù)學(xué)家的工作，人們才弄清楚什么是計(jì)算的本質(zhì)，以及什么是可計(jì)算的、什么是不可計(jì)算的等根本性問(wèn)題。

    抽象地說(shuō)，所謂計(jì)算，就是從一個(gè)符號(hào)串f變換成另一個(gè)符號(hào)串g。比如說(shuō),從符號(hào)串12+3變換成15就是一個(gè)加法計(jì)算。如果符號(hào)串f是，而符號(hào)串g是2x,從f到g的計(jì)算就是微分。定理證明也是如此，令f表示一組公理和推導(dǎo)規(guī)則，令g是一個(gè)定理,那么從f到g的一系列變換就是定理g的證明。從這個(gè)角度看，文字翻譯也是計(jì)算，如f代表一個(gè)英文句子，而g為含意相同的中文句子，那么從f到g就是把英文翻譯成中文。這些變換間有什么共同點(diǎn)？為什么把它們都叫做計(jì)算？因?yàn)樗鼈兌际菑募褐?hào)(串)開始，一步一步地改變符號(hào)(串)，經(jīng)過(guò)有限步驟，最后得到一個(gè)滿足預(yù)先規(guī)定的符號(hào)(串)的變換過(guò)程。

    從類型上講，計(jì)算主要有兩大類：數(shù)值計(jì)算和符號(hào)推導(dǎo)。數(shù)值計(jì)算包括實(shí)數(shù)和函數(shù)的加減乘除、幕運(yùn)算、開方運(yùn)算、方程的求解等。符號(hào)推導(dǎo)包括代數(shù)與各種函數(shù)的恒等式、不等式的證明,幾何命題的證明等。但無(wú)論是數(shù)值計(jì)算還是符號(hào)推導(dǎo),它們?cè)诒举|(zhì)上是等價(jià)的、一致的，即二者是密切關(guān)聯(lián)的，可以相互轉(zhuǎn)化，具有共同的計(jì)算本質(zhì)。隨著數(shù)學(xué)的不斷發(fā)展,還可能出現(xiàn)新的計(jì)算類型。

計(jì)算的實(shí)質(zhì)與E奇－圖靈論點(diǎn)

    為了回答究竟什么是計(jì)算、什么是可計(jì)算性等問(wèn)題，人們采取的是建立計(jì)算模型的方法。從20世紀(jì)30年代到40年代，數(shù)理邏輯學(xué)家相繼提出了四種模型，它們是一般遞歸函數(shù)、λ可計(jì)算函數(shù)、圖靈機(jī)和波斯特(E.L.Post，1897-1954)系統(tǒng)。這種種模型完全從不同的角度探究計(jì)算過(guò)程或證明過(guò)程，表面上看區(qū)別很大，但事實(shí)上卻是等價(jià)的，即它們完全具有一樣的計(jì)算能力D在這一事實(shí)基礎(chǔ)上，最終形成了如今著名的丘奇-圖靈論點(diǎn)：凡是可計(jì)算的函數(shù)都是一般遞歸函數(shù)(或是圖靈機(jī)可計(jì)算函數(shù)等)。這就確立了計(jì)算與可計(jì)算性的數(shù)學(xué)含義。下面主要對(duì)一般遞歸函數(shù)作一簡(jiǎn)要介紹。

    哥德?tīng)柺紫仍?931年提出了原始遞歸函數(shù)的概念。所謂原始遞歸函數(shù),就是由初始函數(shù)出發(fā)，經(jīng)過(guò)有限次的使用代人與原始遞歸式而做出的函數(shù)。這里所說(shuō)的初始函數(shù)是指下列三種函數(shù)：

    (1) 零函數(shù)0(x)=0(函數(shù)值恒為零)；

    (2) 射影函數(shù)(x1,x2,…,xn)=xi(1≤i≤n)(函數(shù)的值與第i個(gè)自變?cè)闹迪嗤?；

    后繼函數(shù)S(x)=x+1(其值為x的直接后繼數(shù))。

    代人與原始遞歸式是構(gòu)造新函數(shù)的算子。

    代人(又名疊置、迭置)，它是最簡(jiǎn)單又最重要的算子,其一般形式是:由一個(gè)m元函數(shù)f與m個(gè)n元函數(shù)g1，g2，…，gm造成新函數(shù)f(g1(x1,x2,…,xn),g2(x1,x2,…,xn),…,gm(x1,x2,…,xn))。

    原始遞歸式，其一般形式為

    特殊地為

其特點(diǎn)是，不能由g,h兩已知函數(shù)直接計(jì)算新函數(shù)的一般值f(u,x),而只能依次計(jì)算f(u,0)，f(u,1)，f(u,2)，…；但只要依次計(jì)算，必能把任何一個(gè)f(u,x)，對(duì)值都算出來(lái)。換句話說(shuō)，只要g,h有定義且可計(jì)算，則新函數(shù)f也有定義且可計(jì)算。

    根據(jù)埃爾布朗(J.Herbrand，1908-1931)一封信的暗示，哥德?tīng)栍?934年引進(jìn)了一般遞歸函數(shù)的概念。后經(jīng)克林(S.C.Kleene，1909-1994)的改進(jìn)與闡明，便出現(xiàn)了現(xiàn)在普遍采用的定義。所謂一般遞歸函數(shù)，就是由初始函數(shù)出發(fā)，經(jīng)過(guò)有限次使用代人、原始遞歸式和μ算子而做成的有定義的函數(shù)。 這里的μ算子就是造逆函數(shù)的算子或求根算子。

    如此定義的一般遞歸函數(shù)比原始遞歸函數(shù)更廣，這是沒(méi)有任何疑問(wèn)的。但是，人們還是可以問(wèn)：這樣定義的函數(shù)是否已經(jīng)包括了所有直觀上的可計(jì)算函數(shù)？如果還有更廣的可計(jì)算函數(shù)又該怎樣定義？在受到這類問(wèn)題困惑的同時(shí)，丘奇、克林又提出了一類可計(jì)算函數(shù)，叫做λ可計(jì)算函數(shù)。但事隔不久，丘奇和克林便分別證明了λ可計(jì)算函數(shù)正好就是一般遞歸函數(shù)，即這兩類可計(jì)算函數(shù)是等價(jià)的、一致的。在這一有力的證據(jù)基礎(chǔ)上，丘奇于1936年公開發(fā)表了他早在兩年前就孕育過(guò)的一個(gè)論點(diǎn)，即著名的丘奇論點(diǎn)：每個(gè)能行地可計(jì)算的函數(shù)都是一般遞歸函數(shù)。

    與此同時(shí)，圖靈定義了另一類可計(jì)算函數(shù)，叫做圖靈機(jī)可計(jì)算性函數(shù),并且提出了著名的圖靈論點(diǎn)：能行可計(jì)算函數(shù)都是用圖靈機(jī)可計(jì)算的函數(shù)。圖靈機(jī)是圖靈提出的一種計(jì)算模型，或一臺(tái)理論計(jì)算機(jī)口它可以說(shuō)是對(duì)人類計(jì)算與機(jī)器計(jì)算的最一般、最高度的抽象。一年后，圖靈進(jìn)一步證明了圖靈機(jī)可計(jì)算函數(shù)與λ可定義函數(shù)是一致的，當(dāng)然也就和一般遞歸函數(shù)一致、等價(jià)。于是，表面上不同的三類可計(jì)算函數(shù)在本質(zhì)上就是一類。這樣一來(lái)，丘奇論點(diǎn)和圖靈論點(diǎn)也就是一回事了，現(xiàn)將它們合稱為丘奇-圖靈論點(diǎn)，即直觀的能行可計(jì)算函數(shù)等同于一般遞歸函數(shù)、可λ定義函數(shù)和圖靈機(jī)可計(jì)算函數(shù)。

    丘奇－圖靈論點(diǎn)的提出，標(biāo)志著人類對(duì)可計(jì)算函數(shù)與計(jì)算本質(zhì)的認(rèn)識(shí)達(dá)到了空前的高度，它是數(shù)學(xué)史上一塊奪目的里程碑。

    一般遞歸函數(shù)比較抽象，為此給出一種較為直觀的解釋。大家知道，凡能夠計(jì)算的，即使是“心算”，總可以把其計(jì)算過(guò)程記錄下來(lái)，而且是逐個(gè)步驟逐個(gè)步驟地記錄下來(lái)。所謂計(jì)算過(guò)程，是指從初始符號(hào)或已知符號(hào)開始，一步一步地改變(變換)符號(hào)，最后得到一個(gè)滿足預(yù)先規(guī)定的條件的符號(hào)，并從該符號(hào)按照一定方法得到所求結(jié)果，即所求函數(shù)的值的全過(guò)程。可如此計(jì)算的函數(shù)，一般稱為可以在有限步驟內(nèi)計(jì)算的函數(shù)。現(xiàn)已證明：凡是可以從某些初始符號(hào)開始，而在有限步驟內(nèi)計(jì)算的函數(shù)都是遞歸函數(shù)。由此可以看到，“能夠記錄下來(lái)”便符合了可計(jì)算性或遞歸性的本質(zhì)要求。一般遞歸函數(shù)的實(shí)質(zhì)也由此顯得十分直觀易懂。

    丘奇－圖靈論點(diǎn)的提出與確認(rèn)，在數(shù)學(xué)和計(jì)算機(jī)科學(xué)上具有重大的理論和現(xiàn)實(shí)意義。正如我國(guó)數(shù)理邏輯專家莫紹揆教授所言，有了這個(gè)論點(diǎn)以后，就可以斷定某些問(wèn)題是不能能行地解決或不能能行地判定的。對(duì)于計(jì)算機(jī)科學(xué)，丘奇-圖靈論點(diǎn)的意義在于它明確刻畫了計(jì)算機(jī)的本質(zhì)或計(jì)算機(jī)的計(jì)算能力，確定了計(jì)算機(jī)只能計(jì)算一般遞歸函數(shù)，對(duì)于一般遞歸函數(shù)之外的函數(shù)，計(jì)算機(jī)是無(wú)法計(jì)算的。

DNA計(jì)算:新型計(jì)算方式的出現(xiàn)

    1994年11月，美國(guó)計(jì)算機(jī)科學(xué)家阿德勒曼(L.Adleman)在美國(guó)《科學(xué)》上公布DNA計(jì)算機(jī)的理論，并成功運(yùn)用DNA計(jì)算機(jī)解決了一個(gè)有向哈密頓路徑問(wèn)題。 DNA計(jì)算機(jī)的提出，產(chǎn)生于這樣一個(gè)發(fā)現(xiàn)，即生物與數(shù)學(xué)的相似性：(1)生物體異常復(fù)雜的結(jié)構(gòu)是對(duì)由DNA序列表示的初始信息執(zhí)行簡(jiǎn)單操作(復(fù)制、剪接)的結(jié)果；(2)可計(jì)算函數(shù)f(ω)的結(jié)果可以通過(guò)在ω上執(zhí)行一系列基本的簡(jiǎn)單函數(shù)而獲得。

    阿德勒曼不僅意識(shí)到這兩個(gè)過(guò)程的相似性，而且意識(shí)到可以利用生物過(guò)程來(lái)模擬數(shù)學(xué)過(guò)程。更確切地說(shuō)是，DNA串可用于表示信息，酶可用于模擬簡(jiǎn)單的計(jì)算。這是因?yàn)椋菏紫龋珼NA是由稱作核昔酸的一些單元組成，這些核昔酸隨著附在其上的化學(xué)組或基的不同而不同。共有四種基：腺嘌呤、鳥嘌呤、胞嘧啶和胸腺嘧啶，分別用A、G、C、T表示。單鏈DNA可以看作是由符號(hào)A、G、C、T組成的字符串。從數(shù)學(xué)上講，這意味著可以用一個(gè)含有四個(gè)字符的字符集∑ =A、G、C、T來(lái)為信息編碼(電子計(jì)算機(jī)僅使用0和1這兩個(gè)數(shù)字)。其次，DNA序列上的一些簡(jiǎn)單操作需要酶的協(xié)助，不同的酶發(fā)揮不同的作用。起作用的有四種酶：限制性內(nèi)切酶，主要功能是切開包含限制性位點(diǎn)的雙鏈DNA；DNA連接酶,它主要是把一個(gè)DNA鏈的端點(diǎn)同另一個(gè)鏈連接在一起；DNA聚合酶,它的功能包括DNA的復(fù)制與促進(jìn)DNA的合成；外切酶，它可以有選擇地破壞雙鏈或單鏈DNA分子。正是基于這四種酶的協(xié)作實(shí)現(xiàn)了DNA計(jì)算。

    不過(guò)，目前DNA計(jì)算機(jī)能夠處理的問(wèn)題，還僅僅是利用分子技術(shù)解決的幾個(gè)特定問(wèn)題，屬一次性實(shí)驗(yàn)。DNA計(jì)算機(jī)還沒(méi)有一個(gè)固定的程式。由于問(wèn)題的多樣性，導(dǎo)致所采用的分子生物學(xué)技術(shù)的多樣性，具體問(wèn)題需要設(shè)計(jì)具體的實(shí)驗(yàn)方案口這便引出了兩個(gè)根本性問(wèn)題(也是阿德勒曼最早意識(shí)到的)：(1)DNA計(jì)算機(jī)可以解決哪些問(wèn)題確切地說(shuō)，DNA計(jì)算機(jī)是完備的嗎？即通過(guò)操縱DNA能完成所有的(圖靈機(jī))可計(jì)算函數(shù)嗎？(2)是否可設(shè)計(jì)出可編程序的DNA計(jì)算機(jī)？即是否存在類似于電子計(jì)算機(jī)的通用計(jì)算模型——圖靈機(jī)——那樣的通用DNA系統(tǒng)(模型)？目前，人們正處在對(duì)這兩個(gè)根本性問(wèn)題的研究過(guò)程之中口在筆者看來(lái)，這就類似于在電子計(jì)算機(jī)誕生之前的20世紀(jì)三四十年代理論計(jì)算機(jī)的研究階段。如今，已經(jīng)提出了多種DNA計(jì)算模型，但各有千秋，公認(rèn)的DNA計(jì)算機(jī)的“圖靈機(jī)”還沒(méi)有誕生。相對(duì)而言，一種被稱為“剪接系統(tǒng)”的DNA計(jì)算機(jī)模型較為成功。

    有了“剪接系統(tǒng)”這個(gè)DNA計(jì)算機(jī)的數(shù)學(xué)模型后，便可以來(lái)回答前面提出的DNA計(jì)算的完備性與通用性問(wèn)題。前面講過(guò)，丘奇-圖靈論點(diǎn)深刻地刻畫了任何實(shí)際計(jì)算機(jī)的計(jì)算能力——任何可計(jì)算函數(shù)都是可由圖靈機(jī)計(jì)算的函數(shù)(一般遞歸函數(shù))。現(xiàn)已證明：剪接系統(tǒng)是計(jì)算完備的，即任何可計(jì)算函數(shù)都可用剪接系統(tǒng)來(lái)計(jì)算D反之亦然。這就回答了DNA計(jì)算機(jī)可以解決哪些問(wèn)題——全部圖靈機(jī)可計(jì)算問(wèn)題。至于是否存在基于剪接的可編程計(jì)算機(jī)，也有了肯定的答案：對(duì)每個(gè)給定的字符集T，都存在一個(gè)剪接系統(tǒng)，其公理集和規(guī)則集都是有限的，而且對(duì)于以T為終結(jié)字符集的一類系統(tǒng)是通用的。這就是說(shuō)，理論上存在一個(gè)基于剪接操作的通用可編程的DNA計(jì)算機(jī)。這些計(jì)算機(jī)使用的生物操作只有合成、剪接(切割-連接)和抽取。

    DNA計(jì)算機(jī)理論的出現(xiàn)意味著計(jì)算方式的重大變革。當(dāng)然，引起計(jì)算方式重大變革的遠(yuǎn)不止DNA計(jì)算機(jī)，光學(xué)計(jì)算機(jī)、量子計(jì)算機(jī)、蛋白質(zhì)計(jì)算機(jī)等新型計(jì)算機(jī)模型層出不窮，它們使原有的計(jì)算方式發(fā)生了前所未有的變化。

計(jì)算方式及其演變

    簡(jiǎn)單地講，所謂計(jì)算方式就是符號(hào)變換的操作方式，尤其指最基本的動(dòng)作方式。廣義地講，還應(yīng)包括符號(hào)的載體或符號(hào)的外在表現(xiàn)形式，亦即信息的表征或表達(dá)。比如，中國(guó)古代的籌算，就是用一組竹棍表征的計(jì)算方式，后來(lái)的珠算則是用算盤或算珠表征的計(jì)算方式，再后來(lái)的筆算又是一種用文字符號(hào)表征的計(jì)算方式，這一系列計(jì)算方式的變化，表現(xiàn)出計(jì)算方式的多樣性與不斷進(jìn)化的趨勢(shì)。相對(duì)于后來(lái)出現(xiàn)的機(jī)器計(jì)算方式，上述各種計(jì)算方式均可歸結(jié)為“手工計(jì)算方式”，其特點(diǎn)是用手工操作符號(hào)，實(shí)施符號(hào)的變換。

    不過(guò)，真正具有革命性的計(jì)算方式，還是隨著電子計(jì)算機(jī)的產(chǎn)生才出現(xiàn)的。機(jī)器計(jì)算的歷史可以追溯到1641年，當(dāng)年18歲的法國(guó)數(shù)學(xué)家帕斯卡從機(jī)械時(shí)鐘得到啟示：齒輪也能計(jì)數(shù)，于是成功地制作了一臺(tái)齒輪傳動(dòng)的八位加法計(jì)算機(jī)口這使人類計(jì)算方式、計(jì)算技術(shù)進(jìn)入了一個(gè)新的階段。后來(lái)經(jīng)過(guò)人們數(shù)百年的艱辛努力，終于在1945年成功研制出了世界上第一臺(tái)電子計(jì)算機(jī)。從此，人類進(jìn)入了一個(gè)全新的計(jì)算技術(shù)時(shí)代。

    從最早的帕斯卡齒輪機(jī)到今天最先進(jìn)的電子計(jì)算機(jī)，計(jì)算機(jī)已經(jīng)歷了四大發(fā)展時(shí)期。計(jì)算技術(shù)有了長(zhǎng)足的發(fā)展。這時(shí)計(jì)算表現(xiàn)為一種物理性質(zhì)的機(jī)械的操作過(guò)程。符號(hào)不再是用竹棍、算珠、字母表征，而是用齒輪表征，用電流表征，用電壓表征等等。但是，無(wú)論是手工計(jì)算還是機(jī)器計(jì)算，其計(jì)算方式——操作的基本動(dòng)作都是一種物理性質(zhì)的符號(hào)變換(具體是由“加”“減”這種基本動(dòng)作構(gòu)成)。二者的區(qū)別在于：前者是手工的，運(yùn)算速度比較慢；后者則是自動(dòng)的，運(yùn)算速度極快。

    如今出現(xiàn)的DNA計(jì)算無(wú)疑有著更大的本質(zhì)性變化，計(jì)算不再是一種物理性質(zhì)的符號(hào)變換，而是一種化學(xué)性質(zhì)的符號(hào)變換，即不再是物理性質(zhì)的“加”“減”操作，而是化學(xué)性質(zhì)的切割和粘貼、插人和刪除。這種計(jì)算方式將徹底改變計(jì)算機(jī)硬件的性質(zhì)，改變計(jì)算機(jī)基本的運(yùn)作方式，其意義將是極為深遠(yuǎn)的。阿德勒曼在提出DNA計(jì)算機(jī)的時(shí)候就相信，DNA計(jì)算機(jī)所蘊(yùn)涵的理念可使計(jì)算的方式產(chǎn)生進(jìn)化。

    量子計(jì)算機(jī)在理論上的出現(xiàn)，使計(jì)算方式的進(jìn)化又有了新的可能。電子計(jì)算機(jī)的理論模型是經(jīng)典的通用圖靈機(jī)——一種確定型圖靈機(jī)，量子計(jì)算機(jī)的理論模型——量子圖靈機(jī)則是一種概率型圖靈機(jī)。直觀一些說(shuō)，傳統(tǒng)電腦是通過(guò)硅芯片上微型晶體管電位的“開”和“關(guān)”狀態(tài)來(lái)表達(dá)二進(jìn)位制的0和1，從而進(jìn)行信息數(shù)據(jù)的處理和儲(chǔ)存。每個(gè)電位只能處理一個(gè)數(shù)據(jù)，非0即1，許多個(gè)電位依次串連起來(lái)，才能共同完成一次復(fù)雜的運(yùn)算。這種線性計(jì)算方式遵循普通的物理學(xué)原則，具有明顯的局限性。而量子計(jì)算機(jī)的運(yùn)算方式則建立在原子運(yùn)動(dòng)的層面上，突破了分子物理的界限。根據(jù)量子論原理，原子具有在同一時(shí)刻處于兩個(gè)不同位置、又同時(shí)向上下兩個(gè)相反方向旋轉(zhuǎn)的特性，稱為“量子超態(tài)”。而一旦有外力干擾，模糊運(yùn)動(dòng)的原子又可以馬上歸于準(zhǔn)確的定位。這種似是而非的混沌狀態(tài)與人們熟知的常規(guī)世界相矛盾，但如果利用其表達(dá)信息，卻能發(fā)揮出其瞬息之間千變?nèi)f化而又萬(wàn)變不離其宗的神奇功效。因?yàn)楫?dāng)許多個(gè)量子狀態(tài)的原子糾纏在一起時(shí)，它們又因量子位的“疊加性”，可以同時(shí)一起展開“并行計(jì)算”，從而使其具備超高速的運(yùn)算能力。電子線性計(jì)算方式如同萬(wàn)只蝸牛排隊(duì)過(guò)獨(dú)木橋，而量子并行運(yùn)算好比萬(wàn)只飛鳥同時(shí)升上天空。

計(jì)算方式演變的意義

    計(jì)算方式的不斷進(jìn)化有著十分重要的理論意義和現(xiàn)實(shí)意義，筆者認(rèn)為至少表明以下兩方面。其一，計(jì)算方式是一種歷史的結(jié)果，而非計(jì)算本性的邏輯必然。加拿大的卡里(L.Kari)指出：“DNA計(jì)算是考察計(jì)算問(wèn)題的一種全新方式。或許這正是大自然做數(shù)學(xué)的方法：不是用加和減，而是用切割和粘貼、用插入和刪除。正如用十進(jìn)制計(jì)數(shù)是因?yàn)槲覀冇惺畟€(gè)手指那樣，或許我們目前計(jì)算中的基本功能僅因?yàn)槿祟悮v史使然。正如人們已經(jīng)采用其他進(jìn)制計(jì)數(shù)一樣，或許現(xiàn)在是考慮其他的計(jì)算方式的時(shí)候了。”筆者以為，這一說(shuō)法是很有啟示性的。確實(shí)，仔細(xì)回顧一下人類計(jì)算方式或計(jì)算技術(shù)的歷史,就不難體會(huì)到計(jì)算方式是一種歷史的結(jié)果，而非計(jì)算本性的邏輯必然。

    也就是說(shuō)，計(jì)算之所以為計(jì)算，在于它具有一種根本的遞歸性，或在于它是一種可一步一步進(jìn)行的符號(hào)串變換操作。至于這種符號(hào)變換的操作方式如何，以及符號(hào)的載體或其外在表現(xiàn)形式如何，都不是本質(zhì)性的東西，它們?cè)皇且环N歷史的結(jié)果，無(wú)不處于一種不斷變革或進(jìn)化的過(guò)程之中。不同表征下的符號(hào)變換有著不同的操作方式，甚至同一種表征下的符號(hào)變換都可以有不同的操作方式：既可以是物理性的方式，也可以是化學(xué)性的方式；即可以是經(jīng)典的方式,也可以是量子的方式；既可以是確定性的方式，也可以是概率性的方式。在此，計(jì)算本質(zhì)的統(tǒng)一性與計(jì)算方式的多樣性得到了深刻的體現(xiàn)。筆者相信，DNA計(jì)算機(jī)、量子計(jì)算機(jī)等的出現(xiàn)已經(jīng)打開了人們暢想未來(lái)計(jì)算方式的思維視窗，隨著科學(xué)技術(shù)的不斷發(fā)展，計(jì)算方式的多樣性還會(huì)有新的表現(xiàn)。

    其二，計(jì)算方式的歷史性、多樣性反觀了計(jì)算本性的邏輯必然性、統(tǒng)一性。由丘奇-圖靈論點(diǎn)所揭示的計(jì)算本質(zhì)是非常普適的，它不僅包括數(shù)值計(jì)算、定理推導(dǎo)等不同形式的計(jì)算，而且包括人腦、電子計(jì)算機(jī)等不同“計(jì)算器”的計(jì)算。大家不要忘了，以丘奇-圖靈論點(diǎn)為基石的可計(jì)算性理論是在電子計(jì)算機(jī)誕生之前的1930年代提出的，即它并非在對(duì)電子計(jì)算機(jī)進(jìn)行總結(jié)與抽象的基礎(chǔ)上提出，但又深刻地刻畫了電子計(jì)算機(jī)的計(jì)算本質(zhì)。如今最先進(jìn)的電子計(jì)算機(jī)在本質(zhì)上就是一臺(tái)圖靈機(jī)，或者凡是計(jì)算機(jī)可計(jì)算的函數(shù)都是一般遞歸函數(shù)。現(xiàn)在人們又進(jìn)一步認(rèn)識(shí)到，目前尚在實(shí)驗(yàn)室階段的DNA計(jì)算機(jī)、量子計(jì)算機(jī)，在本質(zhì)上也是一種圖靈計(jì)算。這說(shuō)明不同形式的計(jì)算、不同“計(jì)算器”的計(jì)算，在計(jì)算本質(zhì)上是一致的，這就是遞歸計(jì)算或圖靈計(jì)算。

轉(zhuǎn)自：http://cfc.nankai.edu.cn/readings/lijie.htm