weidagang2046的專欄

什么是計算與計算的類型

    在大眾的意識里，計算首先指的就是數的加減乘除，其次則為方程的求解、函數的微分積分等；懂的多一點的人知道，計算在本質上還包括定理的證明推導?？梢哉f，“計算”是一個無人不知元人不曉的數學概念，但是，真正能夠回答計算的本質是什么的人恐怕不多。事實上，直到1930年代，由于哥德爾（K.Godel，1906-1978）、丘奇(A.Church，1903-1995)、圖靈(A.M.TUI-ing，1912-1954)等數學家的工作，人們才弄清楚什么是計算的本質，以及什么是可計算的、什么是不可計算的等根本性問題。

    抽象地說，所謂計算，就是從一個符號串f變換成另一個符號串g。比如說,從符號串12+3變換成15就是一個加法計算。如果符號串f是，而符號串g是2x,從f到g的計算就是微分。定理證明也是如此，令f表示一組公理和推導規則，令g是一個定理,那么從f到g的一系列變換就是定理g的證明。從這個角度看，文字翻譯也是計算，如f代表一個英文句子，而g為含意相同的中文句子，那么從f到g就是把英文翻譯成中文。這些變換間有什么共同點？為什么把它們都叫做計算？因為它們都是從己知符號(串)開始，一步一步地改變符號(串)，經過有限步驟，最后得到一個滿足預先規定的符號(串)的變換過程。

    從類型上講，計算主要有兩大類：數值計算和符號推導。數值計算包括實數和函數的加減乘除、幕運算、開方運算、方程的求解等。符號推導包括代數與各種函數的恒等式、不等式的證明,幾何命題的證明等。但無論是數值計算還是符號推導,它們在本質上是等價的、一致的，即二者是密切關聯的，可以相互轉化，具有共同的計算本質。隨著數學的不斷發展,還可能出現新的計算類型。

計算的實質與E奇－圖靈論點

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

    哥德爾首先在1931年提出了原始遞歸函數的概念。所謂原始遞歸函數,就是由初始函數出發，經過有限次的使用代人與原始遞歸式而做出的函數。這里所說的初始函數是指下列三種函數：

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

    (2) 射影函數(x1,x2,…,xn)=xi(1≤i≤n)(函數的值與第i個自變元的值相同)；

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

    代人與原始遞歸式是構造新函數的算子。

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

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

    特殊地為

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

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

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

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

    丘奇－圖靈論點的提出，標志著人類對可計算函數與計算本質的認識達到了空前的高度，它是數學史上一塊奪目的里程碑。

    一般遞歸函數比較抽象，為此給出一種較為直觀的解釋。大家知道，凡能夠計算的，即使是“心算”，總可以把其計算過程記錄下來，而且是逐個步驟逐個步驟地記錄下來。所謂計算過程，是指從初始符號或已知符號開始，一步一步地改變(變換)符號，最后得到一個滿足預先規定的條件的符號，并從該符號按照一定方法得到所求結果，即所求函數的值的全過程?？扇绱擞嬎愕暮瘮担话惴Q為可以在有限步驟內計算的函數?，F已證明：凡是可以從某些初始符號開始，而在有限步驟內計算的函數都是遞歸函數。由此可以看到，“能夠記錄下來”便符合了可計算性或遞歸性的本質要求。一般遞歸函數的實質也由此顯得十分直觀易懂。

    丘奇－圖靈論點的提出與確認，在數學和計算機科學上具有重大的理論和現實意義。正如我國數理邏輯專家莫紹揆教授所言，有了這個論點以后，就可以斷定某些問題是不能能行地解決或不能能行地判定的。對于計算機科學，丘奇-圖靈論點的意義在于它明確刻畫了計算機的本質或計算機的計算能力，確定了計算機只能計算一般遞歸函數，對于一般遞歸函數之外的函數，計算機是無法計算的。

DNA計算:新型計算方式的出現

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

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

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

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

    DNA計算機理論的出現意味著計算方式的重大變革。當然，引起計算方式重大變革的遠不止DNA計算機，光學計算機、量子計算機、蛋白質計算機等新型計算機模型層出不窮，它們使原有的計算方式發生了前所未有的變化。

計算方式及其演變

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

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

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

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

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

計算方式演變的意義

    計算方式的不斷進化有著十分重要的理論意義和現實意義，筆者認為至少表明以下兩方面。其一，計算方式是一種歷史的結果，而非計算本性的邏輯必然。加拿大的卡里(L.Kari)指出：“DNA計算是考察計算問題的一種全新方式?；蛟S這正是大自然做數學的方法：不是用加和減，而是用切割和粘貼、用插入和刪除。正如用十進制計數是因為我們有十個手指那樣，或許我們目前計算中的基本功能僅因為人類歷史使然。正如人們已經采用其他進制計數一樣，或許現在是考慮其他的計算方式的時候了?！惫P者以為，這一說法是很有啟示性的。確實，仔細回顧一下人類計算方式或計算技術的歷史,就不難體會到計算方式是一種歷史的結果，而非計算本性的邏輯必然。

    也就是說，計算之所以為計算，在于它具有一種根本的遞歸性，或在于它是一種可一步一步進行的符號串變換操作。至于這種符號變換的操作方式如何，以及符號的載體或其外在表現形式如何，都不是本質性的東西，它們元不是一種歷史的結果，無不處于一種不斷變革或進化的過程之中。不同表征下的符號變換有著不同的操作方式，甚至同一種表征下的符號變換都可以有不同的操作方式：既可以是物理性的方式，也可以是化學性的方式；即可以是經典的方式,也可以是量子的方式；既可以是確定性的方式，也可以是概率性的方式。在此，計算本質的統一性與計算方式的多樣性得到了深刻的體現。筆者相信，DNA計算機、量子計算機等的出現已經打開了人們暢想未來計算方式的思維視窗，隨著科學技術的不斷發展，計算方式的多樣性還會有新的表現。

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

轉自：http://cfc.nankai.edu.cn/readings/lijie.htm