全球知名的計算機科學家哈雷爾告訴你,電腦也有搞不定的時候!
電腦一直被公認為無所不能,從一般人到計算機科學家,
普遍都認為:只要軟體夠厲害,硬體夠快,電腦的能力就會無遠弗屆。
然而事實並非如此,電腦有很多問題無法解決,它離無所不能的境界還遠得很呢!
電腦真是神乎其技,它無疑是二十世紀最重要的發明之一,電腦深入我們生活的各個層面,我們的生命、財產以及生活品質,都與這機器脫不了關係。然而,就在我們持續享受電腦科技帶來的福祉之際,也該是檢討一下電腦的底限的時候了。電腦真的是萬能的嗎?
全球知名電腦科學家哈雷爾在本書中闡釋一個最根本卻也最為人忽略的一面:電腦與生俱來的限制。即便是把所有最棒的硬體、軟體以及電腦工程師全部聚集起來,我們還是得面對一個現實存在的問題:電腦也有搞不定的時候! 就在二十一世紀剛開始時,且聽聽哈雷爾告訴我們電腦這個上個世紀的偉大智慧產品,遺留下哪些惱人、卻又引人深思的疑難雜症待處理。
以色列魏茲曼科學院(Weizmann Institute of Science)數學與計算機科學所所長,現任蘇士曼講座教授(William Sussman Professorial Chair)。他也是美國計算機學會(ACM)和國際電子電機工程師學會(IEEE)的會士。 哈雷爾曾完成計算機科學領域上許多方面的研究,是極受尊崇的計算機科學家。他曾榮獲許多獎項,包括1992年美國計算機學會卡爾斯頓傑出教育家獎(Karlstrom Outstanding Educator Award)、1997年以色列總理頒發的軟體獎。他的著作《算法學——計算的精神》(Algorithmics: The Spirit For Computing)入選為麥克米倫科學圖書館(Macmillan Library of science)1988年春季的選書。
1948年生於南京。台灣大學數學系畢業,美國杜克大學數學博士。中央研究院數學研究所退休研究員,曾任該所所長。多年來致力於科學普及工作,為天下文化「科學文化」叢書策畫者之一。曾獲李國鼎通俗科學寫作佳作獎、吳大猷科學普及著作獎翻譯類佳作獎。
著有《一條畫不清的界線—李國偉的科文游牧集》,譯有《笛卡兒,拜拜!》(與饒偉立合譯)、《宇宙的詩篇》(與葉李華合譯)、《電腦也搞不定》、《科學迎戰文化敵手》、《數學教你不犯錯》、《小學算術教什麼,怎麼教:家長須知,也是教師指南》。
前言 致謝辭
第一章 到底是怎麼回事?
算法
基本指令
文本vs.程序
輸入
算法解決了什麼問題?
我們的架構是否過於簡單?
解決算法問題
程式規劃
錯誤與正確性
終止
第二章 有時候我們辦不到
有限問題是可解的
鋪地磚問題
我們當真嗎?
基本計算裝置
丘池—涂林論點
可計算性是強健的
骨牌長蛇
程式驗證
停機問題
沒有關於計算的問題是可以計算的!
有些問題情況更慘
第三章 有時候我們辦不起
資源:時間與記憶空間
改善跑程式的時間 上界與下界
那又怎樣呢?
河內塔
好的,壞的和醜的
難解性
路障與西洋棋
更難的問題
不合理的記憶體需求
第四章 有時候我們就是不知道
猴子謎題
NP完備問題
尋找短的路徑
排程與匹配
再談謎題
給網路著色
魔術銅幣
同舟一命
大神秘:P等於NP嗎?
我們能接近嗎?
有時候我們能成功
第五章 嘗試減輕痛苦
平行,或說分進合擊
平行化能消除壞消息嗎?
隨機化或丟銅幣
再談蒙地卡羅算法
檢驗質數
隨機化檢驗質數
隨機化能消除壞消息嗎?
電腦能模擬真正的隨機現象嗎?
量子計算
量子算法
能造得出量子電腦嗎?
分子計算
第六章 轉壞為好
古典密碼學
公開金鑰解密系統
替信息簽名
有辦法使這一切實現嗎?
RSA密碼系統
互動證明
零知識證明
我能把網路3著色
一位百萬富翁,選票及其他
第七章 我們自己能做得更好嗎?
算法智能?
涂林測驗
伊萊莎和祖布求
試探法
知識是什麼?
瞭解自然語言
後語
第一章
到底是怎麼回事? 電腦很神奇,它好像什麼都行。它能開飛機與太空船,能操控發電廠與危險的化工廠。沒有它公司無法營運、許多醫療程序無法進行。它能幫助律師與法官尋找法律判例,它能幫助科學家與工程師執行極端複雜的數學計算。
它導引與控制上百萬同時進行的電話通訊,它管理龐大的全球網際網路(internet)的數據傳送。它執行閱讀地圖、排版、影像處理、機械人輔助製程、積體電路設計等任務,都極端精準。它幫助個人處理許多單調乏味的日常瑣事,並且同時提供電腦遊戲的娛樂,以及在網上遨遊的樂趣。
除此之外,今日的電腦正努力協助設計明日更厲害的電腦。 而更令人驚訝的是,即便是最摩登最複雜的數位電腦,基本上也只是一堆叫做「位元」(bit)的開關所組成,每一個位元的狀態可以是開或關。通常用1表示開,用0表示關。
一個位元的值基本上是由某些電子元件的特徵決定,譬如由某一點上的電荷為正或為負而定。從技術的角度來看,電腦其實只能執行極少數非常簡單的動作,像是顛倒一個位元的值,把它歸零,或檢查它的值(也就是當某個位元開時做某件事,當它關時做另一件事)。
電腦之間的差別可以表現在大小(也就是能使用的位元總數上),可以表現在內部組織,以及它所提供的基本運算類型與執行的速度上。它們在外觀上以及與外在世界的聯繫上也會有差異。但是與位元及內在的佈局相比,外觀只是邊緣現象。
由外在世界輸入的刺激,是經過位元來「感知」;如何做出輸出的反應,也是由位元來「決定」。輸入的管道可以是鍵盤、觸感螢幕、控制版、電子通訊線路、麥克風、相機、甚至化學感應器。把輸出傳到外在世界的工具包括顯示螢幕、通訊線路、印表機、揚聲器、呼叫器、機械臂、以及各色各樣的器具。
它們如何達成任務呢?是什麼作用把反轉0與1之類的簡單操作,轉換成電腦驚人的表現呢?答案在於計算科學所立足的概念:計算的程序和算法(或稱之為程式),使它們得以實現。 算法 想像有一個廚房,裡面有烤蛋糕的材料、各種廚具、烤箱、還有一位大師傅。
蛋糕當然是由大師傅用材料製作、放入烤爐、最後焙製出來的,然而最重要的是必須有可供遵循的食譜。蛋糕製作過程中,各種材料是「輸入」,蛋糕是「輸出」,食譜就是「算法」(algorithm)。在電子計算的世界裡,食譜(算法)是包藏在「軟體」之中,而廚具、烤爐則代表「硬體」。
就像電腦只會操作位元一樣,大師傅就算有廚具與烤爐,能耐也有限。烤蛋糕的硬體可以傾倒、攪拌、攤開、注水、揉和、點爐子、打開烤爐門、量時間、量份量,等等。但是它不能直接烤出蛋糕。能讓新手與工具的有限能耐,轉化成蛋糕的魔力在於食譜。
食譜才是真正的核心,而不是烤爐或大師傅。 在電腦的世界裡,食譜叫做算法,研究算法的學問與專門知識叫做「算法學」(algorithmics)。
1 與烤蛋糕的類比可以理解如下:食譜的焙製方法,也就是算法,是抽象的東西。但是見諸書面的食譜,就像是電腦程式(computer program),它用電腦懂得的特定程式語言(programming language)把算法表現出來。但是重要的是我們要記住,同樣的食譜不管用英文、法文、或拉丁文來寫,不管在哪裡,誰來照做,都會有同樣的成品。
同一個算法不管用Fortran、C、Cobol還是Java來寫,不管用輕薄的筆記型電腦,還是占滿整個房間的主架電腦來跑,結果都是一樣。因為軟體是寫來給真正的電腦執行的,所以我們所謂的軟體,通常是指程式,而不是算法這種抽象的概念。但是本書中我們會模糊兩者的差異,因為我們所講的故事對兩者皆適用。 基本指令 讓我們把烤蛋糕的比喻再推進一步。此處有一個做巧克力慕斯的食譜
2,它的輸入,也就是製作的材料,包括8盎司半甜巧克力,2茶匙的水,1/4杯糖粉,6顆分開卵黃與卵白的雞蛋,等等。輸出則是六到八人份美味的巧克力慕斯(Mousseline au chocolat): 在鍋中放入兩茶匙水,然後把巧克力隔水加熱融化。
同時把糖粉攪拌進去,慢慢加進牛油一次加一點點,然後暫時放置一邊。把蛋黃打5分鐘,打到顏色淡黃且濃稠。再把巧克力輕輕加入,如果需要的話,可以稍微加熱融化巧克力。邊攪拌邊加入甜酒與香草精。把蛋白打發,加入2茶匙糖,繼續打到發。輕輕把蛋白倒入巧克力與蛋黃的混合中。
分裝到點心盤裡,冰上4個小時。喜歡的話,可在臨吃時加一點打發的鮮奶油。這個配方可做出6到8客。 這是與做慕斯有關的「軟體」;它是描述由材料到做出慕斯過程的算法。程序由做慕斯的人執行,所用的「硬體」包括各種廚具:煮鍋、加熱器、打蛋器、湯匙、計時器、等等。
在做慕斯的食譜裡,有一項基本指令是:「把糖粉攪拌進去」。為什麼食譜不說:「拿一點糖粉,倒進融化的巧克力,攪拌進去,再拿一點粉糖,倒進去,攪拌,……」如果說得更精確些,為什麼不說:「拿2,365顆粒粉糖,倒進融化的巧克力,拿一根湯匙,然後轉圈子把糖粉攪拌進去,……」甚至更精確點說:「以14度角方向,把你的手臂移向烘焙材料,以約略每秒18英吋的速度……」答案其實很簡單,「硬體」知道如何把糖粉攪拌進融化的巧克力,並不需要進一步的細節。
如果硬體知道如何混合巧克力的假設成立,食譜一開始的步驟就可以省略為:「混合好巧克力」?如果推到極致,假設硬體知道整個烘焙過程,只要簡單地寫;「做巧克力慕斯」就是一份完美的巧克力慕斯食譜。這指令清楚又簡潔,沒有任何錯誤,而且保證照命令製造出指定的東西。
顯然,在討論算法的基本指令時,細節詳盡的程度,影響很大。算法所指定執行的動作,必須切合執行此項任務的硬體的功能。此外,動作要讓人能理解。這是因為算法由人設計,也必須由人確認算法能正確運作,並且維護或者將來修改那些算法。
再看較接近一般計算的例子:整數的乘法。假設我們要用46乘528。通常的「食譜」教你先用6乘8,得出48,把個位數字8寫下,記好十位數字4。再用6乘2,把4加進去,得到16。個位數6寫到8的左邊,十位數1記下來,等等。
我們同樣可以問,為什麼要「用6乘8」?為什麼不說:「在乘法表裡找出第6行第8列的數字」?或者「把6自己加自己8次」?同樣的,我們為什麼不乾脆說:「用46乘528」,就把整個問題一下解決了?最後這個問題有點妙,我們可以直接乘6與8,卻不准直接乘46與528,為什麼呢?
在設計乘法的算法時,同樣的,細節要寫得多詳細,是關鍵的條件。我們假設所使用的硬體(此處就是我們自己),雖然有能力乘6與8,卻沒有能力乘46與528,因此只有前者可以作為算法的基本指令,拿來計算出後者的答案。
這些例子還說明了一件事,就是不同的問題,自然有不同的基本指令。食譜需要描述攪拌、混合、倒入、加熱;乘法需要使用加法、數字相乘、記憶數字;查電話本就需要翻開一頁、把手指沿著名單指下來、比較心中的名字與本子上的名字是否相同。
有意思的是,我們稍後會討論到,對於電腦使用的算法而言,這些基本指令本質上都沒有的差異。 文本 vs. 程序 假如我們手頭上有公司裡每個人的人事資料,每筆記錄裡載有員工的名字、薪水、及其他事項。
我們想要知道員工薪水的總和,下面是求和的算法: 1. 注記數字0; 2. 順著名單而下,把現在看到的員工的薪水加到已經注記的數字上; 3. 把名單看完之後,輸出最後注記的數字。 顯然這個算法能達成任務。「注記」的數字,可以想像成一個空盒子,它裝著一個會變動的數字。這樣的物件我們稱之為「變元」(variable)。
在這個例子裡,注記的數字的值由0開始,當第二行指令對第一位員工執行後,值就變成那位員工的薪水數目。當第二位員工的薪水加進去後,那個值就成為頭兩位員工薪水的總和。如此類推,到最後注記的數字就是全體員工的薪水總和。
有意思的是,這個算法的文本(text)不僅短,而且長度是固定的。但是它所描述的過程(process)卻會隨員工名單的長短而變化,甚至有可能非常非常長。一家10個人的公司,跟另一家百萬員工的公司,都可以用同樣的算法算自己公司員工薪水的總和。
不過頭一家公司算起來,過程會比第二家快很多。再進一步看,不僅算法的文本短而且長度固定,兩家公司也都只需要一個變元(注記的數)來完成任務。因此「廚具」的數目也是小而固定的。雖然注記的數的值,對第二家公司而言可以很大,但是從頭到尾,都只要有一個數字被注記。
因此我們有了一個固定的算法,在各種不同的情況(也就是對於每個不同的輸入名單),它都不需要更改,但是對於不同的輸入情況,它所限定的過程,在長度以及消耗的時間上就會有不同。 輸入 即使薪水求和這麼簡單的例子,也有各種各樣可能的輸入:小公司、大公司、有些薪水會是零的公司、或者薪水都一樣的公司。
算法還得處理一些非比尋常的特例,例如沒有員工的公司、或者接受負薪水的員工(該公司的員工為了過工作的癮,願意花錢來上班)。 事實上,薪水求和的算法,對無窮多的各式員工名單,都應該能圓滿達成任務。
這是從一種極端的方向來理解「短算法、長過程」原則。計算時間,也就是過程長短的差別固然有趣,更值得注意的是,一個固定長度的算法,所限定的過程數目卻可以非常大,甚至經常是無窮無盡。
3 算法的輸入就目的而言,首先必須合規格(legal)。譬如對於薪水求和的算法來說,「紐約時報」的暢銷書單就不能當作輸入,就像不能用花生醬或果凍來當作巧克力慕斯的材料。因此我們需要一種描述輸入的規格(specification)。
必須有人來決定哪種員工名單合用,哪種名單不合用;員工間的紀錄如何銜接;每筆薪水的數目記錄在哪裡,是用完整的數寫下(如$32,000),或者是用簡寫(如$32K),等等。 算法解決了什麼問題?
這些問題都把我們導引到算法學與計算世界底層的中心概念——算法問題(algorithmic problem),也就是利用算法來解決的問題。算法問題的性質必須包含兩個要件: l 精確定義合規格輸入的集合; l 精確刻畫輸入如何決定輸出。 當我們討論算法問題應用到特定輸入上時,(像薪水求和問題應用到某個具體的員工名單),我們稱其為該問題的一個實例(instance)。
算法問題輸入的種類非常繁多:可以是數目、詞句、文本、地圖、甚至其它的算法或程式。問題本身有的純粹在計算,有的涉及重新排列(排序問題),有的需要擷取訊息(尋找共有的詞),有的是最佳化問題(最短路徑),有的是判定性問題(檢定質數及走遍所有都市)。
所謂判定性問題(decision problem)就是給出「是」或「否」答案的算法問題。判定性問題不在於計算、擷取、或最佳化,而是要判斷,也就是決定某種性質到底是真還是假。有些算法問題是混合型的,例如把判定性問題與計算結合,則它的輸出是兩個簡單計算結果之一,但到底是哪一個,就要取決於輸入是否具有某種性質了。 所有這些樣本問題都有無窮個合規格的輸入。
要想解決這些問題,我們必須能處理所有數字的算術,能把所有字串排序,能在所有都市地圖裡尋找最短路徑。換句話說,我們針對每個問題,都要發明一種方法,一種公用的程序或處方,以解決該問題的任何實例。而可能的實例數目是無窮多,這類的方法就構成一個算法。
在現實生活的世界裡,很多算法問題並不那麼容易界定清楚。有時很難界定所想要的輸出。譬如從西洋棋的某個盤面,問下一步最好的走法(什麼是「最好」難以精確規定)。在另外一些情形裡,描述輸入非常複雜。假設有20,000種報紙要用50輛卡車分派到100個都市的1,000個分銷點,輸入就必須包含城鎮間的距離,每個城鎮裡各分銷點間的距離,每個分銷點所需的報紙種類與數量,目前每輛卡車的所在,每輛卡車能承載的報紙量,待命司機的確實人數和所在地點,每輛卡車的運貨量、汽油容量,以及每加侖汽油能跑多少里程。
輸出則是一張排班表,指定哪位駕駛開哪輛車、到哪個目的地,使得派報公司的成本最為節省。事實上,這個問題所需要的算法,應該對任何數目的報紙、城鎮、分派點、卡車都適用。 有些問題既有難以掌握的輸入,又有難以規範的輸出,譬如天氣或是股票市場趨勢的預測。 在這本書裡,我們只專注於看來簡單的算法問題,它們通常都有容易描述的輸入與輸出。
事實上,我們多半專注在判定性問題上。因此我們的問題會比較容易描述,而輸出經常為「是」或「否」。 我們的架構是否過於簡單? 我們會不會把事情搞得過於簡單了?電腦忙著對付各種複雜問題,哪裡只是讀取簡單的輸入,做一點工作,然後答覆「是」或「否」就停止。
假如對現代電腦在實際計算上的架構,例如互動式的計算、分封系統、即時系統、大量圖像的運用、多媒體、以及整個網際網路世界避而不談,難道不會使我們的講法站不住腳嗎? 你也許想對我這個作者說:「你也是冬烘先生嗎?你懂不懂計算啊?別給我們這一套閒聊式的簡單輸入/工作/輸出的計算,拜託,拿出貨真價實的東西嘛!」 我的答案是,不錯,我們是在簡化事情,而且簡化得非常厲害。但是簡化得有理。記得嗎?我們是在處理壞消息。
這本書不在於使事物更好、更小、更強、更快,而是要說這些目的經常是達不到的,經常會搞得糟透了,有些甚至根本沒有可能性。如果以闡釋壞消息為目的,那麼考慮比較簡單的問題類型,會使我們的論證與斷言更強,而非更弱。
我們要證明即使在非常簡單的計算架構下,事情都已經可以糟到不可收拾。不言而喻,在更細密複雜的系統裡,必然會出狀況。電腦有無可彌補的先天的侷限這件事,發生在簡單輸出入計算系統,比發生在複雜計算系統更能凸顯問題。
此外,雖然本書幾乎只討論判定性問題,我們其實也暗示了壞消息與需要用複雜冗長的輸出無關。只是要回答「是」或「否」就足夠產生惡夢了。 注釋: Algorithm這個字源自於九世紀阿拉伯/波斯的數學家穆罕默德‧科瓦力茲彌的名字Mohammed al-Kowârizmî,據說他首先訂出出十進位算術的逐步演算法則。
他的名字在拉丁文中變成Algorismus,英文的algorithm就是由此衍生。歷史上第一個重要的算法是西元前400到300年間希臘的大數學家歐幾里得發明的。人稱「歐幾里得算法(Euclidean algorithm)」的方法,可以計算出兩個正整數間的最大公因數(gcd),也就是可以同時整除兩數的最大整數。例如:80與32的gcd是16。最早出現algorithmics這個字的地方應該是J. F. Traub的書Iterative Methods for the Solution of Equations (Prentice-Hall, 1964)。
最先在書中建議把這個領域叫做algorithmics 的是D. E. Knuth: Algorithmic Thinking and Mathematical Thinking, American Math. Monthly 92(1985), 170 - 181,而本書作者率先使用在書名上Algorithmics: The Spirit of Computing (Addison-Wesley, 1987)。 2 食譜採自Sinclair and Malinowski (1978), French Cooking. Weathervane Books, p. 73. 3 在可能的輸入有無窮多個的例子中,情況與食譜的類比有點不同。
雖然食譜不管用多少次,都應該得到正確的成果,但是因為所使用的材料總是有固定數量,所以食譜其實只有一種可能的輸入。當然巧克力慕斯的食譜也可看做是一個通則,我們可以按比例調整成為不同的輸入。
摘自《電腦也搞不定》第一章
前言
1984年《時代》雜誌某次封面故事以電腦軟體為主題,在這篇精彩的文章裡,引用了一位軟體雜誌主編的話:「只要把恰當的軟體放進電腦裡,它就會做任何你想叫它做的事。機器本身的性能也許有一定的極限,但是能用軟體做的事卻沒有極限。」 錯了,而且大錯特錯!
我這本書一言以蔽之,就是要來描述與解釋一些事實,以駁斥甚至粉碎上面那種說法。 當然,電腦是很了不起的東西。它無庸置疑是二十世紀最重要的發明,巨大而不可逆轉地改變了我們的生活方式,並且多半是往好處改變。不過這只是消息中好的一面,大部分談電腦的書都在表揚好的這一面。
我這本書要傳播的卻是壞消息,檢討一下事情負面的真相。 電腦挺貴的,這已經是壞消息了。此外它還讓我們飽受挫折:替它寫程式很費勁,用起來有時又很困難;它又很能吸引人,讓我們忽略更重要的事;它會出錯;它會當機;它會感染病毒;等等,等等。
然而這本書裡關心的壞消息倒不是這類掃興的事。這本書的目的是要解釋與闡明電腦世界裡最重要、最基本的事實之一:電腦在先天上是有限制的。 當人們沒辦法讓電腦順著自己的意思運作時,通常會找到三種藉口:錢不夠、時間不夠、腦筋不夠。
如果錢多一些,就可以買更大更精良的電腦,用更好的軟體來支援;如果年紀輕點,或者壽命長點,就有時間等待極度耗費時間的程式跑完;如果腦筋更聰明點,就可以找到一般人想不到的解決辦法。這些都是有力與正確的論點,我們並不想辯駁:這三種資源如果能有更充沛的供給,確實可以有效助我們一臂之力。
然而大致上來說,我這本書並不在討論這一類的匱乏。我們所討論的壞消息均屬經過證實、恆久不變、顛撲不破,都涉及電腦根本無法解決的問題,與硬體、軟體、聰明才智或耐心毅力都沒關係。當我們說「經過證實」,指的是真正經過數學的證明,而不光是泛泛的經驗談。
我們為什麼會對壞消息感興趣呢?計算機科學家不是應該花時間把東西做得更小、更快、更簡單、更好用、功能更強嗎?不錯,他們是應該這麼做,大多數的計算機科學家也確實在這麼做。不過即使如此,自1930年代開始,愈來愈多研究者非常努力嘗試想了解錢幣的另一面,也就是了解電腦天生的弱點。
這類研究的動機來自四個方面: 滿足知識上的好奇心。就像物理學家想判定宇宙的終極大小,或是物理定律的基本限制一樣,計算機科學家想發現什麼能計算、什麼不能計算,而如果能計算時又要花多少成本。
許多人,甚至包括專精的電腦專家,都嘗試解決一些計算問題,而這些問題剛好都會帶來慘透了的壞消息。我們愈理解這些問題的本性,就愈不需要浪費時間與氣力了。 促進發展新的典範。如果沒有壞消息的刺激,像平行算法、隨機化、探索法、量子與分子計算等有潛力又令人振奮的計算科學新研究領域,就不會發展起來。
讓不可能的成為可能。讓不可能的成為可能?!這不是有點太矛盾了嗎?我們如何能從壞消息裡獲得利益呢?謎底要到第六章才揭曉,我們此刻只能說這是我們故事裡比較令人感覺始料未及,且令人驚喜的有益的一面。 動機講得夠多了,至於我們所謂壞消息的本質,可以從那些嘗試強化電腦能力,使它達到人類智能的大量精彩研究中找到。
在這些研究的發展過程中,就產生電腦計算能力侷限的問題,像是電腦能不能經營公司?能不能進行醫療診斷?能不能創作音樂?能不能談情說愛?雖然已經達成一些前景樂觀、令人稱奇的進展(不過,最後一項的進步最為遲緩),但是這些問題的問法都太不精確且籠統含糊。除了本書最後一章外,我們不去談這類問題。
反之,我們將集中注意力在精確定義的計算問題上,它們都天生具有明確的目標。因此就可以精確地說明白,這些問題能夠、還是不能夠圓滿解決。 我們所討論的問題並不是可辯論的,也不涉及哲學性、擬科學性的論證。
我們專注於可嚴密敘述、可用數學證明的鐵的事實。你不會花功夫去找內角和是150度或200度的三角形(雖然從來沒有人度量過所有的三角形),只因為早已證明這種三角形不可能存在。 同樣的,當一些我們將會討論的計算問題被證明是無解時,再想去尋找答案就是毫無意義的了。
類似的情形也可以推演到某些有解答的問題上,它們通常被證明需要用到超乎常理的巨大電腦(譬如,體積比已知宇宙還大得多),或者需用掉極不合理漫長的計算時間(譬如,要花比從大霹靂至今更長的時間)。我們也會討論很多這類的問題。
絕大部分的人都不曾覺察到本書所探討的問題。就像《時代》雜誌引言所顯示,連計算行業裡的專業人員,也毫無警覺,這實在是很不幸且讓人吃驚的狀況。假如壞消息是新近發現的現象,因此沒有太多人認識它,或許還可以理解。但是事實上我們要講的故事,有些已經有60幾年之久,早在電腦問世之前就已存在。而其他的則在近30年中逐步顯現。
坦白說,我們這些作計算機科學研究的人也應該受到責備,我們太沒有花功夫向大眾解釋、舉例、描繪這個學門的基本知識,以及強調其負面的事實。導致大眾幸福安詳,充滿崇敬的隨著軟、硬體的技術精進,而沈醉於嶄新應用功能的亢奮中,憧憬著由即時通訊、多媒體、虛擬實境、人工智能、全球網路革命等等所帶來的未來世界。
雖然盛會不必就此散席,而且我們本就該致力發展更大更好的事物。但是,適度的謙虛是有必要的:電腦不是萬能的——它還差得遠呢!而且這些問題真的存在,永遠不會消失,想躲也躲不掉。 注釋: 1如果想對科學家感興趣的限制性結果有較通盤的了解的話,請參閱 Barrow, J. D. (1998). Impossibility: The Limits of Science and the Science of Limits. Oxford University Press, Oxford. 2我們指的當然是平面的三角形。在球面或近乎球面的曲面上,例如地球的表面,三角形三內角和會略大於180度。
天下文化不會主動以電話等方式,告知您因訂單錯誤或分期付款等原因,需要您親自到ATM操作修正, 或請您提供往來銀行電話、信用卡資料;亦不會以 「問卷」或「中獎」形式通知您提供個人資料或要求匯款, 若您接獲此類可疑電話,請與我們連繫確認或撥打165警政專線求證,以確保權益。請勿聽從任何指示到提款機(ATM)做任何操作。
退換貨說明: