電腦也搞不定, D. Harel 著, 李國偉譯, Computers Ltd., 天下文化【科學天地39】, 2002, ISBN 986-417-023-6.
這本書是 David Harel 在演算法的內容、意義與限制這個主題上， 最新、最薄的一本書。 原本以英文書寫，書名是 Computers Ltd.: What They Really Can't Do， 在西元 2000 年由牛津大學出版，隨後翻譯成德文和義大利文，同時在 2002 年問世。 這裡要談的是李國偉教授翻譯、天下文化出版的中文譯本： 《電腦也搞不定：從數學看計算機科學的罩門》。 這是 Computers Ltd. 的第三種文字翻譯本，甚至比希伯來文 (Harel 自己的母語) 還要早出版。
David Harel 的身份之一是「理論計算機科學」的著名學者。 他的研究領域以演算法分析為主軸，涵蓋了圖靈機、不可決定性、計算複雜度、 自動機理論、程式語言邏輯等等課題；這一學門所運用的工具和方法主要是數學和邏輯。 由於這些側面的觀察，發現李國偉和 David Harel 兩位教授， 在數學、邏輯、哲學，乃至於學者對社會應負起的教育責任方面， 都有遙遙相映之趣， 所以才比較不奇怪何以李教授在那麼繁重的研究、教學與管理負擔之下， 還願意提起筆來親自為 Harel 翻譯他的書？
Harel 和 Donald Knuth 常被人當作堅持「計算機科學之核心課題乃是演算法研究」這種主張的代表人物。 這也不太奇怪，原來 Harel 是 Knuth 的第一位徒孫。 Knuth 在 1968 年進入 Stanford 計算機科學系，1972 年授給生平第二個博士學位： Vaughan Pratt (如今每一個演算法的學生都會遇到 Knuth-Morris-Pratt 字串搜尋算法)，而 Pratt 到 MIT 去發展，他在那裡授給的第一個博士就是 David Harel (1978)。Harel 畢業之後到 IBM 工作一段時間， 想必他在那裡認識了關聯式資料庫的創造者 Edgar Codd 和 SQL 語言。 在那一段時期，他曾投入資料庫查詢語言的理論研究。 1980 年，Harel 回到母國--以色列的 Weizmann 科學研究院。
雖然 Knuth 和 Harel 都揚起演算法之大旗， 不過 Harel 並不完全跟隨祖師爺的腳步。 Knuth 認為演算法比較像數學，它更接近於一種藝術而不是一種科學， 因此他寫了一輩子的那本書叫做 The Art of Computer Programming。 相對地，Harel 先在 1987 年首度出版如今成為經典暢銷書的 Algorithmics: The Spirit of Computing， 隨後又改編成另一本 The Science of Computing: Exploring the Nature and Power of Algorithms。 在這兩本書裡，Harel 傾向於將「演算法學」Algorithmics 視為科學。
前述 Algorithmics 那一本書，是 Harel 的普級著作之成名作， 為他獲得了許多獎項 (想必也帶來不少現金)，原文仍是英文， 另外有荷蘭文、希伯來文和波蘭文的譯本。 1992 年出來第二版，增補一些新的發展。 2000 年出版的 Computers Ltd. 一方面大約是第二版 Algorithmics 的「節本」， 以篇幅來說幾乎一半，省略掉很多細節、特別是數學方面的解釋--雖然 Algorithmics 的數學門檻已經不高，但是 Computers Ltd. 卻幾乎沒有。 另一方面，Computers Ltd. 在這幾乎減半的篇幅內， 卻新增了許多最新發展的材料，不僅有密碼學和零知識證明， 甚至就連量子計算和分子計算都提到了。 有消息顯示 Algorithmics 的第三版預定在 2003 年發行， 此時找不到更進一步的情報，但是我禁不住猜想， 這第三版將會反過來把 Computers Ltd. 當中的新材料擴充進入 Algorithmics， 然後 Harel 就會有兩本相同主題的書傳世：一本重些、另一本輕些。
接續前一段的背景說明，我忍不住要說說對於譯本之副標題的看法。 英文書名一語雙關：Computers Ltd. 的 Ltd. (股份有限公司) 是 Limited 的慣用縮寫，而 Limited 又是「被限制」的意思。 加上副標題 What they really can't do 無非就是要講電腦的「能力界限」， 其使命是要社會覺知：電腦並非無所不能。 譯本的書名用《電腦也搞不定》就夠傳神達意了 (我耳邊忍不住響起很草根的聲音：「電腦也會『撿土豆』唷」)， 再加個副標題「從數學看計算機科學的罩門」就有點不妙。 對於數學興致高昂的讀者，可能會因為內容的數學不夠而稍感失望； 本來就對「數學」兩個字敏感的讀者，看了書名恐怕就要平白錯過一本精彩的小書； 對數學沒什麼意見但是特別親愛計算機科學的潛在讀者呢， 也許因為副標題的語氣而感覺委屈不平，甚至心生反感。 他們或許會說，誰關心「罩門」呢？電腦不過就是個工具， 工具總有適合做和不適合做的事。 總不會有人嘲笑自己的榔頭沒本事，只因為它不好拿來繡花吧？
在前言當中，Harel 就點明了這本書的使命： 他從 1984 年 Times 雜誌封面報導中引述軟體業同行的「誇大」言談說起， 提出一個常見的迷思：認為只要錢花得夠多、電腦的硬體夠快、週邊設備製作得夠恰當、 程式寫得夠聰明，天下就沒有電腦辦不到的事。 他覺得有點吃驚且感到不幸的是，就連他的某些同行也抱持這樣的錯誤信念。 而不論 Algorithmics 或是 Computers Ltd.，都想要負起破除此一迷信的使命。
Harel 在第一章以常用的比喻來引介算法的形式與意義， 然後舉出從明顯到隱晦共八種不同的算法問題。 在舉例當中也順便擴展了所謂「計算」的涵義。 然後聲明這一專業的研究方法看似過於簡化，卻能夠反應世界上的真實問題。 接著他在第二章進入主題，以三個例子展現某些問題是「不可計算」的： 經由數學證明，不可能寫出解決某種問題的程式。 他介紹了圖靈機，也講了 Church-Turing thesis， 並花費半頁來說明 thesis (論點) 和 theorem (定理) 有何不同。 不過他沒有繼續採用這套概念來解釋「停機問題」之不可計算性。 我猜想，沒有見過這種數學或算法論述的讀者， 會覺得這一章頗神秘的。
第三章把那些「可計算」的問題分成兩類：好算的與難算的。 這就相當於一篇簡介計算複雜度下界 (complexity lower bound) 的短文。 所謂「好算的」是指已經確定在「多項式時間」內可以解決的問題。 而「難算的」問題又可以分成兩類：確定難算的和不確定的。 所謂「確定難算的」是指已經證明其複雜度下界是「指數時間」的問題。 對於這一類問題，撒更多鈔票、買更快的電腦或更多的記憶體， 的確可以改善其效能，但是這改善微弱得幾乎所有人都捨不得花這筆錢。 所謂「不確定難算的」是指尚未證明其複雜度下界是「指數時間」、 卻又經過長期努力找不到「多項式時間」算法的問題。 對於這一類問題，理論上不能排除有一天會冒出一個極聰明的人， 寫出一個好算的程式來；但是許多年過去了，卻還是等無人。
第四章從「不確定難算的」問題當中， 抽出一類 NP (nondeterministic polynomial) 問題： 它們雖然尚未找到好算的求解程式，卻有好算的驗證程式。 譬如學校裡一年一度的排課大事，其實屬於 NP： 我們沒有一個通用而好算的程序，保證任意多老師、任意多門課， 可以在任意劃分的課表上，安排一張符合任意限制條件的課表。 但是如果給我們一張課表，卻可以輕易檢查這張表是否滿足了所有老師的要求， 和所有課程之間的安排條件。
更刺激的是，越來越多的 NP 類問題被證明是「相通」的： 只要有個聰明人找到這堆問題當中任何一個問題的好算法， 就等於同時找到了所有這堆問題的好算法， 使得這堆問題 (稱為 NP 完備) 更像是累積許多期沒人中頭彩的樂透一樣。 許多人經常在生活中必須解決的問題，理論上其實屬於 NP 完備： 譬如前面說的排課問題， 出門一趟就想要採購所有用品、辦完所有瑣事的最短路線計畫， 暑假前想要把宿舍裡清出來的大大小小箱子、塞得貨倉越滿越好的方法， 它們竟然都相通，而且也都屬於 NP 類。 雖然我們在生活中看起來好像「解決」了這些問題， 不過就理論而言，我們平常所說的「解決」並不確定是「最佳」解法， 而且仔細想想似乎也得承認， 每次我們「解決」這些問題的時候，都無法採用一個固定程序的方法。
並非所有 NP 問題都屬於 NP 完備，譬如線性規劃就不是。 線性規劃問題本來只有一個指數時間算法 (simplex)， 過了三十多年，果真有個聰明人創造了多項式時間算法 (Karmarkar)， 還史無前例地為他的演算法申請了專利。 有點諷刺的是，在大部分實用情況下，理論上難算的 simplex 算法， 卻比理論上好算的 Karmarkar 算法更有效率。
為了更牢靠地確定第二、三、四章所說的壞消息， 在可想像的未來都還會保持住它們的地位， Harel 在第五章檢視了平行計算機與平行演算法、隨機化演算法， 以及雷聲隆隆的量子計算和分子計算。 對於這四種「異類」的前兩類，Harel 有精彩的概論！ 如果您只想看一萬字以內的報導，把隨機和平行演算的本質與限制都看清楚， 那就是這本書的 120 到 136 頁。 至於量子計算，就我個人讀過的科普書籍來說， 願意推薦《碼書》第八章給大家當作初步瞭解。 而 Harel 在這裡還是強調壞消息，有趣的是他在別處都說理論上的壞消息， 對量子電腦就說實務上的壞消息了。 在分子計算方面，原文譯出來八百個字，讀者不能寄望太高。
讓我岔開兩段，為本文的讀者補充一點材料。 演算法的「壞消息」經常來自於計算複雜度之下界估計。 而估計下界的手段，經常假設存在某種「黑盒子」，就像 p.61 翻譯成「玄器」 的 oracle 那樣，可以在合理的範圍內以「一個計算步驟」回答最神奇的問題。 然後論者要說，就算給你這種神奇的黑盒子， 電腦程式還是必須經過若干步驟才能完成工作。 譬如要將任意 N 個數從小到大排好順序， 不論如何都需要至少 N*lg(N) 次比大小才能完成 (其中 lg(N) 是以 2 為底的 N 對數)， 這就是下界估計。而其論述過程就假設有一個神奇的黑盒子， 你從那 N 個數當中隨便挑一個， 問它「這個數排第七會不會太前面？」這一類的問題， 它可以立即回答是或否。
雖然還沒有實際可用的量子電腦，但是量子算法的研究已經開始了； 當然已經帶來一些令人矚目的好消息 (兩個常見的名字是 Peter Shor 和 Lov Grover)。 不過，在地平線的另一端，關於量子算法的下界研究也已經開始了 (例如 Umesh Vazirani)，而他們也開始散播壞消息。 在手法上，他們仍然假設存在一種神奇的「量子黑盒子」 (忽然發現，這兩個名詞湊在一起還真速配)，它已經完全掌握量子電腦的物理特性， 並且已經在可想像的範圍內能夠回答最不可思議的問題。 在這些前提下，他們能夠針對幾種 NP 類問題，證明即使利用量子電腦的特性， 其計算複雜度下界也不過等於傳統算法下界開個平方根而已。 開平方根的「進步」，在好算的問題上已經夠令人吃驚。 譬如在電子計算機內，從任意 N 個數據中搜尋某個特定數 x， 絕對需要 N 次比對才能確定 x 不在這群數據當中； 而 Grover 證明，若換成量子電腦， 就可以只花根號 N 次「量子步驟」便確定 x 不在其中、 或者在的話在第幾個。 但是在難算的問題方面，如果計算複雜度只是開平方根， 那只是把例如 2 的 N 次方換成 2 的 N/2 次方，還是難算的。 除非那個論述中的「量子黑盒子」還能夠比現在想像的更神奇， 否則量子電腦馴服 NP 類問題的機會，並不太被看好。
這本《電腦也搞不定》邏輯上可以在第五章就結束掉。 可是 Harel 像是要補償讀者似地，在第六章宣佈一些好消息。 他根據 NP 問題很容易檢查答案而很難找到答案的特性， 介紹它們在各類數位安全方面的應用。Harel 寫得比較詳細的是公開金鑰、 數位簽章和零知識證明，我個人覺得最後一項寫得最精彩 (pp.169--175)。 然而這些應用之所有有用，全是因為它們屬於 NP， 但事實上它們屬於 NP 完備。 萬一有一天 NP 完備的其中一員被宣告「好消息」， 也就是找到了好算的算法，那麼這些應用就全毀了。 所以，第六章的最後一句話很莊子：
我們居然希望壞消息繼續保持是壞消息。第六章還算跟這本書的標題相貫，第七章就岔得更遠了一點兒； Harel 在這裡談人工智慧：知識是什麼？智能是什麼？有可能被模仿嗎？如何模仿？ 從 70 年代開始，就接續著有許多具備豐富想像力的人， 從專業的、科普的、科幻的、寓言的各種角度來闡述這個問題。 Harel 想要在這裡闡述壞消息，不過必須使用比較「軟」的論述， 這似乎也表明了 AI 的困難：就連明確描寫壞消息的論述都還沒有成型。 這一章在文字上饒富趣味，但是在意義的傳遞上比較模糊。 本章標題問「我們自己能做得更好嗎？」但是讀者似乎在書裡找不到答案。 譬如看「瞭解自然語言」這一節，我們能做得更好嗎？ 答案恐怕因人而異，但是理論上應該是肯定的。 譬如跟善體人意的 Eliza 相比 (我在十年前真的操作過這種心理醫生模擬軟體， 真是嚇人，它只差沒有一副柔美的嗓音而已)，我們能做得更好嗎？ 至少我不能。或許 Harel 用這一章給讀者最後一個親身體驗： 要回答「是」或「否」，還真是難啊！
固然我們看得出來，Harel 致力於擴展這本書的讀者群， 不過要在 200 頁範圍裡說得透徹，畢竟需要一定的背景知識， 或至少對於所探討的問題有基本認識。 在這個意義之下，我個人感到 Harel 的確可以成功而有效率地以這本小冊子對他的同行、 或者對像我這樣「計算機理論的牆外旁觀者」， 闡述一些關於電腦能力壞消息、與這些壞消息的竟而有用。 對於這一類的讀者而言，不論是正文還是附註，都非常受用。 但是對於再外圈一點兒的科普愛好者， 可能要把這本書當作「理論計算機科學」的大比例鳥瞰地圖， 而需要更精確一點兒的導引，才能找到更精彩的景點。
最後，讓我野人獻曝地提醒讀者，Harel 並不只是一名理論派的學者。 他的另一個身份，是 I-Logix 公司的合夥創辦人， StateCharts 系統藍圖語言的發明人， 接觸過 UML (Unified Modeling Language) 的讀者可能已經從這個角度認識了 Harel。 最近他將物件導向中的訊息交換模型，應用在生物模型上， 還發表了幾篇關於嗅覺和「電子鼻」的文章。 部份文章有公開的 PDF 文件可由他的首頁下載。
[ 回上層 ]