曼紐爾·布盧姆

曼紐爾·布盧姆（ManuelBlum），1938年4月26日生於委內瑞拉首都加拉加斯。Blum是計算的複雜性理論的奠基人之一，該理論可以應用於密碼術及程序校驗。1995年，Blum在美國伯克利的加州大學的事業非常輝煌，並於同年在那裡以奠定了計算複雜性理論的基礎和在密碼術及程序校驗方面的貢獻而獲得計算機領域中的最高獎項：圖靈獎。 1999年，Blum來到卡內基梅隆大學做客座教授。2001年秋天，他正式獲得了卡內基梅隆的教授職位。從他早期關於計算的內在局限性的研究開始，Blum的工作就圍繞著一個統一的主題展開，那就是發現在一個所有計算資源全是有限的世界里生存的實際結果。他指出，由於所有的計算的設備資源有限，安全的商業交易和假的隨機數發生都是可能的。

Blum研究興趣包括計算機、物理、邏輯、複雜性理論、演演算法、保密協議和機器學習等等。而他在計算機科學方面的興趣則尤為突出，因此，他在WarrenS.McCulloch和WalterPitts的神經生理學實驗室工作了幾年，在 MarvinMinsky.的領導下研究人工智慧。空餘時間，Blum經常思考什麼是知覺，我們的電腦和機器人能有知覺嗎？他們能像人一樣進行思考嗎？

Blum解決這些問題的途徑是通過CAPTCHA項目，即“全自動區分計算機和人類的圖靈測試（CompletelyAutomatedPublicTuringTest）”。一個CAPTCHA是任何一個能區分計算機和人類的程序。這些程序能夠進行人類可以輕鬆就過關而計算機卻不能的測試。這幾乎是一個荒謬的要求，因為這意味著CAPTCHA必須能生成並評價人類能很容易通過但計算機卻通不過的測試。何況一個人類能通過而計算機不能的測試真的存在嗎？Blum認為，總有一天計算機能通過所有人類能通過的測試，但是在那一天到來之前，CAPTCHA是可以存在的。而且這些測試有著確定的效用，例如該測試被Yahoo用於確保在網站上登陸獲取email帳號的是人類而不是機器人。

卡內基梅隆大學校長JaredCohon說：“ManuelBlum在計算機科學學院做了20年努力，另外，ManuelBlum除了是一位在計算理論方面最具創造性的科學家之一，他還是個鼓舞士氣的人，計算機科學領域最偉大的顧問之一。計算機科學學院的院長JamesMorris說道：“Manuel多年以來一直是計算機科學領域中一股具有創造性的力量，他也將繼續使我們的智力環境變的更加生動。”他曾經給過至少29名學生建議，在他的鼓勵下，這些學生多數走向社會並開創了計算機科學的新領域。

ManuelBlum曾在麻省理工學院學習，1959年和1961年他分別在那裡獲得了學士學位和碩士學位，並於1964年獲得了博士學位。

1.計算機複雜性理論

1995年度的圖靈獎授予加州大學伯克利分校的計算機科學家曼紐爾·布盧姆（ManuelBlum）。布盧姆是計算複雜性理論的主要奠基人之一。在此之前，已有5位科學家因為在計算複雜性理論方面的貢獻而獲此殊榮，他們是：拉賓（1976年）、庫克（1982年）、卡普（1985年）、哈特馬尼斯和（1993年）。在圖靈獎34年的歷史上，這是獲獎科學家最多的一個分支領域，由此可見計算複雜性作為基礎性分支在計算機科學中的突出地位及其重要性。

計算複雜性的研究始於20世紀50年代末60年代初，當時在美國有兩個并行的中心，一個是通用電氣公司設立於紐約州斯克內克塔迪（Schenectady）的研究實驗室，核心人物是哈特馬尼斯（J．Hartmanis）和斯特恩斯（R．Stearns）。1964年11月，他們在普林斯頓舉行的第五屆開關電路理論和邏輯設計學術年會上發表了論文Computationalcomplexityofrecursivesequences（遞歸序列的計算複雜性），論文中首次使用了“計算複雜性”這一術語，由此開闢了計算機科學中的一個新領域，並為之奠定了理論基礎。他們兩人是1993年度圖靈獎獲得者。另一個中心是麻省理工學院MIT，在那裡，布盧姆與前述兩人互相獨立地進行著相關問題的研究，並完成了他的博士論文：Amachiceindependenttheoryofthecomplexityofrecursivefunctions(與機器無關的遞歸函數複雜性的理論)，該論文的詳細摘要1967年發表於J．ACM14（2），322～336頁。

實際上，布盧姆是受以色列學者拉賓（M.O.Rabin）的啟發而開始這方面的研究的。拉賓是希伯萊大學的教授，是研究計算複雜性問題的先驅，並在1976年榮獲圖靈獎。拉賓在1959－1960年間就發表過一些關於計算複雜性方面的論文和丘吉，可惜流傳的面較小，影響不大。但MIT“慧眼識英雄”，邀請拉賓前來講學。布盧姆當時正苦於沒有適當的課題作博士論文，聽了拉賓的講座極感興趣，當即決定沿此方向進行研究，其結果就是完成了上述博士論文。布盧姆的論文不但提出了有關計算複雜性的一些分理，而且在對複雜性類的歸納上也比其他學者有更高的抽象度。因此學術界公認，布、哈、斯三人是計算複雜性理論的主要奠基人。

2.密碼系統和程序檢驗

布盧姆除了在計算複雜性理論方面作出了開創性貢獻以外，還致力於將這一理論應用於對計算機系統的安全性和通信的安全性有十分重要意義的“密碼學”以及在“軟體工程”中十分重要而又十分困難的程序正確性驗證方面，並且取得了令人矚目的成就。1989年5月，他和同事SampathKannan在西雅圖召開的21屆ACM計算理論專題研討會上所提交的一篇論文中，首次提出了ProChecker的概念，並綜合利用密碼學、概率演演算法和程序測試、概率交互證明等手段解決程序正確性驗證這一難題，把這一領域的研究推進了一大步。有興趣的讀者可參閱他們發表在J．ACM1995年1月號上的論文DesigningProgramsthatCheckTheirWork。大家知道，Intel公司在推出其著名的奔騰微處理器Pentium。以後不久，被人發現該處理器的除法運算存在一個細微問題，從而引起了一場軒然大波。布盧姆和他的學生瓦塞曼（H．Wasserman）仔細地研究和分析了這個問題，提出了解決方案和應吸取的教訓。他們的有關論文 ReflectionsonthePentiumDivisionBug刊載於IEEETrans.onComputer，1996年4月。在軟體可靠性方面，布盧姆1997年發表的“具有運行期結果校驗的軟體的可靠性”（Softwarreliabilitywithrun－timeresult- checking,J．ACM，1997年11月，826-849頁）一文也很值得重視。

他和他的妻子——著名的計算機教授LenoreBlum與卡內基梅隆有著不解之緣，20世紀五十年代末期，Lenore就在當時的卡內基科技學院上大學念建築學。後來，1991年，他們的兒子Avrim成為了那裡計算機科學學科的副教授，也因此一家人都走進了卡內基梅隆大學。因此，Blum夫婦被譽為計算機領域的“居里夫婦”，Blum 一家也是卡內基梅隆大學的計算機世家。Blum說，“能加入這個國家最好的計算機科學系的機會是一個‘結合物’：JimMorris的盛情邀請，加上能和 Avrim以及他的家庭團聚，包括我們的第三代——Alex和Aaron，是所有這些因素把我們帶到了匹茲堡。”

到2005年秋天為止，為了從國家科學基金會（NSF）贏得價值560萬美元的信息技術研究（ITR）的承認，Blum全家把他們在計算機科學理論方面的專門技術與幾個理論工作組的同事們共享，其中包括 GuyBlelloch,DanielSleator和副教授RamamoorthiRavi。該項基金是為了幫助支持演演算法的自適應、分解與集成中心，能夠使其受這560萬美元資助的“阿拉丁（Aladdin）計劃”更廣為人知。其目標是把運演演算法則以一個更及時的方式送到那些潛在的用戶手中。 Blum 是美國國家科學院所選出的，認為在該年獨創研究方面做出了卓越、持續成就的72名新成員之一，他在國家科學院的這一當選，使卡內基梅隆大學的成員數量增加到了7名，其他幾位分別是JohnR.Anderson,StephenFienberg和 JamesMcClelland,DanaScott,RobertGriffiths以及LincolnWolfenstein。

2002年10月18日，由微軟亞洲研究院和國家自然科學基金委員會聯合舉辦的第四屆“二十一世紀的計算”大型國際學術研討會在北大百年紀念堂舉行，本次會議主題為“高信度計算”。ManuelBlum博士做了關於“慵懶的密碼學專家們是如何做人工智慧的”精彩演講。

主要內容與他們二人正在進行的CAPTCHA項目有關。CAPTCHA是“全自動計算區分人與計算機系統”的縮寫。CAPTCHA這個項目的目的是區分計算機和人類，可以把它看成是一個衛兵，它站在門口，如果要是一個人的話，那就請進，要是電腦的話，那就對不起了，別想進來。這裡邊有一點自相矛盾的地方，這個程序能夠進行這種測試，自己卻通不過這個測試。

2021年7月8日（周四）至10日（周六），曼紐爾·布魯姆參加參加2021世界人工智慧大會。

1995年，Manuel Blum獲得圖靈獎。

2021年1月14日，入選ACM Fellow。