1.1 生物計(jì)算的產(chǎn)生

人類社會(huì)文明與信息處理的計(jì)算工具息息相關(guān)。計(jì)算工具是衡量人類社會(huì)文明程度的重要依據(jù)，也是推動(dòng)人類社會(huì)發(fā)展的主要?jiǎng)恿ΑＨ祟惿鐣?huì)歷經(jīng)石器時(shí)代、鐵器時(shí)代、蒸汽時(shí)代、電氣時(shí)代、信息時(shí)代，當(dāng)前正處于人工智能時(shí)代，計(jì)算工具也由簡(jiǎn)單到復(fù)雜、由低級(jí)到高級(jí)，歷經(jīng)結(jié)繩記事、算籌、算盤(pán)、機(jī)械計(jì)算機(jī)、電子計(jì)算機(jī)等。其中，電子計(jì)算機(jī)也從電子管計(jì)算機(jī)、晶體管計(jì)算機(jī)、個(gè)人計(jì)算機(jī)（Personal Computer，PC）發(fā)展到當(dāng)今的超級(jí)計(jì)算機(jī)，它們?cè)诓煌臍v史時(shí)期為人類社會(huì)的發(fā)展做出了不可磨滅的貢獻(xiàn)。圖1.1所示為人類計(jì)算工具發(fā)展歷程。

圖1.1　人類計(jì)算工具發(fā)展歷程

其實(shí)，以人類神經(jīng)系統(tǒng)為代表的生物神經(jīng)系統(tǒng)一直都是人類社會(huì)信息處理的最好工具，該工具也隨時(shí)代的變遷不斷進(jìn)化，進(jìn)化的結(jié)果是腦神經(jīng)系統(tǒng)愈發(fā)復(fù)雜。圖1.2所示為人類神經(jīng)系統(tǒng)的進(jìn)化過(guò)程示意。人腦這個(gè)信息處理系統(tǒng)，不僅自身在進(jìn)化發(fā)展，而且人類其他信息處理工具均由它設(shè)計(jì)研發(fā)，其中電子計(jì)算機(jī)是當(dāng)今廣泛應(yīng)用的先進(jìn)人造計(jì)算工具。

圖1.2　人類神經(jīng)系統(tǒng)的進(jìn)化過(guò)程示意

電子計(jì)算機(jī)是當(dāng)今人類社會(huì)信息處理的核心工具，人們的生活離不開(kāi)它。但是，電子計(jì)算機(jī)的計(jì)算模型是圖靈機(jī)，圖靈機(jī)是串行計(jì)算模式，故電子計(jì)算機(jī)不能有效求解NP完全問(wèn)題。NP完全問(wèn)題的特點(diǎn)是所需計(jì)算量隨問(wèn)題規(guī)模的增大呈指數(shù)級(jí)增長(zhǎng)。而電子計(jì)算機(jī)的工藝制造技術(shù)已達(dá)極限，這迫使人們開(kāi)始尋求新的計(jì)算模型，以期通過(guò)創(chuàng)造新的計(jì)算工具來(lái)解決阻礙當(dāng)今社會(huì)發(fā)展的NP完全問(wèn)題。

在尋求新計(jì)算模型的過(guò)程中，科學(xué)家從多個(gè)領(lǐng)域展開(kāi)探索，相繼提出了模擬腦信息處理的人工神經(jīng)網(wǎng)絡(luò)、模擬遺傳機(jī)理的進(jìn)化計(jì)算、基于生物大分子特性的生物計(jì)算、基于量子特征的量子計(jì)算、基于光特性的光計(jì)算等。當(dāng)對(duì)這些計(jì)算模型研究到一定程度時(shí)，相應(yīng)的計(jì)算機(jī)就會(huì)被研發(fā)出來(lái)。因此，可形象地稱當(dāng)今非傳統(tǒng)計(jì)算機(jī)的研究處于“戰(zhàn)國(guó)時(shí)期”，生物計(jì)算是“戰(zhàn)國(guó)”中的“一員”。

由于生物計(jì)算主要用于求解NP完全問(wèn)題，故本書(shū)第2章會(huì)較詳細(xì)地介紹圖論基礎(chǔ)、圖靈機(jī)、可計(jì)算性，以及基于圖靈機(jī)的計(jì)算復(fù)雜性理論等。

生物計(jì)算源自理查德·菲利普斯·費(fèi)曼（Richard Phillips Feynman）在1961年提出的研制亞微尺度計(jì)算機(jī)的構(gòu)想[1]。1973年，查爾斯·H.貝內(nèi)特（Charles H. Bennett）提出了一種用酶來(lái)催化的圖靈機(jī)[2]；20世紀(jì)80年代，以蛋白質(zhì)為信息處理數(shù)據(jù)的二態(tài)分子計(jì)算模型被提出，稱為蛋白質(zhì)計(jì)算模型。蛋白質(zhì)計(jì)算模型實(shí)際上是受電子計(jì)算機(jī)的影響，希望用分子產(chǎn)生可控的“二態(tài)”來(lái)模擬所謂的“0,1”目標(biāo)。關(guān)于蛋白質(zhì)計(jì)算的具體內(nèi)容將在第12章介紹。

1994年，倫納德·阿德曼（Leonard Adleman）建立了一種枚舉DNA計(jì)算模型，用于求解7個(gè)頂點(diǎn)有向圖的哈密頓路徑（Hamilton Path）問(wèn)題，該模型的基本原理是以DNA分子為“數(shù)據(jù)”，以生物酶與聚合酶鏈反應(yīng)（Polymerase Chain Reaction，PCR）等為“算子”，獲得問(wèn)題的解[3]，詳述見(jiàn)第6章。DNA計(jì)算模型產(chǎn)生的另一個(gè)重要背景是人類基因測(cè)序計(jì)劃這項(xiàng)巨大工程的實(shí)施。人類基因測(cè)序計(jì)劃促使基因工程、分子生物學(xué)理論、生化操作技術(shù)（尤其是DNA測(cè)序技術(shù)）快速發(fā)展，為DNA計(jì)算的產(chǎn)生、實(shí)現(xiàn)與發(fā)展提供了豐沃的“土壤”，也為DNA計(jì)算機(jī)的研發(fā)奠定了基礎(chǔ)。

作者在此領(lǐng)域的一些早期綜述文章見(jiàn)文獻(xiàn)[4-8]，感興趣的讀者可自行查閱。在DNA計(jì)算的研究過(guò)程中，作者發(fā)現(xiàn)了一種全并行計(jì)算模型——探針機(jī)[9]，相關(guān)理論及應(yīng)用將在第9章給出。