【探索22-1】計算的歷史縱深

分享至

在這一個世紀中,計算有跳躍性的進展,對人類文明產生十分巨大的影響。在人類漫長的歷史裡,計算如何從古代懵懵懂懂的操作經驗,慢慢提升到了解到它的本質,逐漸從數學裡分化出來,有自己研究的目標、方法,作為一個成熟的知識領域。李國偉教授從軟體、硬體雙方的發展來看計算如何從數學逐漸演化出來的歷程,以橫貫東西文明的觀點看其歷史的縱深。

《模仿遊戲》劇照

講者|中研院數學研究所兼任研究員 李國偉
彙整撰文|何艾玲

建構數學知識的兩大方式——論證、計算

數學知識主要是由「論證」與「計算」的方法建構成。人類古文明從兩河流域到埃及,人們發覺某些幾何命題的真確性是無庸置疑的,於是作為推導其他看似複雜命題的起點,並以這種思維發展出公理法的論證方式。

在西元前300年,歐幾里得(Euclid)將過去人們豐碩的思想,統整出縝密的邏輯系統,寫進《幾何原本》(Elements)中。這本著作成為西方知識發展的重要基石,在近代仍然發揮它深遠的影響力,像是史賓諾沙(Baruch de Spinoza)的《倫理學》(Ethica Ordine Geometrico Demonstrata)、牛頓的《自然哲學的數學原理》(Philosophiæ Naturalis Principia Mathematica)、美國《獨立宣言》都是參照《幾何原本》公理法寫成的。

1820年,伽羅瓦(Évariste Galois)發展「群」與「有限體」等概念,用結構性的論證得到多項式可用根式解的充要條件,以更高層次來看待數學的結構,成為數學史上重要的分水嶺,推理論證成為數學的主流。到19、20世紀最具影響力的數學家——希爾伯特(David Hilbert)巧妙深刻的存在性證明,將論證數學帶上高峰,領導整個20世紀數學的發展。然而,這也使得計算方法在漫長的歲月受到貶低。

每種學術方法都各有各個的存在的價值與意義。計算作為建構數學知識的方式儘管在過去被輕視,但在人類文明的發展上佔有一席之地。它的起源遠遠早於論證,本身人類對量的處理就是「計算」。計算可視為由三大要素「算法」、「表徵」、「工具」所組成。

-算法

算法(algorithm)是一組明確的規則,給出一系列操作後,得以解決特定類型的問題。具有限性、清晰性、有效性、輸入輸出的特徵。

《幾何原本》是論證數學的經典著作,但其中也包含了古代最具代表性的算法——輾轉相除法(歐幾里得算法)來求得最大公因數。在中國古代數學裡,也有本質完全一樣的「更相減損法」,最早被記載在西漢問世的《筭數書》中:

「約分術曰:以子除母,母亦除子,子、母數交等者,即約之矣。有曰:約分術曰:可半,半之。可令若干一、若干一。其一術曰:以分子除母,少,以母除子,子、母等,以為法。子、母各如法而成一。不足除者可半,半母亦半子。」

另一本東漢的著作《九章算術》也提到約分術,本質跟前兩者完全一致。

「約分術曰:可半者半之;不可半者,副置分母、子之數,以少減多,更相減損,求其等也。以等數約之。」

這本《九章算術》是中國古代數學最重要的著作。三國時代,魏國數學家劉徽為這本著作注解,他不僅得出圓周率的近似值為3.1416,也用「出入相補術」證明了畢氏定理。雖然劉徽沒有發展出像歐幾里得那套嚴密的邏輯系統,但仍然在他的著作中看見中國數學完整的思想脈絡。古代中國數學常以「問題集」的方式呈現其成果,依序用這五條項目來表達:

  1. 問,很具體的帶著數據的問題。
  2. 答,給出這個問題的數字解。
  3. 術,得出答案的方法,也就是「算法」。
  4. 注,解釋前人算法為何是對的,呈現一套思想脈絡。
  5. 草,在宋朝之後加了演算過程的細節。

-表徵

表徵(representation)就是在計算的過程中有輸入跟輸出,在腦中抽象的概念必須轉化成具體的形象來代表,作為可以讓人彼此溝通的實像。表徵經過漫長歲月的演變漸漸變得抽象、複雜,現在幾乎任何東西都可以透過適當的表徵,一層一層的化為表徵計算最基本對象「數」。再透過數字的編碼(coding),可以針對各式各樣的對象進行計算來解決問題,像是物理學中的問題等等。

●中西文明的合金與輝映——十進位、二進位

中世紀的歐洲因為經歷黑暗時代,科學發展受到宗教的箝制。此外,數學的發展也受到希臘數字系統本身的限制而停滯很長一段時間,一直到斐波那契(Leonardo Fibonacci)在1202年出版了《計算之書》(Liber Abaci),引進十進位制的印度數字系統(123456789)以及0的符號,讓歐洲社會摒棄過去傳統的羅馬數字,對商業、金融、科學發展產生深遠的影響。在這本著作中討論到的算法、算題,其中像是:分數加法、配分比例等與《九章算術》的內容相似。這背後可能暗示著中國知識透過這本著作接枝到歐洲的文明發展。

近代歐洲強盛的文化發展不單單只是靠自己的力量發展起來,在12世紀傳遞與交融的時代中,歐洲本身的文化脈絡與阿拉伯、印度、中國的文化緊密交織成多股合成的繩子,構成新歐洲的十分堅實核心,推動下個時代的科學革命與工業革命。

萊布尼茲自己發展出對於電腦計算十分重要的二進制記數法,博學多聞的他十分景仰中國文化。當時在中國的耶穌會教士白晉(Joachim Bouvet)寄信給萊布尼茲,介紹中國學術思想以及中國史,其中他特別強調《易經》這本著作,認為它是中國科學和哲學的源頭。1701年,萊布尼茨寫信給白晉,詳細介紹了他發明的二進制後,白晉回信給萊布尼茨,附上了「伏羲64卦方位圖」。他的慧眼看出中國古代數學依循的原理就是萊布尼茨提出的二進制,易卦中的陽爻「—」比作二進制中的「1」;把陰爻「--」比作「0」。1703年,萊布尼茨透過《關於二進制算術的說明並附其應用以及據此解釋古代中國伏羲圖的探討》這篇論文向歐洲社會闡明出東西文化思想的輝映。

-工具

工具(tool)是外在的媒介,透過這些工具幫我們處理計算。西元前300年,巴比倫人已經開始使用大理石製的算板;印加人利用結繩(khipu)來計數;古羅馬也曾出現過金屬算盤。中國古代運用算籌來計算,至於中國算盤出現的時間目前還有爭論。一直到明朝中葉1592年,程大位撰的《直指算法統宗》集珠算之大成,使得珠算盤在民間廣為流傳,從此取代了算籌。

一直到近代,隨著機械計算器的問世,西方社會才開始出現計算工具較大的進展。17世紀中葉,帕斯卡(Blaise Pascal)為了減輕父親計算稅率稅款的繁複計算,自己製作出一台可以加減、進位的機械式計算機(若遇到乘除則是使用連加、連減的方法來進行運算)。當帕斯卡的「加法器」論文流傳到萊布尼茲手上,萊布尼茲為帕斯卡的齒輪計算機的設計添增了萊布尼茲輪,可以進行加減乘除的四則運算。然而單靠他的力量無法完全的製造出一台沒有瑕疵的計算機,後來他請鐘錶匠Oilvier幫他製作新型的計算機。雖然萊布尼茲的計算機沒有完全成功,但他仍然被後人推崇為計算機器的先鋒。

分析機織出代數的式樣

巴貝奇(Charles Babbage)得到比前人更高明的想法,他將複雜的數學運算分解成許多步驟,來簡化每一次計算的過程。把機器結構分為兩大部分,分別是「計算」和「儲存」單元,可以將計算過程中的暫時結果儲存在機器中。接著他發想出分析機(analytic engine),透過指令的輸入讓機器自動進行各種運算,避免計算結果受到人為錯誤的影響。甚至可以在機器中進行程式邏輯的處理,條件判斷、迴圈等等。

巴貝奇所提出的革命性構想,控制和邏輯滲入計算工具的演化,作為當代電子計算機的雛型。這個想法也不是憑空迸出來的,這位天才的造就也跟當時的文明發展有密切的相關。分析機中的「計算單元」和「儲存單元」來自於當代工業「工廠」(mill)、「倉庫」(store)。自動化的概念深受當時雅卡爾(Joseph Marie Jacquard)發明的緹花紡織機啟發,借用自動化的紡織機的輸入媒介——打孔卡,作為分析機的輸入工具。

「正如雅卡爾的緹花紡織機提出花朵與樹葉一樣,分析機織出代數的式樣。」

愛達.拜倫(Augusta Ada Byron

●符號邏輯變成了計算機語言

自從亞里斯多得,邏輯學首次最大革新,在1854年,布爾(George Boole)出版了一篇跨時代的著作The Laws of Thought,將邏輯符號化,使邏輯成為數學的一部分,建立了命題邏輯的體系。其中詳細介紹了一種代數化的邏輯系統,後人稱之為布爾代數(Boolean algebra)。在1937年,由仙農(Claude Shannon)闡明如何使用開關來實現邏輯和數學運算,把電路的解釋與布爾代數結合起來,寫在他的碩士論文《繼電器與開關電路的符號分析》(A Symbolic Analysis of Relay and Switching Circuits)中,奠定了數位電路的理論基礎。

然而命題邏輯不足以表達對於所有或存在某些的量化詞的語句性質,所以缺乏符號陳述所有數學命題的能力,所以命題邏輯必須要升級到謂詞邏輯(Predicate Logic)。謂詞邏輯的興起從1879年弗雷格(Gottlob Frege)開始有深刻思想,他給出「集合」嚴格的定義。中間經過了羅素等人發展悖論,最終在1928年,希爾伯特定下來謂詞邏輯的最終型態,提出「判定式問題」:有沒有一種算法,能夠判定在謂詞邏輯下的命題是否可以證明成立?

為了解決某個問題是否存在算法解,在1930年代許多論述相繼提出,像是埃爾布朗(Herbrand)與哥爾德(Kurt Gödel)的方程組、丘奇(Alonzo Church)的λ演算、克林尼(Stephen Kleene)的遞歸函數、波斯特(Emil Post)的機器模式。在1936年,丘奇與圖靈解決了判定性(decidability)問題,謂詞邏輯不存在一種判定算法,論證與計算之間有本質上的差異,證明原先希爾伯特提出的用計算來代替論證的計畫永遠無法實現。

●現代計算機科學的鼻祖——圖靈

最終在1936 年,圖靈(Alan Turing)發表了跨時代的文章《論可計算數及其在判定性問題上的應用》(On Computable Numbers, with an Application to the Entscheidungsproblem),將邏輯跟計算機完全的整合在一起,發明了理論計算機,證明通用計算機的存在以及證明計算機無法解決的問題,像是停機問題。換句話來說,上述提到的算法、表徵、工具都是錯覺!在理論的層次,它們能整合在一個架構裡去理解。起初,人類在外面操作機器;現在,把機器的操作跟機器整合在一起。

「在圖靈之前,一般都認為機器、程式、資料三個範疇,是全然不同的區塊,機器是物理性的物件,我們今天稱之為硬體。程式是準備做計算的方案……資料是數值的輸入。通用圖靈機告訴我們三個範疇的區分只是錯覺。」

●圖靈機實體的實現

在二戰結束後,圖靈參與國家物理實驗室的自動計算引擎(Automatic Computing Engine,ACE)計畫,但最終ACE 計畫以失敗收場。直到1948年,威廉斯(Frederic Williams)才成功地讓圖靈計算機變成實體。然而,第一個製造出全自動數位計算機的人不是威廉斯,而是德國工程師楚澤(Konrad Zuse)。他為了處理土木工程很龐雜的計算,他在父母的家中,獨自完成了純機械式計算機Z1,是史上第一台採用二進位系統的計算機。在1941年,楚澤在農莊地下室裡所製作出世界上第一台由程式控制的全自動數位計算機——Z3。

在圖靈思想的指引下,計算為這個世界敞開了一扇大門,讓人類得以進入嶄新的文化層次與時代中。在這快速展開新歷史中,相信還有更多值得期待的新發明,帶領人們進入更廣闊的世界中。

 

--
本文整理自:108/9/21由李國偉老師在臺大思亮館國際會議廳所主講之「計算的軟硬兼施發展脈絡」演講內容。

(Visited 207 times, 1 visits today)

分享至
views