數學與計算機科學

張澤玲

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

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

圖靈機

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

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

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