數(shù)學(xué)與計算機科學(xué)

張澤玲

計算機中的“計算”二字，已經(jīng)顯而易見地表示出了數(shù)學(xué)與計算機科學(xué)的關(guān)系。但計算機中的數(shù)學(xué)理論，并不只是加減乘除這些算術(shù)這么簡單。比如，計算機的模型基礎(chǔ)就是名為“圖靈機”的自動機。計算機科學(xué)理論中另外一種有趣的自動機模型，則是跟自然界很多生物行為現(xiàn)象相關(guān)的元胞自動機。

嚴格來說，元胞自動機是一種時空離散的局部動力學(xué)模型，它是一種通用性的建模方法，在社會和自然科學(xué)的各個領(lǐng)域幾乎都會見到它。元胞自動機會按照一定的規(guī)則進行演化，比如從一個簡單的起點出發(fā)，利用一組規(guī)則，就能生成一套復(fù)雜無盡的花紋;在生物世界中，當(dāng)設(shè)定好初始狀態(tài)和進化規(guī)則后，單細胞生物便會依據(jù)規(guī)則在離散的時間步上進行演化。

圖靈機

這是英國數(shù)學(xué)家艾倫·圖靈于1936年提出的一種抽象計算模型，其更抽象的意義為一種數(shù)學(xué)邏輯機，可以看作等價于任何有限邏輯數(shù)學(xué)過程的終極強大邏輯機器。這種機器只是一個虛擬的理想設(shè)備，圖靈認為這樣的一臺機器能模擬人類所能進行的任何計算過程。

計算機理論基礎(chǔ)中，判斷一類計算是否能用計算機在有限時間內(nèi)解決，靠的也是數(shù)學(xué)證明。比如著名的旅行銷售員問題，內(nèi)容是求解一個銷售員走遍每個城市的最短總路徑，本質(zhì)上是一個還未解決的數(shù)學(xué)問題。因為雖然目前計算機已經(jīng)有了可以求解這個問題的辦法，但耗時都非常多，數(shù)學(xué)理論則試圖證明，這類問題用計算機是真的有更快的解法，還是確實無法找到更快的方法。（這個問題被簡化為“證明NP=P”，在計算機科學(xué)理論里的地位相當(dāng)于數(shù)學(xué)里的“哥德巴赫猜想”。）

除此之外，不僅僅是數(shù)學(xué)影響著計算機科學(xué)，計算機作為人類強大的幫手，也在影響著數(shù)學(xué)。比如四色定理，就是靠計算機來輔助證明的。