好的，現在可以了。我們開始吧。好的，大家好，歡迎。多倫多大學的 University Professor，Al Borodin，將介紹演講者。謝謝。嗯…我不知道，我想我比 AI 還要緊張。我很榮幸且非常高興能介紹 2023 年圖靈獎得主 Avi Wigderson。

Avi 的開創性工作橫跨計算機科學以及純數學中最基礎的領域，這並非說理論計算科學不純粹。Avi 的工作是基礎性的，例如在 expanders、communication complexity、proof complexity、zero knowledge proofs、cryptography、randomness extraction，以及也許最值得注意的是在 arithmetic and Boolean complexity Theory，特別是在我們對 randomness 的理解方面。他跨越數十載思索的工作，給予我們強烈的證據，證明多項式時間演算法是可以進行 derandomized 的，這個結果至今仍看似違反直覺，與普遍看法相悖。我可以在這裡問，有誰沒有被 Avi 的工作在其論文和課程中啟發？

圖靈獎可以加入到 Avi 已經獲得的獎項中，他同時也是 Nevanlinna Prize 的得主（當時被視為我們領域的 Fields Medal），以及數學界的 Abel Prize，還有許多其他實至名歸的獎項。Avi 是第一位同時獲得 Abel Prize 和圖靈獎的人。

或許和他的研究一樣重要的是，Avi 作為我們社群的領導者，尤其重要的是他對我們社群中年輕和不那麼年輕成員的指導。如果你身處理論計算科學領域，很有可能 Avi 曾為你寫過教職、升遷或獎項的推薦信，或者三者都有。Avi 被要求為你寫信的可能性很高，但這並非隨機的過程，大家都想要 Avi 的意見。

我和我的妻子 Edna 認識 Avi 和 Edna 已經超過 40 年了。他們在專業和個人上的慷慨，以及在普林斯頓或以色列的熱情好客都是非凡的。Avi 和 Edna 有一個美好的家庭，三個很棒的孩子都在做自己的事情：Azi 是個釀酒師，Anat 是個創傷諮詢師，而 Yuval 則是一位數學家，Avi 與 Yuval 合作發表了三篇論文。加油，Anat 和你的丈夫今天能來這裡。

讓我分享一個關於 Avi 的個人經歷。Avi 有一個夏天在多倫多訪問，我們有一次去了水上樂園。認識 Avi 長子 Azi 的人知道他會做大多數人連想都不會去想的事情。樂園裡有一個非常高、非常陡的滑水道，而 Azi 那時七歲，當然滑了幾次那個滑水道，並鼓勵 Avi 也滑。這就是那種非常高階的滑水道，你滑下去時會騰空，感覺像是只有一秒鐘，但又像是永恆。我不知道 Avi 是否想滑這個滑水道，但最終是愧疚感或忠誠心（你自己選是哪個）驅使他去滑了。他滑了，並且活下來了。也許這就是為什麼他在研究中如此願意冒險，致力於計算機科學中最基礎的問題。

請歡迎 2023 年圖靈獎得主，Professor Avi Wigderson。

謝謝。謝謝 Al 的介紹。我很高興能在這裡，STOC 確實是我的家園社群。我從 1980 年代開始就來這裡參加 STOC 和 FOCS 會議，雖然不像 Al 來得那麼久，但可能比你們大多數人都久。這是一個很棒的地方來發表這次演講。

我想和你們分享我過去六個星期準備這場演講的經驗。我有一個絕妙的主意，你知道嗎？圖靈獎演講該講些什麼？為什麼不講講 Alan Turing 呢？而且，你知道嗎，像你們許多人一樣，我以為我知道他，我讀過他幾篇著名的論文，而且我所知甚多。然後我開始閱讀，我發現我有多麼無知，我將分享一些我學到的東西。

我完全不會談論他的個人生活。這方面有很多可說的，他的生命很短暫且悲劇收場。我只會談論專業方面的事情。這大致上是他的學術履歷，他在各個時期待過的地方。我將只談論每個時期的一到兩篇論文。我將分享我在閱讀時所想到的，關於我們的社群如何運用他的這些想法。他在許多主題上都有深刻的思想，主題的多樣性令人驚訝，你們今天會看到一些。是的，我想他會很喜歡看到我們現在正在做的事情，而我們顯然是受到他當時工作的啟發。

我將不會提及很多事情。我可以談一個小時、三個小時、五個小時關於我讀到的內容，但我只有一個小時。我不會提及任何實際應用的事情，例如他在建造電腦方面的工作，整個電腦演進史；他在程式設計和程式實踐方面的工作，這方面他的思想和寫作非常驚人；他在學生時期關於 Central Limit Theorem 的工作；他在數值分析方面的工作，他發明了 decomposition 和 condition number，你們可能不知道；他在加密方面的工作；他在程式設計西洋棋方面的工作；以及他對 Riemann Hypothesis 的執著（你們最後可以問我）。我不會提及這些，因為我沒有時間。

劍橋時期：可計算數與不可判定性

讓我從第一個時期開始，他在劍橋的時光。這裡我想談論最明顯的候選人，這大概是我將花最長篇幅討論的論文，即使你們可能對它最熟悉：《On Computable Numbers, with an Application to the Entscheidungsproblem》。這可能是對世界影響最大的數學論文。他聽了 Max Newman 的課程，Newman 是一位拓撲學家，對基礎論感興趣，他向學生描述了 Hilbert 的夢想，即為數學建立堅實的基礎。所以你想要有一個理論，並證明它確實是基礎。你想說它是完備的（任何可證明的東西都能被證明），它是一致的（沒有矛盾，否則任何命題都是平凡的），而且如果某樣東西是可證明的，存在一個機械程序（他的德文原文如此）來生成證明。當然，眾所周知，Gödel 擊敗了前兩個，而 Turing 在這篇論文中擊敗了第三個，那就是 Entscheidungsproblem，判定問題。他證明了這是做不到的。所以他徹底摧毀了 Hilbert 的夢想，這是最後一擊。

但是，你知道，他寫完這篇論文後把它帶給了 Max Newman，而 Max Newman 幾週前剛收到普林斯頓的 Alonzo Church 的一封信，其中有一篇論文證明了相同的結果：不可判定性結果。作為一個好的導師（他終其一生都是 Turing 的好導師），他做了兩件事：首先，他身為 London Mathematical Society 的編輯，他說「是的，這個結果已經知道了，但這裡有一個完全不同的證明，我們需要發表它」。他也寫信給 Alonzo Church，寄給他 Turing 的論文，支持 Turing 的觀點，並且知道當時普林斯頓是這個邏輯基礎工作的大本營，他請 Church 接受 Turing 作為研究生，Turing 後來就去了那裡。

Turing 以及所有致力於這個問題的人必須問自己的主要問題是：什麼是計算？什麼是機械程序？這是一個問題，你知道，幾乎是最基礎的問題了，很難想到比這更基礎的。這個詞是什麼意思？任何人的意思是？人們自然地提出了建議。Gödel 和 Herbrand 以及其他人提出了遞歸函數的概念。Church 在 30 年代早期發展了 Lambda calculus，並認為它捕捉了計算的概念。而 Turing，眾所周知，提出了一個完全不同、完全基礎、令人驚嘆且優雅的模型。值得注意的是，一發表出來，Church 和 Gödel 都說 Turing 的模型才是正確的模型，他們立即認識到它是捕捉計算的最自然事物。Church 實際上是命名它為圖靈機的人。

這確實是一篇經典的 STOC 論文。它引入了一個全新的模型，現在你必須論證它確實捕捉了計算的概念。Turing 在許多其他論文中一樣，詳盡地解釋了這一點。首先，你想論證這捕捉了任何可計算的事物。他提供了三種不同類型的理由。一是它模仿了「計算機」的工作方式，「計算機」當時是指一種人類職業，指進行計算的人，主要是女性。他認為他能想到這一點的原因是他認為「我們」就是這樣計算的，也許是在一張畫滿方格的紙上。他將其簡化為一維（你們都知道整個故事）。這是一個解釋。第二個是讓我展示如何計算任何數，任何無限實數，例如像布林函數、Pi、e，許多其他的，例如 Bessel functions 這些。他提供了計算它們的程式。第三個是，他知道 Church 使用不同的框架證明了不可判定性，他展示了這與 Church 的模型是等價的，實際上也與 Gödel 的模型等價。所以正如我們所說，一個好的模型如果能與其非常不同的表現形式等價，那就是好的。

這當然是我們領域的誕生。這就是我們有了計算機的數學模型，所以我們可以做數學了。不僅如此，複雜性理論已經嵌入在這個模型中了，因為對「時間單位」和「空間單位」存在明確的數學精確概念。所以我們可以定義這些類別，就像 Hartmanis 和 Stearns 所做的時間類別一樣。我們可以精確地計算一個演算法花費多少時間，當然這些只是第一個複雜性類別。從那以後，我們有了 Scott 大約 20 年前開始維護的兩個類別。

主要結果是不可判定性結果。正如你們都知道並在大學部課程中學到的，他證明了沒有演算法可以解決 Halting problem，這用通俗的話來說，對任何編寫程式的人意味著你無法偵錯。沒有辦法總是自動偵錯電腦程式。我喜歡 Christos Papadimitriou 解釋這一點的方式，他說計算機科學誕生於此，而且它誕生時就已經意識到自己的局限性。計算機無法解決所有問題，實際上這個領域的主要問題就無法由計算機解決。這與物理學不同，物理學誕生後幾千年才發現不確定性原理或熱力學第二定律，他們必須發現量子力學或其他局限性。

我覺得課程中沒有足夠強調的是，它的影響有多大，這很難低估。它對數學產生了驚人的影響，數學總是計算性的，我一直堅持這一點，從 Euclid 開始，數學家就是計算機科學家。但這產生了驚人的影響，因為它提供了一種方式來說明你何時能理解一個數學問題，你能否將定理放進這個理論中，這個理論中的基本定理。Hilbert 相信一切皆有可能，但現在這不再顯而易見了。所以人們開始設計演算法，這些是可判定性的證明。有些基本問題是可判定的，例如 Tarski 發展了他的 Quantified 理论，人們發展了數學中的技術和結構來證明可判定性結果，例如實數的一階理論，Tarski 發展了 quantifier elimination，一個非常基礎的技術。Haken 發展了 normal surfaces 的理論來證明決定一個結是否為 unknotted 是可判定的。

另一方面，從 Turing 開始，其他人則去證明數學中的基本問題是不可判定的，這與計算無關。這些是 word problems，從 semi groups 開始，然後著名的是 groups，以及 70 年代的結果（這花了一些時間），因為這些問題到 Halting problem 的歸約更為複雜。但是的，多項式方程式通常無法求解。

Turing 開發的技術，我們當然可以立即使用。當然，在論文中，他提出了「程序即資料」的概念，因此我們可以將程序視為其他程序的輸入，因此我們可以進行對角線法，我們可以進行模擬，我們可以進行對角線法。這是一種證明技術。儘管他將其用於不可判定性，但他強調這種模擬是有效率的。他說，在通用機器上運行一個程序，不會比在它自己的機器上運行花費更長的時間。所以這又被 Hartmanis 和 Stearns 用來證明時間階層定理：更多的時間讓你計算更多的函數，更多的空間讓你計算更多的函數。然後這被更複雜地擴展，例如 Cook 的非決定性時間階層，以及一個我不知道這裡有多少人知道的結果，那就是 P vs NP 問題的線性時間版本：在線性時間上，非決定性讓你獲得更多能力。無論如何，這是 Turing 提出的，它開始在各地被使用，直到今天。

有一件事我覺得許多人並未認識到，我其實在週六問了 Scott Aaronson，他也不知道，那就是非決定性（nondeterminism）。它從何而來？誰先引入了它？顯然是 Turing。他在論文中說：「看，我定義的機器是完全確定的，下一步直接由當前狀態決定，我稱這些為自動機器（a-machines）。但還有一個段落，他後來沒有繼續探討，但他說『我們可以考慮另一種版本，選擇機器（c-machines），其運動僅由當前配置部分決定，存在一些選擇，而某人必須做出這些選擇。』」他不僅在這裡定義了非決定性計算，而且告訴你原因。為什麼？因為這捕捉了證明系統中發生的事情。這就是證明有效驗證的本質，這就是非決定性機器中發生的事情。

當然，這種計算與驗證、非決定性與決定性之間的對比再次被我們的領域所採納。我會說，在我們的領域，Cook 是開啟 NP-completeness 的人中最符合邏輯的一位。他關於 NP-completeness 的論文實際上稱為《The Complexity of Theorem Proving Procedures》。後來與 Russell Impagliazzo 合作的論文，最後一節是關於證明系統，他介紹了這種方法來處理命題證明系統，並基本上指出，世界上所有證明系統，所有數學書籍中的證明系統，都有一個共同點：驗證必須是有效率的。Cook 和 Levin 的結果可以被視為分離了計算與驗證這兩個概念，在有限演算法的情況下。

當然，從那時起，我們一直在努力證明這種有效率的類比，即將有效率的驗證與有效率的計算分離開來。我認為這個領域最偉大的成就之一不僅是研究這個問題，而且將有效率驗證的概念擴展到驚人的多樣性，包括互動式驗證、機率式驗證、量子驗證。有一系列驚人的工作，以及所有先前的相關工作，在這些工作中，我們不僅理解了不同證明系統的概念，而且對它們的計算能力進行了精確的刻劃，除了 NP 以外。而對於 NP，我們有 PCP theorem，這是一個相當好的替代方案。

我可以談論這篇論文更多，但我應該停下並轉到 Turing 生活的下一個階段。如果你們都覺得可以，最後再問我問題。Valerie 答應我最後有無限的時間提問。

普林斯頓時期：諭示機與複雜性階層

好的，正如我所說，Turing 從劍橋去了普林斯頓，與 Church 一起攻讀博士學位。那裡是邏輯學的中心，Church 在那裡，Kleene 和 Rosser 是他的學生，並繼續建立可計算性理論。Recursive Theory 也在那裡。John von Neumann 也在那裡，他對 Gödel 的工作和 Turing 的工作非常感興趣。當 Turing 在那裡時，Gödel 部分時間也在那裡，但他與他們的互動並不多，我想是的。他甚至提到了這點，但讓我跳過。

總之，他寫了一篇博士論文，題為《Systems of Logic Based on Ordinals》，他在其中試圖研究不可判定性或不完備性是否能有所突破。例如，如果你給你的計算機解決 Halting problem 的能力，那麼也許它就能解決所有問題了。於是，他引入了我們都知道並喜愛的 oracle。他說：「讓我們假設我們被提供了一些解決數論問題（如 Halting problem）的未指定方法，姑且稱之為一種神諭（oracle）。藉助這個神諭，我們可以想像一種新型機器，稱之為 O-machine，其基本運算之一就是向神諭發出查詢。」他不僅引入了這個概念，連我們現在使用的名稱也是他取的。

它對 recursion theory 和可計算性理論產生了巨大影響，早於複雜性理論。不過，Turing 的學生 Post 你們會在下一頁看到（事實上，是 Emil Post），總之，他提到了 Turing 在這篇論文中引入了一種他們都知道的技術，這基本上展示了你也可以對 oracle 機器進行對角線法。這被用來建立不可解性階層，Turing-Gödel 或 arithmetic hierarchy。Arithmetic hierarchy 最初是由 Kleene 根據邏輯公式中量詞的數量定義的，但後來 Post 意識到它可以用 oracle 來定義。所以你真的定義了第 i 級是通過給基本機器前一級的 oracle 來實現的。利用 Turing 的技術，我們知道——他們都證明了——所有的類別當然是向上包含的，並且所有的這些類別都是不同的。

我們知道在我們的世界裡，這種有效率的版本在 70 年代由幾個 STOC 成員引入，Myers 和我，這就是 polynomial time hierarchy。它看起來完全一樣，通常帶有一個上標 P，底部是 P、NP 和 CoNP。與之對比的是，我們沒有分離，我們沒有單一的分離結果。但我們有關於我們失敗的解釋，所以 oracle 不僅被用來定義這些類別，它們也被用來提供解釋。正如你們肯定都知道的 Baker-Gill-Solovay 的基礎論文，它問道，為什麼 Adleman、Cook 等人的結果距離證明 P 不同於 NP 還有差距？答案是，你可以用不同的 oracle 使 P 等於 NP 或不等於 NP。而對角線法/模擬/對角線法的技術無法區分這一點，所以你無法使用這些技術。這是第一個 barrier result，我們當然成為 barrier results 的愛好者。

進行自我反省，我認為這是我們社群另一個非常重要的特質：我們進行自我反省，當我們未能做成某事時，我們會尋找解釋，而不僅僅是轉向其他問題。所以我們有這些解釋，這些解釋當然非常基礎且有用，因為我們試圖收集特別是在證明下界時使用的技術，看看它們做不到什麼。就像 Baker-Gill-Solovay 的 barrier 一樣，還有 Razborov 的 natural proofs 和 Impagliazzo 和 Rudich 的 algebraization。從理解這些 barrier 中，有時我們可以超越它們，有一些顯著的結果，尤其是 Ryan Williams 證明了 ACC 的下界。然後我們又卡住了，我們發明新的 barrier，希望最終能繼續取得好的結果。

二戰時期：密碼學與機率統計

好的，我想轉到 Turing 生活的下一個階段，那就是二戰時期。正如你們肯定也知道的（從電影裡），他在戰爭爆發時正在 Bletchley Park 度過他的時光。他其實在前一年參加了一個密碼破解課程，然後去了 Bletchley Park，被分配到著名的 Hut 8，他們被指派去破解海軍的 Enigma 密碼。德國陸軍不同部門使用了許多不同的 Enigma 機器。

而著名的結果是他們破解了密碼，Churchill 稱之為「二戰勝利的最大單一貢獻」。這絕非易事，因為一戰確實不幸地是一場偉大的戰爭。主要問題是，德國佔領了歐洲大部分地區後，英國完全依賴從美國運來的食物、補給、彈藥和武器的護航船隊。所以有護航船隊將這些東西從美國運往英國，而大西洋充斥著 U-boat。戰爭開始時有 60 艘，戰爭結束時大約有 400 艘，每個月都有許多船隻被魚雷擊沉。這是一個驚人的問題。我無法想像那些知道這件事並必須進行防禦的人面臨的壓力。你可以將其視為兩種機器之間的戰爭：Enigma 加密機和所謂的 Bombe 機器，Bombe 實際上最初是由波蘭數學家設計的，在戰爭開始前一個月，相關知識被帶到了法國，然後英國情報部門在 Bletchley Park 改進了它。這台機器基本上就是進行暴力破解搜索的電動機械機。

我肯定直到過去六個星期才知道這其中蘊含了多少理論。儘管有所有這些壓力，Turing 對此抱持著原則性的方法。搜索在某種程度上是有指導的，你需要根據一些被解密的加密訊息來調整你的偏見。你如何做到這一點？嗯，你必須為此建立一個理論，這就是他思考的方式。

所以我要告訴你們他對機率論、統計學和資訊理論的一些基礎性貢獻，這比其他人在後來做類似事情要早得多。我將告訴你們 Turing 的論文，但實際上沒有這樣的論文。有一些在 80 年代後期發表的筆記是他當時描述的東西，這是因為戰爭的保密性。但是 I.J. Good，他在戰爭開始後大約六個月或一年去了 Bletchley Park 和 Turing 一起工作，寫了很多關於這些理論的東西。我引用的雖然是 Good 的論文，但我將告訴你們關於對「證據權重」和「估計族群頻率機率」的兩項貢獻，因為 Good 親口告訴你這些工作有多少是 Turing 做的。

這是引用他 53 年的一篇論文：「下一頁我將展示的公式是 Dr. Turing 幾年前連同一個直覺的證明一起向我提出的。因此，本論文絕大部分的功勞應歸於他，我非常感謝他允許我發表這項工作。」關於證據權重，也有一樣的情況，這是關於族群頻率的。關於證據權重，在他生命接近尾聲時，Good 寫了一篇關於這項工作的調查，其中他基本上告訴你，「然後 Turing 來了，向我展示了這個定理，然後他向我展示了這個定義，然後他告訴我…」這真是了不起。

所以讓我告訴你們這兩件事。我會講得很快，可能你們捕捉不到所有的細節，但你們會明白他當時的思想類型，這些思想有助於破解 Enigma。

一個是關於估計族群頻率的問題。這是一個你們都知道如何解決的非常基礎的問題。我給你一個來自某個字母表 D 的 N 個 IID 樣本。我問你下一個樣本是一個在樣本中出現 K 次的項目的機率是多少？你想估計 P(K)，即看到一個在樣本中出現 K 次的項目 s 的機率。你的答案會是 K/N。或者我的答案會是 K/N。這有什麼大不了的？但大不了的是，這是一個我們通常不會考慮的情景，其中的字母表像是所有德文單詞。字母表遠大於樣本。事實上，你沒有看到宇宙中存在的大部分項目。那麼你會給出什麼估計？現在就不清楚了。這就是公式，它被稱為 Good-Turing 估計量。

它看起來是這樣的：如果你有 N_k 種物種或項目出現 K 次，那麼這就是公式。它乍一看非常違反直覺。與其使用 K/N，你使用 (K+1)/N，所以在某種程度上給出了一個更大的數字，但你卻以看到出現 K+1 次的物種數量除以看到出現 K 次的物種數量作為權重。思考一下。他們理解到，你應該也對其進行平滑處理。據我所知，他們沒有證明任何關於此事的定理。第一個證明它最優的論文在 2015 年才發表。所以這是你能得到的最佳估計，無論分佈 D 是什麼。這看起來有點奇怪，因為如果你知道 D，你就確切地知道，但你不知道確切的情況。也許分佈對兩個項目賦予了不同的機率，但它們都在樣本中出現了 K 次。總之，這就是最佳估計。

再來，思考我們在這個領域所做的事情。顯然我們做了很多。理論計算機科學與統計學在分佈檢測和學習領域的聯繫越來越緊密。我們有像這樣的實例最優結果。我們有針對錯誤的穩健結果，而且有很多很多美麗的工作。

第二個是他們稱之為證據權重（weight of evidence）的東西。你們會立即認出來。問題是什麼？有兩個可能的分佈你想區分。你從 P 中得到一個樣本 X。問題是，你從中獲得多少資訊，讓你相信它實際上來自 P？它證實 P 相對於 Q 的程度有多少？於是他們提出研究這個特殊的隨機變數，他們稱之為 W，即 log(P(X)/Q(X))。當然你們認得這個。他建議研究這個分佈。這很熟悉，因為這個分佈的期望就是我們現在稱為 KL Divergence 的東西，KL Divergence 是很久以後才定義的。但我一直以為期望就是一切，還有 KL Divergence。但實際上，Turing 和 Good 研究了高階矩，他們得到了關於這些高階矩的驚人且美麗的定理，這些定理至少在我們社群中是不被教授的。

這些理論有些構成了所謂的序列分析（sequential analysis）的基礎，這是 Abraham Wald 在戰後發展起來的一種理論。序列分析基本上是你樣本大小不固定時該怎麼辦，你會獲得越來越多的樣本，你必須更新你的工作。這是統計學的基本定理，其中許多定理在戰爭期間已經由 Turing 和他的合作者證明了。當然，是的，這對破解 Enigma 和發展 Good 和 Wald 後來寫了數十篇論文的理論都產生了巨大影響。

戰後曼徹斯特時期：人工智慧與形態發生

我的時間怎麼樣？我本來預計… 不，我會繼續。我會在一個小時內結束。

好的，我想轉到 Turing 生活的下一個階段，那是二戰後的時期。正如我確信你們知道的，Turing 去了倫敦，實際上住了三年，試圖建造 ACE 電腦，當然是設計它，然後由於沮喪而離開了，因為政府和工程師們對這些想法並不太熱情，他們認為它們太複雜了。總之，他去了當時在曼徹斯特的 Max Newman 那裡，試圖建造自己的電腦，這後來成為曼徹斯特 Baby 電腦以及曼徹斯特系列電腦。

我學到的一個軼事是，1953 年，他被任命為計算理論的 Reader。所以這，我認為是一個 Reader，當然在英國他是 Professor。這是一個享有聲望的職位，當時獲得了巨大的薪水增長。我知道這是在他去世前一年，也是在他受審判後一年。你知道嗎，對於英國法庭判處他進行化學去勢，大學卻完全忽視了這一切，他們晉升了他，並給了他這個職位。

我想談談這個時期的兩篇論文，這也將是演講的結尾。其中一篇你們都知道也聽說過，這是他關於人工智慧的論文。他寫了幾篇論文，實際上也做了幾場演講，甚至在 BBC 上進行了關於機器和智能的演講和辯論。我想談談這篇論文。我會提到模仿遊戲，你們都知道模仿遊戲，當然是從電影裡，很可能在電影之前就知道了。但我想告訴你們這篇論文中我完全不知道的其他內容。

首先，他引入了機率演算法（probabilistic algorithms）。這也是他思考過的事情，它出現在以前的其他論文中，非常清楚。我接下來告訴你們的這些內容都是為了論證認為機器能夠思考並非不合理的想法。他實際上準備了對潛在批評的完整答案集，他知道他會收到這些批評。他的另一篇論文叫做《Heretical Theory of Machine Intelligence》。總之，這裡他清楚地說：「數位計算機概念的一個有趣的變體...」你在讀這些論文時必須想到，當時沒有計算機，沒有實踐，什麼都沒有，他在其他人之前就思考過這一切。「...是引入一個隨機元素的概念。」所以指令可以是「投擲一枚骰子，將結果放入第 1000 個儲存單元」。在其他論文中，他也提出了（這裡也提到了）也許是電子過程。在其他論文中，以及實際上他設計和建造的設備中，他使用熱噪聲，你知道，與鐳相關的隨機性。他提出了所有這些其他的想法來生成隨機性。所以他也思考過這一點。

他也思考過偽隨機性（pseudorandomness）。他在同一篇論文中說：「從觀察機器中判斷它是否含有隨機元素通常是不可能的，或者可以透過讓機器做出依賴於 pi 的數字的選擇來產生類似的效果。」所以他已經告訴你這裡有一些可能是偽隨機的，你無法區分這與真正的隨機性。不僅如此，這個引用在著名的 GGM 論文（Goldreich, Goldwasser, Micali）關於偽隨機函數的論文中已經被引用了。他們注意到了這一點，而且這與他們的論文精確地契合。他說了以下這段話：「我在曼徹斯特計算機上設置了一個小型程序，只使用了 1000 個儲存單元，當它被提供一個 16 位數字時，它會在 2 秒內回覆另一個 16 位數字。我將挑戰任何人從這些回覆中學習到足夠關於程序的資訊，以預測下一個值。」這就是偽隨機函數的定義！他當然是利用這一點來論證機器可以是不可預測的。你知道，在許多與他人的爭論中，人們說機器是完全可預測的，他們可能想到了算盤吧。總之，他已經在這篇論文中提出了這一點。

他提出的另一件事，在當時也是完全激進的。世界各地所有人都正在建造計算機，目的是什麼？主要是軍事用途。IBM 也為企業建造計算機，但都是為了計算。而 Turing 卻認為「不，我們應該教它們，它們應該學習，我們應該教育它們。」他談了很多關於這件事。他對機器可以擁有的儲存量非常著迷，認為這是為了思考。他對生物學家、人類大腦的大小、它有多少記憶體非常感興趣。他向所有人解釋說，機器之所以可以預測，是因為如果你讓它們乘以兩個數，它們就會給你結果。它們怎麼能學習呢？但他接著說，它們學習的方式非常簡單，因為它們可以改變自己的指令。他當時就已經這樣思考了。人們當時並非如此思考。

這又是在爭論中。人們說機器總是產生可重現的結果，而且你不能容忍它們犯錯。他說：「如果我的機器被期望是無誤的，它就不可能是智能的。」他已經開始思考我們應該考慮學習並允許機器犯錯。他不僅談論從經驗中學習，所以他用兒童學習類比說：「好吧，我們出生時有一個大腦，這是初始心智狀態。然後有兩種經驗，一種是我們被長輩教育，另一種是我們自己體驗世界，也許是隨機的。」

我在準備這場演講時想到了一件有趣的事。我拿到了 Valiant 的新書，關於 Evolvability，他明確地說道，Turing 當然知道這一點，Turing 談論了機器的教育，這在學習理論中並沒有被太多地探討。當然，我們有很多關於從分佈中學習的理論等等。事實上，我當時正在思考 Valiant 之前關於 Circuits of the Brain（20-25 年前）的書，以及關於 PAC Learning 的理論和書，我當時想，Turing 如果看到 Valiant 以及許多其他人如何將這些想法發展得如此精緻和深入，他一定會非常高興。

終於，我談到了 Turing test，模仿遊戲。他以他優美的風格寫道：「我們如何研究『機器能否思考』這樣的問題？」他說，「嗯，有一個自然的方法。我可以為你定義什麼是機器，我可以定義什麼是思考。然後你會開始與我爭論你不同意這個定義，然後我們就沒有進展了。所以，讓我建議別的東西。讓我們只測試一台機器是否思考。」

第一個想法基本上是客觀的、哲學性的、本體論式的風格，但這些定義可能不被同意，可能無法測試，可能無法證偽，可能沒有普遍意義，等等。相反，他提出了一種主觀的、行為主義的定義。這可以被精確化、可測試、可操作、有用，而且，你們會看到，具有革命性。

那麼，模仿遊戲是什麼？你們都看過了。你想比較兩種情景，兩個對象，在本例中是一個人和一個機器人，你想測試也許是智力，或者也許是交談的能力。你想像有兩個房間，一個測試者，在本例中是一個人，他不知道這是哪個房間，與這個對象交流，然後他給出一個介於零和一之間的數字，比如他說「我認為這是一個人類」。一個數字，這個數字在左邊是 P0，在右邊是 P1。如果無論測試者怎麼做，他們可能會給出不同的數字，但只要這兩個數字 P0 和 P1，這兩個房間對測試者來說看起來幾乎完全相同，對每一個測試者來說都一樣，那麼你就說它是不可區分的，然後你就說這個對象，在本例中是機器人，通過了測試。

關於這個問題，有很多很多爭論，寫了許多書，關於 Turing 模仿遊戲的爭論不休。我不想談論這個。我想談論我們用這個做了什麼。我們愛上了模仿遊戲，有時甚至是潛意識地。我們有很多精確的模仿遊戲。我們基本上採用了這個範式：不可區分性範式（indistinguishability paradigm）。如果兩件事不能被一個合理的測試區分開來，那麼它們就是相同的。合理性必須參考其所處的環境。

關於這一點，我認為對於 Turing 以及這個領域所有工作的一個關鍵點是，通常最重要的步驟是定義正確的概念。一旦你有了正確的概念，你知道其餘的理論、證明、構造就會自然而然地產生。在這種情況下，我將在一兩分鐘內展示這個特定範式——模仿遊戲範式——的力量，以及它如何促成了這種驚人的，無論是科學的、數學的、技術的，還是社會的影響，在密碼學、偽隨機性、隱私保護方面。你們都見證了這一切，但也許不是以這些圖景呈現的。我想將它們全部展示為模仿遊戲。

這裡的核心概念，在密碼學中，最基本的概念是在 Goldwasser 和 Micali 這篇奠定密碼學數學基礎的開創性論文中提出的。你如何判斷一個加密方案是否安全？「給我兩個不同訊息的加密結果，任意兩個不同的訊息，並將它們提交給任何多項式時間測試。如果沒有任何測試可以區分它們，那麼我們就稱它為安全的。」這看起來是一個非常強的定義。當然他們也證明了在 factorization 是困難的前提下，這是可以實現的。這很驚人。從這個定義中可以推導出很多東西。例如，加密必須是機率式的這一事實，如果你是確定性的，你會試圖加密兩者，看看哪個匹配。總之，安全加密就是這樣定義的。

事實上，密碼學中的幾乎每個概念都是通過模仿遊戲定義的。如果你想知道一個協議是否安全，比如多方計算，你想知道一個選舉協議是否安全，你只需將它提交給一個模仿遊戲，與某個理想情況進行比較。理想情況是什麼？理想情況是擁有一個可信第三方，我出於某種原因稱之為「政府」，但… 我確定你已經注意到了，這不是正在發生的總統辯論，也許他們正在討論類似的事情。

你只需要比較協議與理想情況，允許一個有效率的演算法觀察參與者的狀態（其中一些可能是惡意的），並觀察在理想情況下和在協議中的通訊。如果你無法區分，那麼你知道你不能… 那麼它就是理想的。看起來相同的兩件事就是相同的。

偽隨機性（pseudorandomness），我們如何定義一個分佈（比如這些古老的硬幣）是偽隨機的？簡單地說，讓任何演算法，任何有效率的演算法，用它們做任何想做的事情，並產生一些東西。如果它的行為就像這些金幣一樣，就像均勻分佈一樣，與均勻分佈不可區分，那麼我們就稱它為偽隨機的。你們知道後來發生了什麼。

隱私保護。目前差分隱私（differential privacy）的開創性概念，同樣是一個模仿遊戲。是否存在一種方法來過濾資料庫以便進行各種查詢，使其具有差分隱私？你只需要設置一個模仿遊戲，說「這裡有兩個資料庫，它們只有一條記錄不同」，也許是 Jane 的記錄，但在單一記錄上，這是相鄰的資料庫。對於任何一對相鄰的資料庫，對於過濾後允許的任何查詢，答案都必須是不可區分的。如果答案是不可區分的，那麼 Jane 就應該高興她的資訊不會洩露。

所以這又是一個模仿遊戲。在一個更長的演講中，我可以給出更多例子，我會更多地談論這些模仿遊戲。你可以將 Szemeredi's Regularity Lemma 描述為一個模仿遊戲，還有許多其他概念。

生物學與跨學科影響

總之，我想轉到最後五分鐘，講述 Turing 寫的最後幾篇論文之一，也是在曼徹斯特完成的。這是一篇生物學論文，題為《The Chemical Basis of Morphogenesis》。我想知道有多少人聽說過這篇論文？請舉手。好的，非零數量，但可能更多人沒聽過。所以這不僅僅是一篇生物學論文，這是生物學中最常被引用、參考次數最多的論文之一，約有兩萬次參考。

它討論的是一個問題，你們知道… 我已經告訴過你們他討論過許多其他問題，但這個問題似乎真的離得很遠。他思考的大部分事情，如果你讀他的生平，你知道他對大自然非常感興趣，他是一個非常熱心的化學家，他有一個實驗室。他做了很多實驗。他寫了一篇論文解釋以下這個問題。這是生物學中最基本的問題之一。你們看這張圖，你們會說：「這裡有些不對勁，對吧？」這條斑馬怎麼會變成這樣？畢竟，斑馬、所有哺乳動物以及許多其他生物都來自一個完全對稱、同質的開端——一個受精卵。你們如何得到這些條紋？我不知道，腿、頭、尾巴、身體方向。這不僅僅是從對稱中產生非對稱，這不僅僅是非對稱，所有斑馬都看起來一樣，對吧？你們認得斑馬，或者你們認得人。所以這實際上是關於一旦有了對稱性，不同的結構如何以及會產生什麼樣的不同結構的問題。

我不知道，如果我面臨這個問題，我會不知道該怎麼辦。我會轉向 P vs NP，那看起來比較容易。而 Turing 卻這樣做了。我覺得這真是令人難以置信。

好的，我會稍微說一下，歡迎你們自己閱讀。他也非常大膽。在一個章節中，他描述了一個「生長胚胎的數學模型」。好的，生長胚胎。這個模型將是一個簡化和理想化，因此是一種對現實的扭曲。希望其中保留下來供討論的特徵，在目前知識水平下，是最重要的。考慮到這篇論文的參考次數，是的，這個希望實現了。

他給了更長的描述。他稱這種「形態發生」（morphogenesis），即從同質中產生這些實際結構的過程，他稱這個理論為… 嗯，它基於化學物質，他稱之為「形態發生素」（morphogens）。這個系統被稱為「反應-擴散」（reaction-diffusion）。我稍後會解釋。讀他的文字真是一種享受… 是的，他說「我們將在一個孤立的細胞環的情形下詳細考慮它，這是一個數學上方便但在生物學上不尋常的系統。」但是，這項研究關注的是不穩定性的發生，以及從初始同質狀態的轉變。他找出了六種基本上不同的長期結構形式，其中包含圖案。例如，stationary waves，我們會看到。

模型是什麼？模型就是一個細胞環，其本身完全同質。他考慮了離散和連續兩種設定，並對兩者進行了數學分析。一個狀態就是每個細胞中不同化學物質的數量。這就是狀態。我告訴你，這個細胞裡有 9 毫克 A 和 2 毫克 B，等等。這個過程的演變是通過反應和擴散。反應發生在細胞內部，是細胞內化學物質之間的化學反應。擴散發生在一個細胞內的濃度與另一個細胞內的濃度不同時（比如化學物質 A），就會以一定的速率發生一些擴散，使它們趨於相似。這是唯一的輸入。當然，初始狀態下，你在每個細胞中給予相同量的化學物質，所以它是完全同質的。

然後他說，現在，演化是什麼？這真是驚人，你看，我們可以將其視為計算視角應用於科學（在本例中是生物學）的一個絕佳範例。他解釋說，這基本上就是一台計算機。從一個狀態，我們通過一個簡單的局部規則得到緊隨其後的狀態，無論細胞內部以及兩個不同細胞之間發生什麼。而且，正如我所說，數量在細胞內的反應中發生變化，但最初它們都是相同的。然後通過細胞之間的擴散，他唯一的論點是，這種穩定的平衡，這個平衡是不穩定的。如果存在微小的差異，當然不會是精確相同的數量，那麼就會發生一些不穩定性，然後在長期內，不僅對稱性被打破，結構也出現了，你可以實際量化和描述它們。讓我通過圖片向你們展示。

他實際上不僅考慮了細胞環，也考慮了球體，三維模型，以及一個網格（lattice），他對它們都進行了研究。事實上，他發明了細胞自動機（cellular automata），早於其他人。在二維模型中，他解釋了所謂的向光性（phototaxis），這是一種現象，比如為什麼葉子會朝某些方向生長而不朝其他方向。他對松果和斐波那契數列著迷。事實上，他研究細胞環模型是因為觀察這種水螅（Hydra），這是一種微小的海洋生物。如果你切斷它的莖，那麼在切口處就會重新長出觸手。所以當你切斷它時，它就像一個環。他問，為什麼觸手會從這個地方長出來而不是那個地方？它是同質的。他在三維情況下解釋了這個問題。

他對胚胎非常感興趣，正如你們中肯定有些人知道的，特別是作為父母的你們。受精卵最初並不立即發展，細胞會分裂一段時間，然後形成一個同質的細胞球，這就是囊胚（blastula）。然後在某個地方發生原腸形成（gastrulation），對稱性被打破，方向形成了，基本上是脊椎的方向。那麼這是如何發生的呢？他有這個模型可以解釋原腸形成。

他真正感興趣的第三個對象是斑點和斑紋的形成，比如這些斑馬。他在數學上並沒有分析這個，但他在曼徹斯特計算機上模擬了，比如牛身上的扁平部分（dappling）。他為此保留了計算機時間，每週日晚上和每週四晚上，他獨自使用計算機，整晚都在進行模擬，編寫程序，並通過模擬生成了這些圖案。

總之，我們用這些做了什麼？是的，我們也在這裡跟隨他。當然，我們許多成員都在進行合作，將計算觀點引入生物學、經濟學——今天早上 Mical Feldman 做了一場很棒的演講，關於契約和計算機科學的交叉點——社會科學、物理學、數學以及其他任何領域。存在著合作，存在著交叉授粉。

我認為我們僅僅看到了開始。我們對這種合作的了解僅僅是開始。我確信其中一些領域非常古老，比計算機科學古老得多，有些領域很保守，不習慣將他們的系統視為計算或資訊過程。但現在，我們領域的理論和方法已經非常精緻和深入，我們擁有一種理解，可以並且正在對許多科學家有用，特別是在建模和分析方面。是的，我確信我們將看到更多這方面的成果。

好的，讓我在此結束。是的，這有點難以總結。我認為我能給你們的最佳建議是去讀他的論文。他寫得太優美了，太清楚了。顯然他是一個偉大的思想家，對世界，對我們正在經歷的一切有著驚人的影響。我覺得這真是… 我以前不知道這一點。再次從閱讀中，你可以看到他不同的方面。他熱愛數學，你知道，像數論這樣的事情。他是一位真正的數學家。他在大學部時期就證明了最強形式的拉普拉斯定理（Laplace theorem），你知道，Central Limit Theorem，只是在他之前 10 年已經有人證明了。但他是一個大學部學生。

他是一位科學家，正如你們在最後看到的，他對大自然和自然建模非常感興趣。他顯然具有非常強烈的哲學傾向，從圖靈機論文和他的智能論文中可見一斑。他是一個真正的黑客（hacker）和工程師。我的意思是，我沒告訴過你們，我說我不談實際應用的事情，但他確實非常關心建造設備，他關心... 深入理解用於電腦記憶體的各種材料的電磁特性，或者設計 Enigma 加密機。是的，非常驚人。

他設法研究了令人驚嘆的、多種多樣的基本問題，而且對其中每一個都研究得非常深入。觸及了其中許多事情的核心。我認為很難想像他有多麼無畏。我的意思是，這很難理解。他真的什麼都不怕，他願意去任何地方。他對理解有著深深的渴望。當然他知道理論的價值。再次，閱讀他的論文真的很有趣。在其中許多論文中，存在著… 他寫的論文並不多，但其中有一些有爭議的模型，他非常仔細地思考其他人可能會對這些模型說什麼，各種反對或批評，而且他已經說了，「如果你這麼說，這是我的答案；如果你這麼想，這是我的答案。」所以在智能論文中，這真是太驚人了。他說，「如果你是神學家，你知道，你持有這種觀點，讓我以神學家的身份回答你。」是的，這真是美麗極了，而且他基本上是誠實的。我的意思是，他批評自己。他說「這是一個薄弱的論點，我回答你，但這不是一個很強的論點。」是的，他是一個非常清晰的思想者，而他的寫作方式澄清了這一點。

正如你們所見，他追求的是真正簡單的模型。簡單的模型。愛因斯坦有句名言是：「一切都應盡可能簡單，但不能更簡單。」我認為，是的，Turing 同意這一點。是的，在他發表論文之前，他會把關於這個問題能說的一切都想清楚，然後說「這就是我所有要說的了，現在你們去處理吧。」

總之，謝謝。我會用我平常演講最後一張投影片結束。現在我想大多數人都知道這本書了，但… 是的，非常感謝你們。

這裡有人拿著麥克風，是的。

好的，如果沒有問題的話，晚餐將於 7:30 在 Global 餐廳開始，從這裡步行約 10 分鐘。嗯，沒有人提供方向，大家都有手機嗎？這是一個問題。有人想提供方向嗎？我以為人們都夠聰明能找到餐廳，否則他們就不會餓了。他要告訴人們如何… 好的。Bruce，是的，至少你有個麥克風，你知道嗎？

好的，我相信 Igor 昨天晚上或今天早上發了一封電子郵件，提到了餐廳的名稱和地址。我的第一個建議是，你們只需將該地址輸入到你們最喜歡的地圖軟體中。我的非正式指示是，餐廳在 Georgia Street 上，名字叫做 Glowbal，G-L-O-W-B-A-L。它在 Georgia Street 和 Seymour Street 的街角。如果你從主大廳出來，想往北走上 Burrard Street，那就是右轉。然後到了 Georgia Street 時，右轉。如果你從後面出來，你知道，從 Hornby Street 的另一個入口出來，在 Hornby Street 左轉，然後到了 Georgia Street 時，在 Georgia Street 右轉。經過 Granville Street，經過 Richards Street，你就會到 Seymour Street。我相信它就在東南角。是的，那地方挺大的，很難錯過。

[掌聲]