計算機用來作識別機的時候,往往一點不通人情。比如我們見到一個好久未見的熟人,他可能比以前胖些或者瘦些,不管怎樣,我們仍舊能認識他。計算機可不是這樣,它隻能把這人現在的身長、體重、胖瘦等,與以前儲存的資料作比較,稍有差別,就會作出“不認識”的判斷。
計算機有個力求精確的習慣,要使它模仿人腦的功能進行一些識別和分類,倒希望它有一定程度的模糊。這就用得上模糊數學了。
模糊數學是1965年創立的。現已發展成模糊集合、模糊代數、模糊拓撲、模糊邏輯、模糊規劃等學科。隨著計算機的發展,應用也越來越廣。模糊數學處理的是模糊的東西,可模糊數學本身並不模糊。我們接觸和使用電子計算機的機會越來越多。大家都很關心的是:將來能設計出像人腦一樣的電子計算機嗎?不少科學家是抱樂觀態度的。他們認為,可以設計出一種能用來設計的較複雜的計算機,而較複雜的計算機,又能設計出更複雜的計算機。這樣下去,最後設計出像人腦那樣的計算機是可能的。正因為這樣,也有人擔心頭腦發達的機器人,將來會不會對它的主人采取不禮貌的行為。許多科學家是不相信這點的。
對策論的運用———田忌賽馬齊王與大將軍田忌商議賽馬。他們約定:雙方各出上、中、下三種等級的馬各1匹。每次舉行三場比賽,輸者每輸一場就要付給對方1000兩黃金。由於齊王的馬比田忌同等級的馬匹都要稍勝一籌,而在每一比賽中,雙方都用同等級的馬參加對抗,結果齊王連勝3場,得到了3000兩黃金。
沒過多久,齊王又邀請田忌參加賽馬。田忌感到左右為難,一方麵齊王旨意不好違抗,另一方麵再次參賽又必輸無疑。田忌帳下的軍師孫臏,是一位很有才華的軍事家。他替田忌出了一個主意:用自己的下等馬去和齊王的上等馬比賽;用自己的上等馬去和齊王的中等馬比賽;用自己的中等馬去和齊王的下等馬比賽。比賽開始,齊王的第一匹馬遙遙領先。齊王見對方的馬匹竟如此不堪一擊,高興不已。不料好景不長,在第二、第三場比賽中,田忌的賽馬都取得了勝利。齊王反而輸給田忌1000兩黃金。可笑的是,齊王輸了錢還弄不清自己是怎麼輸的呢。
實際上,齊王出馬的等級和順序總共有六種:(上、中、下)(上、下、中)(中、上、下)(中、下、上)(下、中、上)(下、上、中)。田忌的對策也同樣有這六種。這樣,搭配起來共有36種對抗格局。齊王贏3000金的格局共有6種,贏1000的格局有24種,隻有6種才會輸1000。從總數來看,齊王取勝的機會有6+2436=3036=56,輸的機會隻有636=16。
那麼,田忌是如何取勝的呢?原來孫臏摸清了齊王的對策,他認定齊王上一次贏了比賽之後,便不會輕易改變出馬順序,仍然按(上、中、下)的次序出馬參賽。於是,孫臏就采取了相應的對策,根據田忌的馬比齊王次一等級的馬稍快一些的優勢,放棄一場而抓住另兩場的機會,取得了最後的勝利。孫臏的策略之所以能成功,就在於他正確估計了對方的策略。
田忌賽馬雖然是戰國時期的曆史故事,但它體現了新興的數學分支———對策論的思想。
計算機代碼中的數學問題在數學曆史中,存在著許多成對的分支。它們的相對重要性時而興盛,時而衰退,例如像算術與幾何學的關係或者純數學與應用數學之間的關係。另外一對動態對立物可以在算法與分析數學中看到。後者所研究的是基礎結構和“完美的定理”;與此相應,前者的目標是達到實際解所需要的過程。例如,我們已經看到在各種數製中求2的平方根這樣的無理數的各種算法。研究哪一個過程更有效,換言之,用最少的步驟達到所需的精確度,是算法的一項主要研究項目。
術語“算法”本來是指用阿拉伯數字進行計算,以區別在算盤上所進行的計算。由於算盤的使用在歐洲的衰退,同時隨著計算量變得越來越大,對於機械計算器的需求也越來越強烈。17世紀,帕斯卡、笛卡兒、萊布尼茲都夢想著可以對所有數學問題進行編碼,而且可以機械地生成求解方法的通用語言。這些人本身也製造了各種機械的計算器。萊布尼茲設計的通用計算法已經超越了微積分的範疇,包括了可以判定倫理及法律問題的形式規則。任何有效的算法都可以通過使用計算器來增強計算能力。但是直到20世紀,軟件和硬件才結合到了一起。
巴貝奇(CharlesBabbage,1791—1871)於1819年設計了“差分機”,並於1822年製造出可動原型。他希望這台機器能夠提高乘法速度和改進對數表等數字表的精確度。英國政府出資讚助製造一台全功能差分機,使之有能力計算出保險精算、行政管理及科學研究等所需的高精度的數據表。但是,到了1834年,巴貝奇的這項方案大大超出了預算,而且進程也落後於預期的日期。雖然巴貝奇的智能以及資金約定額沒有問題,但是政府延緩了進一步的資助。從那時起,巴貝奇把注意力轉移到了“分析機”的設計上來。實際上,這就是現代計算機的前身。其最主要的特征是把存儲器和運算器分離開來:存儲器在計算過程中存放數字,而運算器進行算術運算。通過在穿孔卡片上編碼進行輸入和輸出操作,而控製器控製著程序。他也曾設想將結果直接輸出到打印機上,這樣分析機就能像蒸汽機那樣自動運算了,但是分析機沒有被實際製造出來。到了1842年,政府停止了對差分機的資助。巴貝奇對英國科學界的懷疑得到進一步的證實。在大學學習期間,巴貝奇和他人聯合創建了分析協會,其主要目的是使劍橋的數學教學達到歐洲大陸的水平。1830年,他寫了一篇抨擊英國科學現狀的文章,強烈指責了皇家科學院封閉的思想狀況,這導致了不列顛科學促進協會的建立。不幸的是,巴貝奇計算機的高昂造價使他的計算機沉睡了將近100年。
正如巴貝奇所預見的那樣,由於提高計算速度的需要,計算機迅速地發展了起來。1940年,在IBM讚助下,哈佛大學研製成功了第一台自動計算器。第一台電子可編程的計算機“巨人”
(Colossus)於1943年研製成功。它是圖靈和馮·諾依曼在英國外交部做密碼破譯工作時合作的結晶。然而,對未來的計算機體係結構產生影響的是同一時期在賓州大學研製的ENIAC(ElectronicNumeratorIntegratorAndComputer)。馮·諾依曼希望ENIAC(最初是設計成用來計算彈道學的表格的機器)能夠實現曼哈頓計劃所要求的某些計算。但結果他卻發現他自己是在設計一種新型計算機。這種新型存儲程序計算機叫做EDVAC(ElectronicDiscreteVariableAutomaticComputer)。這一新型計算機有5個主要的組成部分:輸入、輸出、控製單元、存儲單元和運算單元。這種計算機之所以叫“存儲程序計算機”,是因為程序同數據一起存儲在機器中的,同時,控製單元執行指令序列。這一類型的計算機始建於1949年的英國,叫做EDSAC(ElectronicDelayStoreAutomaticCalculator)。後來,美國和英國都生產了這樣的計算機。到了20世紀60年代,存儲程序計算機開始普及。半導體元件的發明取代了陰極射線管,使得計算機的速度和可靠性得到了提高。盡管這些設計與巴貝奇的設計相似,但是這些計算機的研究是在完全忽視了巴貝奇的早期工作的情況下完成的。
正如我們所了解的那樣,計算機的發明是在實際需要的背景下產生的,無論是在商業、行政部門、密碼學還是在數學物理中的方程求解中都存在著這樣的需求。存儲程序計算機已將硬件和軟件分開。為了執行適當的計算而做的編程和算法研究不是出於實際需要,而是出於邏輯學家們對形式體係的探索。
普通算術就是形式體係的一個常見例子。它有一個明確的符號集合和為了對問題求解操作這些符號的過程。除了參照形式體係的法則外,這些符號本身沒有意義。例如,如果要驗證算式ABmBAeBEB是可滿足的,可以使用各種方法求得A,B,E,m和e的具體實例。也許把ABmBAeBEB看成乘法等式12×21=252更簡單明了(A←1,B←2,m←×,e←=,E←5),但是,ABmBAeBEB表明具體符號並不重要,重要的是在給定公理體係下能夠證明命題為真,在此例中就存在這樣一個具體的算式。實際上,我們不僅可以用字母表示函數,甚至可以用數字來代表算子而不是表示具體的量。這是特定用途計算機到通用計算機的轉換中的一個至關重要的因素。在現代計算機中,任何一個指令,例如在顯示器上特定位置顯示一個紅點的命令,實質上就是一串數字。事實上,一個完整程序一旦被編碼成二進製,那麼本質上它就是一個(非常大的)數。由於計算機在速度和功能方麵突飛猛進的發展,計算機這一單純的編碼方式往往被忽視。
哥德爾(KurtGodel,1906—1978)於1931年發表的《〈數學原理〉及有關係統中的形式不可判定命題》中給出了為形式係統中的每個可表達的命題賦予一個唯一的數的方法。這樣,每個命題真值得證明都可以表達為唯一的一串自然數。並擴展到已知一串這樣的符號,就有可能決定它是否有意義。在這篇論文中,有兩個經典結論。其中第一個是不完全性定理,即像整數算術一樣的基本公理係統均含有在該係統下不可判定的命題。這與語言學中的兩難問題“這個句子是錯誤的”有點類似。不可判定命題的存在,證明了按照羅素和懷特海的設想尋求數學公理化的想法是行不通的。同時,哥德爾也粉碎了希爾伯特的夢想:希爾伯特試圖建立一個完備且自相容的算術係統,即一個不存在內部矛盾的算術係統。哥德爾的第二個結論是:如果一個係統是相容的,則在該係統的範疇內不能證明此係統的相容性。簡而言之,算術是不完全的。這樣的打擊足以使數學家們放棄尋求一個普遍的數學,而致力於從不同公理形式如何產生不同係統的研究。尋求數學語言的目的是使我們能夠回答疑問,因此在此之前,討論著重於判斷數學命題真偽的過程上。現在,數學家們更加關心的是可計算性而不是可判定性。數學家們從可判定性的研究步入了可計算性的研究領域。
在把目光集中於算法的同時,函數概念的推廣也受到關注。
在最一般的意義下,函數f是數學對象間的任意關聯。一個函數可計算是指,存在一個對於f定義域中的每個x都能求出f(x)的算法。隻有在19世紀末,人們構造出病態函數時,才發現可能存在不可計算的函數。因此,研究轉向了計算算法。判定一個給定算法是否是計算所需函數的算法相對來說比較容易的。但是,對於一個函數,當我們要證明不存在計算它的算法時,則需要精確定義什麼是算法。在定義什麼是算法時,哥德爾所給出的遞歸函數概念,起到了非常重要的作用。所謂遞歸函數,是指從若幹個基本函數出發,按給定規則通過有限步操作而得到的函數。可判定性與此相似:對於命題y=f(x),當在一個形式體係下,存在這一命題真偽的證明時,它在這一形式體係下是可判定的。希爾伯特的第10問題是關於丟番圖方程求解算法的問題。
正是受這一問題啟發,人們開始了可計算性的研究。1936年,普林斯頓大學的丘奇和劍橋大學的圖靈各自獨立地發表了可計算性的概念,而圖靈進一步指出兩個概念本質上是等價的。圖靈的算法定義基於計算的機器模型,丘奇立即把該模型命名為圖靈機。
他們的研究否定了萬能算法的存在,即不存在判定所有命題真偽的算法。這些結果以及哥德爾的結果成功地粉碎了計算機有朝一日能夠判定出所有數學命題真偽的夢想。然而對算法的關注引發了軟件革命,這一革命宣告了計算數學這一新領域的誕生。計算數學不斷地向老問題挑戰,例如太陽係的穩定性等問題,同時人們把注意力轉移到生物係統和生命自身的複雜動力係統。
戰爭博弈論人們總是喜歡玩博弈,無論老幼都為之瘋狂。大部分博弈既需要技巧又需要運氣。經曆了命運變遷之後,一個真正的博弈玩家能夠在多項連續的博弈中保持冷靜、思慮周全。然而,有一些博弈卻不能僅憑運氣來玩,在這裏,既沒有骰子可擲,又沒有平局的幸運,這些博弈完全要依賴於策略才能取勝。關於這樣博弈的研究,就是對策論的研究課題。還有一些博弈簡直就是生與死的較量。在模擬戰爭中,由於戰術失誤的代價較低,因此,軍事戰略家們總是利用軍事策略博弈來改進他們的戰術設計技術。把國際象棋和圍棋看成是理想的戰爭博弈,也許並非偶然。把博弈理論首次實際運用於分析一種新型戰爭———未來有可能爆發的最後一次大戰也並不奇怪。