剛剛，2023年「電腦界最高榮譽」圖靈獎揭曉——複雜性理論先驅、普林斯頓高等研究院教授艾維·維格森(Avi Wigderson)摘得。美國計算機協會（ACM）表示，表彰他對計算理論的基礎性貢獻，包括重塑人類對計算中隨機性作用的理解，以及數十年來在理論計算機科學領域的領導地位。

加上2021年獲得的阿貝爾獎，維格森教授現在一舉成為首個同時拿下數學和電腦最高獎的科學家。

（阿貝爾獎也被譽為「數學界諾貝爾獎」）。

此外，他也是2017年阿里達摩院剛成立時首批「十大祖師」之一。

業內人士紛紛趕來表示祝賀，a16z的研發主管表示：除了已有的學術成果外，也是因為他幾十年來孜孜不倦的領導力，才帶來理論計算機科學界的長青與活力。

例如，沒有他，可能就不會有西蒙斯計算理論研究所。

值得一提的是，他還在5個月前來到清華叉院作客，對當下大語言模式的發展表達了自己的看法。

複雜性理論先驅榮獲圖靈獎

身為數學家和電腦科學家，維格森最重要的貢獻就是增強了人類對計算中隨機性和偽隨機性作用的理解。

具體什麼意思？

20實際70年代末，電腦科學家已經發現：

隨機性和計算難度之間有顯著關聯。

（這裡的計算難度之高指的是那些沒有有效演算法，也就是無法在合理的時間內解決的自然問題，它們計算起來比較困難。）

通俗一點解釋就是：

對於許多難題，採用隨機性的演算法（也稱為機率演算法）可以遠遠勝過其確定性方案。

例如，在一個被稱為「1977證明」的實現中，兩位科學家就引入了一種隨機演算法，可以比當時最好的確定性演算法更快地確定一個數字是否為素數。

而在1980年代初，維格森與UC柏克萊的科學家Richard Karp合作，將隨機性的概念與那些被認為計算難度高的問題聯繫起來，也就是沒有已知的確定性演算法可以在合理的時間內解決這些問題的問題。

儘管不知道如何證明它們很難，維格森和Richard Karp還是發現了一種針對某個難題的隨機演算法，然後發現：能夠將其去隨機化，從而有效地揭示了它的確定性演算法。

大約在同一時間，其他研究人員也發現密碼學問題中的計算難度假設能夠實現一般的去隨機化。

這促使維格森思考隨機性本身的特質。

他和其他人一樣，開始質疑隨機性在高效問題解決中的必要性以及在什麼條件下它可以完全被消除。

終於，1994年，他和另一位電腦科學家Noam Nisan闡明了兩者之間的關聯。

他們證明，如果存在任何自然難題，那麼每一種有效的隨機演算法都可以被有效的確定性演算法所取代。

即我們總是可以消除隨機性。

更重要的是，他們還發現確定性演算法可能使用「偽隨機」序列——也就是看似隨機但實際上並非隨機的資料串。

換句話說：隨機性對於高效率計算來說並不是必要的。

即使在沒有隨機性的情況下，我們仍然可以使用有效的演算法來解決問題。

這一系列研究徹底改變了電腦科學家對隨機性的看法，並適用於理論計算機科學的許多領域。

今天，ACM就將圖靈獎這一重要榮譽頒給了維格森，主要嘉獎的就是他在如上領域的貢獻。

在普林斯頓高等研究院的訪談中，維格森解釋自己既是數學家也是電腦理論科學家，研究的是計算領域的數學基礎。

我的研究領域是數學的一個子域，但同時，我所研究的主要概念是計算。

對於理論計算機科學，他則認為這個學科擁有一個人對學術研究所能期望的所有優點，包含了一系列令人驚嘆的深刻且具有重要智力意義的基本問題，而這些問題對人類、科學、生活和技術都至關重要。

（看得出老爺滿滿的熱愛情了。）

而對於本次大獎，維格森則表示：

很高興看到ACM再次認可計算基礎理論，它確實對計算科學的實踐和技術發展做出了巨大貢獻。

大學被勸學計算機“好找工作”

維格森於1956年在以色列出生，是一位護士和電氣工程師的兒子。他的父親喜歡拼圖，並對數學的基本概念非常感興趣，然後經常與孩子們分享他的想法。

維格森這樣描述父親對他的潛移默化的影響：就是他讓我感染了這種病毒。

不過等他要在當地海法大學上學時，本來想主修數學的他，卻被他的父母勸導說：

選擇計算機吧，計算機好找工作！

結果他發現這個領域有很多數學問題沒有解決，於是開始吭哧吭哧解決了起來。

維格森畢業於以色列理工學院和美國普林斯頓大學，1983 年以論文《組合複雜性的研究》獲得博士學位。

他早期的一項開創性工作，就是證明了一個看似矛盾的問題：

能不能在不展示證明過程的情況下，讓別人相信一個數學論點已經被證明了。

是不是想起隱私計算領域姚期智提出的百萬富翁問題內味了。

那個問題就是兩個百萬富翁，他們想證明誰比較富有，但兩個人都不透露他們擁有多少財富。

而原本的這個問題其實是叫做零知識證明，這個概念最早在1985年由三位科學家引進。隨後由維格森以及他的合作夥伴Micali和Oded Goldreich進一步闡述了這個想法，並發現了一個意想不到的結果：如果真正安全加密是可能的，那麼NP 中每個問題的解也都可以用零知識證明來證明。

換言之，零知識證明可以用於秘密地證明任何有關秘密數據的公開結果。

數十年來，他始終活躍在學術崗位上，並且獲得許多讚譽和獎項。 1994年，他因在計算複雜性理論方面的工作獲得1994年的內萬林納

博士畢業後，他在加州大學柏克萊分校擔任客座助理教授，在IBM擔任訪問科學家，並在柏克萊的數學科學研究所擔任研究員。 1986年加入希伯來大學擔任教員。

1994年，他與Omer Reingold和Salil Vadhan一起因在圖的zig-zag 乘積方面的工作而獲得了2009 年哥德爾獎。

1999年，他加入普林斯頓高等研究院並工作至今。 2013年當選美國國家科學院院士。

2018年，他因對電腦科學和數學理論的貢獻而選出ACM Fellow。

第二年，又因為“在隨機計算、密碼學、電路複雜性、證明複雜性、並行計算以及我們對基本圖特性的理解等領域對計算機科學基礎做出的根本性和持久性貢獻”，他榮獲高德納獎。

2021年，維格森與László Lovász共同獲得阿貝爾獎。

也因為這樣根本性且持久性的貢獻，網友們得知他才獲得圖靈獎時感到意外而又驚喜，還以為他早就得了。

也有人開始看他曾經寫過的書了。

或許有眼熟的朋友嗎？

談大語言模式：最重要還是看它不能做什麼

而他與姚期智以及中國的緣分還在延續。

5個月前，他還曾親自來到清華叉院作客，帶來題為「模仿遊戲（Imitation Games）」的特邀報告。

由姚期智院士親自主持講座，並與他展開對話。

據報道，維格森從圖靈測試出發，敘述了「模仿學習」理論的沿革及其在密碼學、隨機性、離散數學、數論等領域的現代應用。

他以凱撒密碼、恩尼格瑪密碼機、選舉等案例，引導思考安全性的定義、隨機性的應用、隱私和效用的平衡等議題。

對於理論計算機研究將如何應對人工智慧發展這一問題，維格森表示，

儘管包括大語言模型在內的人工智慧有許多驚人表現，但最重要的問題是還有什麼是AI不能做的。

對於給現在正置身於科學研究的同學們，維格森也給了自己的建議。

他表示，自己曾為解決一個開放性問題花了40年時間，建議同學們要選擇自己喜歡的研究領域和話題，並享受在失敗中不斷學習的過程，這樣才能在科研道路上走得長遠。

參考連結：

[1]https://www.acm.org/media-center/2024/april/turing-award-2023

[2]https://www.ias.edu/news/avi-wigderson-2023-acm-am-turing-award

[3]https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/

[4]https://www.youtube.com/watch?v=TK_vD-VnsFw

[5]https://x.com/Tim_Roughgarden/status/1778032735849967818

[6]https://x.com/letonyo/status/1777987622301769771