[1993]斯坦恩斯--"打工"帶來的機遇

? ? ? ? 斯坦恩斯是學數學出身的。1958年他在卡爾頓學院(Carlton?College)取?得數學學士學位后進入普林斯頓大學研究生院，用了3年時間就?取得博士學位，其博士論文課題是關于博奕論的。
? ? ? ??斯坦恩斯跨進計算機科學的大門并成?為一個出色的計算機科學家是十分偶然的。1960年暑假，他到通用?電氣公司打工，被分配到研究實驗室新成立的"信息研究部"，這?使他有緣與已成為那里正式職工的哈特馬尼斯一起工作。學過?物理而后改行數學的哈特馬尼斯和專攻數學的斯坦恩斯相結?合，雙方取長補短，相得益彰，使他們的合作富有成果。他們的第?一個合作課題是"關于時序機的狀態分派問題"。這項研究進行得?十分順利，暑假打工結束時，他們已經完成了第一篇合作論文，這?就是第二年發表的"On?the?state?assignment?problem?for?sequential?machines"，(刊載?于《IRE?Trans.Electr.Comput》雜志，EC10，P593～603，Dec.1961。)暑期臨時工?的經歷雖然十分短暫，但通用電氣公司研究人員的素質和才能，?那里濃郁、自由、活潑的學術空氣，以及新的、充滿機會的學科領?域給斯坦恩斯留下了十分深刻的印象。因此，一年后他一拿到學?位，?就毫不猶豫地應聘到通用電氣公司工作，與哈特馬尼斯再度?攜手，終于再創輝煌，很快完成了奠定"計算復雜性"理論基礎的?那篇著名論文。
? ? ? ?說來有趣，哈特馬尼斯和斯坦恩斯在?通用電氣公司研究計算復雜性的最初幾年，實驗室里并無計算?機可用。他們當時完全是依靠嚴密的理論分析提出有關"計算復雜性"的一系列問題，并給出了科學的解釋的。祆1964年，實驗室?才配了一臺GE300，斯坦恩斯這才開始用BASIC編程，通過電傳打字?機接口使用計算機。在?科學技術的發展史上，開創復雜而重要的?學科領域并取得巨大成功的學者，最初往往在十分困難的條件?下工作，這種情況是屢見不鮮的。
? ? ? ??斯坦恩斯和哈特馬尼斯在研究"計算?復雜性"理論的過程中，還有一個細節值得一提。據斯坦恩斯本人?回憶，他們首次明確提出"計算復雜性"這一名詞的論文有過三個?版本：最早是1963年4月實驗室內部的一個研究報告，沒有公開發?表；然后是在1964年于普林斯頓舉行的IEEE第五屆開關電路理論?和邏輯設計學術年會上提交?瑤蚺□A題為("遞歸序列的計算復雜?性")("Computational?complexity?of?recursive?sequences")，刊于會議論文集82～90?頁。第三個版本是發表于美國數學會匯刊1965年5月上的("論算法?的計算復雜性")("On?the?computational?complexity?of?algorithms")。這三個版本?中，會議版本雖然早于雜志版本發表，但實際上卻是最后一個版?本。因為在此之前，他們對布盧姆M.Blum(見"圖靈獎得主簡介")在?MIT博士論文研究的是同樣問題并無所知；會議之前他們偶然獲?知這一情況，便立即去MIT拜訪了Blum，雙方進行了交流。當時，哈?特馬尼斯和斯坦恩斯已是國際知名大公司的研究人員，而布盧?姆則不過是來自南美洲的小國委內瑞拉的青年學子。但哈特馬?尼斯和斯坦恩斯并不因此而對布盧姆有任何輕視，并且發現布?盧姆在對"復雜性類"等方面的研究比自己還深入一些，因此對布?盧姆十分推崇，并把他的博士論文列入了他們自己的會議論文?的參考文獻之中，雖然該博士論文當時尚未公開與發表。他們這?種在學術上平等待人，互相尊重，善于交流的作風是很可貴和值?得盡?□滿C
? ? ? ??斯坦恩斯后來除了在"計算復雜性"理?論上繼續有建樹并發表了許多論文外，還對?編譯器的設計與理?論進行深入的研究并取得了成果。1976年，斯坦恩斯最先提出將上?下文無關之法的理論應用于編譯器的設計，推動了編譯器技術?的發展。他和P.M.Lewis以及D.J.Rosenkraty合著的《CompilerDesignTheory》一書(ADDISONwESLEY，1976)被軟件界認為是"編譯器設計理論"方面最?出色的專著之?一。
? ? ? ?斯坦恩斯在接受圖靈獎時發表了題為?"是重新考慮時間這個問題的時候了"("It's?Time?to?Recons?ider?Time")的演?說。演說中概括了他和哈特馬尼斯以及布盧姆共同奠定了計算?復雜性理論的基礎以來，這一重要領域所取得的主要進展。關心?這一領域的讀者不妨一閱。演說全文刊載于1994年11月的《Communications?of?ACM》，95～99頁。
? ? ? ??斯坦恩斯現為奧爾馬尼紐約州立大學?計算機科學系教授，其電子信箱為：res@cs.albany.edu

?

?[1994]人工智能大師--費根鮑姆

? ? 他的重大貢獻在于：通過實驗和研究，證明了實現智能行為?的主要手段在于知識，在多數實際情況下是特定領域的知識。

? ? ?1994年度的圖靈獎由兩位人工智能專家分享，其一是聲名卓著的愛德華·費根鮑姆(EdwardAlbert?Feigenbaum)；另一位是后起之秀的雷伊·雷蒂(RajReddy)。費根鮑姆1936年生于新澤西州的威霍?肯，生父是波蘭移民，但在費根鮑姆一歲時就去世了。他的繼父是?一個食品店的會計，使用著一臺笨重的機電式蒙絡計算器(Monroe?calculator，是20世紀初的發明)，這引起少年費根鮑姆的極大好奇與興趣。1952年，費根鮑姆進入卡內基梅隆大學(當時還叫卡內基?理工學院)電氣工程系。在那里，他遇到了著名的諾貝爾獎得主西?蒙教授(也是圖靈獎得主，以后將會介紹)。在他的指導下，費根鮑?姆實現了一個模擬人在刺激反應環境中記憶單詞時的反應的?程序，叫做EPAM(基本識別和存儲設備系統的縮寫)，并以此為題完?成了他的博士論文。獲得博士學位之后，費根鮑姆獲得Fulbright獎?學金到著名的英國國立物理實驗室NPL工作過一段時間。圖靈曾?是NPL的研究員，在那里設計和制造了最早的計算機之一ACE。費?根鮑姆去NPL時，圖靈已于1954年去世，但圖靈在NPL留下的巨大影?響還在，活躍而富于創造性的空氣還在，甚至ACE計算機

也還在?使用。費根鮑姆在NPL的時間雖然不長，但這段經歷對他的影響?卻很大。
? ? ? ??回到美國以后，費根鮑姆進入斯坦福大?學繼續其人工智能的研究。在人工智能初創的第一個10年中，人?們著?囿漪O問題求解和推理的過程。費根鮑姆的重大貢獻在于：?通過實驗和研究，證明了實現智能行為的主要手段在于知識，在?多數實際情況下是特定領域的知識，從而最早倡導了"知識工程?"(Knowledgeengineering)，并使知識工程成為人工智能領域中取得實際?成果最豐富、影響也最大的一個分支。
? ? ? ??費根鮑姆本人，作為知識工程的倡導者?和實踐者，于1965年和遺傳學系主任、諾貝爾獎得主萊德伯?(Joshua?Lederberg)等人合作，開發出了世界上第一個專家系統程序?DENDRAL。DENDRAL中保存著化學家的知識和質譜儀的知識，可以?根據給定的有機化合物的分子式和質譜圖，從幾千種可能的分?子結構中挑選出一個正確的分子結構。
? ? ? ?DENDRAL的成功不僅驗證了費根鮑﹊?關于知識工程的理論的正確性，還為專家系統軟件的發展和應?用開辟了道路，逐漸形成具有相當規模的市場，其應用遍及各個?領域、各個部門。因此，DENDRAL的研究成功被認為是人工智能研究的一個歷?史性突破。費根鮑姆領導的研究小組后來又為醫學、?工程和國防等部門研制成功一系列實用的專家系統，其中尤以?醫學專家系統方面的成果最為突出，最負盛名。例如，用于幫助醫?生診斷傳染病和提供治療建議的著名專家系統MYCIN等。目前，學?術界公認，在將人工智能技術應用于醫學方面，斯坦福大學處于?世界領先地位，這和費根鮑姆是分不開的。
? ? ? ?費根鮑姆有句名言："知識中蘊藏著力?量"("Inthe?Knowledge?liesthepower")。這句話和培根的名言"知識就是力量?"意義相近，但似乎更確切些：知識只μ誕人所發掘和掌握時，才?能生成力量。
? ? ? ?費根鮑姆有許多重要著作。1963年他主?編了《Computersand?Thought》(《計算機與思想》McGrawHill)，這本書被認?為是世界上第一本有關人工智能的經典性專著。書中收錄的21?篇文章是人工智能學者早期的研究成果，但其中的大部分觀點?和結論至今仍被認同。
? ? ? ??80年代，費根鮑姆和AvronBarr等人合編?了四卷本的《人工智能手冊》(《The?Handbook?of?Artificial?Intelligence》)，前三?卷于1981年、1982年由William?Kaufmann出版社出版，第四卷于1989年由?Addison?Wesley出版社出版。這套手冊的內容涵蓋了人工智能的理?論與實踐酢跗萸锳是從事人工智能研究和開發的工程技術?人員必備的參考書。
? ? ? ??日本推出5代機計劃以后，費根鮑姆曾?到日本進行深入考察，寫出了《The?5th?Generation:?A?Iand?Japan's?Computer?Challenge?to?the?World》(《第五代：人工智能和日本計算機對世界的挑?戰》NewAmericanLibrary,1984)。本書在中國人工智能和日本計算機對世界的挑?戰》NewAmericanLibrary,1984)。本書在中國大陸和臺灣省都被譯成中文?出版，在中國人工智能界也有很大影響。還有一本有影響的著作?是《The?Rise?of?the?Expert?Company》(《專家公司的興起》TimesBooks,1988)。費根鮑姆在接受圖靈獎時發表了題為"?什么"怎樣變成"如何"的演說(How ?the"what"?Becomes?the?"How")，對人工智?能的發展作了一個歷史性的回顧與總結?，全文刊載于?《Communications?of?the?ACM》，1996年5月，97～104頁。
???費根鮑姆除在斯坦福大學計算機科學?系任教授外，還是美國空軍的首席科學家。
???費根鮑姆的電子信箱?如下：feigenbaum@cs.stanford.edu

?

[1995]布盧姆--為計算復雜性理論奠基

? ? ?1995年度的圖靈獎授予了加州大學伯克利分校著名的計算機科?學家曼紐爾·布盧姆(Manuel?Blum)。布盧姆是計算復雜性理論的奠?基人之一，而計算復雜性是計算機科學的一個基礎性分支，十分?重要。圖靈獎至今的39位得主中有6位是由于在計算復雜性方面的杰出貢獻而獲此殊榮。
? ? ??所謂"計算復雜性"，通俗說來，就是用計?算機求解問題的難易程度其度量標準：一是計算所需的步數或?指令條數(這叫時間復雜度)，二是計算所需的存儲單元數量(這叫?空間復雜度)。我們當然不可能也不必要就一個個具體問題去研究它的計算復雜性，而是依據難度去研究各種計算問題之間的?聯系，按復雜性把問題分成不同的類，即ComplexityClass。
? ? ? ??在采用圖靈于30年代提出的理想化的?計算模型即圖靈機作為標準的計算工具的情況下，可以非形式?化地定義如下幾類計算問題：
?
???1. P類問題：由確定型圖靈機在多項式時間內可解的一切判?定問題所組成的集合；
?
???2. NP類問題：由非確定型圖靈機在多項式時間內可計算的判定?問題所組成的集
???合；
?
???3. NP完全問題：如果判定問題π?NP，并且對所有其他判定問題?π?NP，都有
???π'多項式變換到π(記為π'∞π)，則稱判定問題π?是NP完全的。
?
???對P類，NP類及NP完全問題的研究推笆?了計算復雜性理論的發展，產生了許多新?概念，提出了許多新方?法。但是還有許多難題至今沒有解決，P=?NP就是其中之一。許多學?者猜想P≠NP，但無法證明。
? ? ? ??計算復雜性的研究始于50年代末、60年?代初，當時在美國有兩個并行的中心，一個是通用電氣公司設立?于紐約州斯克內克塔迪(Schenectady)的研究實驗室，核心人物是哈?特馬尼斯(J.Hartmanis)和斯提恩斯(R.Stearns)。1964年11月，他們在普林斯?頓舉行的第五屆開關電路理論和邏輯設計學術年會上發表了論文"Computational?Complexity?of?recursivese?quences"(遞歸序列的計算復雜性)，論?文中首次使用了"計算復雜性"這一術語，由此開辟了計算機科學?中的一個新領域，并為之奠定了理論基礎。他們兩人是1993年度?圖靈獎獲得者(以后在本欄中還將專門介紹)。另一個中心是麻省?理工學院MIT，在那里，布盧姆與前述兩人互相獨立地進行著相關?問題的研究，并完成了他的博士論文："A machine?independent?theory?of?the?complexity?of?recursive?functions"(遞歸函數復?雜性的機器獨立理論)，該論?文的詳細摘要1967年發表于《J.ACM》14(2)P322～336。實際上，布盧姆?是受以色列學者拉賓(M.O.Rabin)的啟發而開始這方面的研究的。拉?賓是希伯萊大學的教授，是研究計算復雜性問題的先驅，并在?1976年榮獲圖靈獎(以后也將專門介紹)。拉賓在1959～1960年間就?發表過一些關于"計算復雜性方面的論文和報告，惜流傳的面?太小，影響不大。但MIT"慧眼識英雄"，邀情拉賓前來講學。布盧姆?當時正苦于沒有適當的課題作博士論文，聽了拉賓的講座極感?興趣，當即決定沿此方向進行研究，其結果就是完成了上述博士論文。布盧姆的論文不但提出了有關計算復雜性的一些公理，而?且在對復雜性類的歸納上也比其他學者有更高的抽象度。因此?學術界公認，布、哈、斯三人是計算復雜性理論的主要奠基人。
? ? ? ??布盧姆除了在計算復雜性理論方面做?出了開創性貢獻以外，還致力于將這一理論應用于對計算機系?統的安全性和通信的安全性有十分重要意義的"密碼學"以及在"?軟件工程"中十分重要而又十分困難的程序正確性驗證方面，并?且取得了令人矚目的成就。1989年5月，他和事Sampath?Kannan在西?雅圖召開的21屆ACM計算理論專題研討會上所提交的一篇論文?中，首次提出了"Program?Checker"的概念，并綜合利用密碼學、概率算?法和程序測試、概率交互證明等手段解決程序正確性驗證這一?難題，把這一領域的研究推進了一大步。有興趣的讀者可參閱他們發表在《J.ACM》1995年1月號上的論文"Designing?Prognams?that?check
?Their?Work"。
?
???布盧姆現在在加州大學伯克利分校任教。

[1996]讓時態邏輯“搬家”?——伯努利?

? ? ? ? ?1996年度的圖靈獎授予了一位以色列學?者，著名的以色列魏茨曼學院(Weizmann ?Institute?of?Science，位于圣城耶?路撒冷西北約50公里的雷霍沃特)應用數學系教授艾米爾·伯努利(Amir?Pnueli)，以彰顯他把時態邏輯引入計算機科學所做的貢?獻。
? ? ? ??伯努利于1967年在魏茨曼學院獲應用數學博士學位，后留校任教。他的主要研究方向是時態邏輯或叫?時序邏輯(temporal?logic)。時態邏輯是非經典邏輯中的一種，它研究?如何處理含有時間信息(現在、過去、將來；之前、之后等)的事件的命題和謂詞。時態邏輯體系包含的要素有：
????1.?基本符號：事件e，關系或謂詞r，時間區間i(interval)等。
????2.?時態謂詞：after(e,r),before(e,r)等。
????3.?時態事件演算規則：初始規則、終止規則等，如holds(before(e,r))：
???????terminates(e,r)表終止規則，意為若事件已使謂詞r失效，則在e之前?且r成
???????立以一段區間中r為真。
????4.?時態邏輯運算：時態區間的并交，時態謂詞的與、或、非等。

? ? ?1977年，伯努利把時態邏輯引入計算機?科學，把它作為開發反應式系?統(reactivesystem)和并發式系統?(concurrentsystem)時進行規格說明(specification)和驗證(verification)的工具，?取得了極大的成功，在軟件工程界引起轟動，被認為是軟件工?程中的一場革命。伯努利也因此而聲名大振，他曾被斯坦福大?學，哈佛大學等著名高等學府聘為客座教授或進行講學。
? ? ? ??伯努利主要從事教學和研究，但也和國?外絕大多數教授一樣，不限于“純學術”工作。他和別人一起在?美國馬薩諸塞州的Burlington辦了一個公司：i?LogixInc，他任該公司首席科學家。
? ? ? ??伯努利和我國科學院院士、著名的邏輯?和軟件學家唐稚松是朋友和知交。唐稚松曾向伯努利建議，把?“時態邏輯”當作整個軟件開發過程(包括需求、規格說明、設計、?證實、驗證、代碼生成和集成)的普遍的基礎，而不局限于規格說明和驗證。伯努利深受啟發并對唐先生的聰明和眼光大為贊?嘆。1995年8月，為慶祝唐稚松70壽辰，舉辦了一個名為“?□閻M軟?件工程”的國際專題討論會，伯努利帶了一篇新的論文來北京?參加了這個討論會，并負責編輯出版了會議論文集(Logicand?Software?Engineering:?International?Workshopin?Honour?of?ChihSung?Tang,?Singapore:?World?Scientific?Press,1996)。在論文集的前言中，伯努利敘述了他和唐稚松?之間的這段交往。
?
???伯努利的代表作如下：

《The?Temporal?Logic?of?Reactiveand?Concurrent?Systems:?Specification》(SpringerVerlag,1992)
?《Temporal?Verification?of?Reactive?Systems:?Safety》?(Springer?Verlat,?1995)
???伯努利現任斯普林格出版社著名的系?列叢書“Lecture?Notesin?Computer
???Science”的編委，也是有關領域的不少?雜志如《Acta?In?formatica》、
???《Science?of?Computer?Programming》、《Noteson?Computer?Science》的編委。
?
???伯努利的電子郵箱為：amir@wisdom.weizmann.ac.il