0
| 本文作者： 我在思考中 | 2022-07-25 10:43 |
圖注：Dana Scott
作為一位在上世紀(jì)早期獲得圖靈獎的科學(xué)家，Dana Scott 是個典型的通才式科學(xué)家，他的研究涉及計算機(jī)科學(xué)家、數(shù)學(xué)和哲學(xué)等多個領(lǐng)域，他在自動機(jī)理論、模態(tài)邏輯、模型論、集合論和編程語言理論等問題上做出了開創(chuàng)性的貢獻(xiàn)，尤其是域理論（domain theory），它分析計算機(jī)編程語言所必不可少的一種數(shù)學(xué)理論。
如今的 Dana Stewart Scott 已經(jīng) 89 歲，從 CMU 退休后一直居住在加州伯克利。本文講述了他在獲得圖靈獎之前 26 年求學(xué)、科研與教學(xué)生涯。在加州伯克利分校、普林斯頓大學(xué)、芝加哥大學(xué)、斯坦福大學(xué)、牛津大學(xué)等地，Scott 先后結(jié)識了一批偉大的數(shù)學(xué)家、計算機(jī)理論學(xué)家，并受到了他們的深刻影響。他曾師從邏輯學(xué)家 Alfred Tarski 和圖靈的導(dǎo)師 Alonzo Church，Rabin 是他的師兄。70 年代，他遇到編程語言設(shè)計先驅(qū) Christopher Strachey，與他的合作奠定了現(xiàn)代編程語言語義學(xué)方法的基礎(chǔ)。
Scott 于 1932 年出生于加利福尼亞州伯克利，一家人住在蘇珊維爾附近的一個農(nóng)場，后來搬到了斯托克頓市。如今的他還記得，1941 年 12 月 7 日那天，街上的賣報聲不絕于耳：「號外！號外！快來看?。赫渲楦郾晦Z炸了」。
學(xué)生時期，Scott 對音樂產(chǎn)生了極大的興趣，他學(xué)會了演奏單簧管，還上過一些鋼琴課。在學(xué)習(xí)樂器的過程中，他開始思考樂器是如何發(fā)出聲音的。他從樂隊(duì)老師那里得到一本書“Science of Musical Sounds”（《音樂的聲音科學(xué)》），他被這本書吸引住了。書中的數(shù)學(xué)知識又激發(fā)了他對數(shù)學(xué)的興趣，叔叔給了他一本微積分的書，他便埋頭啃了起來。
Scott 經(jīng)常光顧周圍總是塵土飛揚(yáng)的州立圖書館。他在那里發(fā)現(xiàn)了 Helmholtz 關(guān)于聲學(xué)和音樂理論的書，受其啟發(fā)，他在高中慢慢地研究起了對數(shù)和傅里葉級數(shù)。高年級的時候，他做了一個關(guān)于聲學(xué)的小項(xiàng)目，最終獲得了西屋獎學(xué)金。
對 Scott 而言，音樂在他的一生中占有極其重要的地位，他的妻子、女兒和孫女也都是專業(yè)級的古典音樂家。
而在學(xué)習(xí)數(shù)學(xué)的路上，Scott 從高中數(shù)學(xué)老師那里得到了非常多的鼓勵，所以高中時的他就下定決心，如果有機(jī)會上大學(xué)，一定要主修數(shù)學(xué)。Scott 的父母都沒有上過大學(xué)，而他很幸運(yùn)地獲得了一筆小額獎學(xué)金，足夠他進(jìn)入加州大學(xué)伯克利分校學(xué)習(xí)。在他的所有直系親屬中，他是第二個獲得大學(xué)學(xué)位的人。
1950 年進(jìn)入伯克利后，Scott 報名參加了邏輯入門課程，任課教師是哲學(xué)系主任 Paul Marhenke 教授。這門課對 Scott 來說不算難，他也開始喜歡上了邏輯學(xué)。升入大二后，Scott 修了更多哲學(xué)系 Benson Mates 教授的課，兩人成了關(guān)系很好的朋友。Benson Mates 推薦他讀 Alfred Tarski 的作品，Tarski 是全球邏輯學(xué)的領(lǐng)導(dǎo)者，此前他在波蘭逃脫了猶太人的迫害，后來進(jìn)入伯克利做數(shù)學(xué)教授。
圖注：Alfred Tarski
大學(xué)前兩年，Scott 的生活仍比較拮據(jù)，為了養(yǎng)活自己，他在校圖書館的期刊室打工。在那里，他讀了很多符號邏輯期刊上的文章，但幾乎所有文章他都看不大懂，除了 Jan Kalicki 有關(guān)真值表的那篇論文。1951 年，Kalicki 應(yīng) Tarski 的邀請來到伯克利。Scott 報名參加了他的方程理論課程，Kalicki 自己竟然讀了他的論文感到既驚訝又高興。后來，兩人就合寫了一些關(guān)于方程理論的論文，而 Tarski 也早已在研究這些理論。Scott 談起他與 Kalicki 的合作：我們的理論是「完整的」，因?yàn)樗鼈儽仨氃诓槐罎⒌那闆r下才能進(jìn)一步擴(kuò)展，因此可以推導(dǎo)出所有方程。
非常不幸的是，在 Scott 認(rèn)識 Kalicki 第二年的時候，Kalicki 在一場車禍中喪生。這位朋友和導(dǎo)師的離去，給 Scott 帶來了很大的打擊。Scott 回憶，Kalicki 是一位非常了不起的教師，和許多數(shù)學(xué)家一樣，他可以在沒有任何筆記的情況下授課。那個時期，Scott 已經(jīng)進(jìn)入了 Tarski 的圈子里，大三的時候，他繼續(xù)參加 Tarski 的課程和研討會。
后來，Scott 開始學(xué)習(xí)形式理論，他找到了 Paul Rosenbloom 寫的關(guān)于數(shù)理邏輯的小書。其中一章是關(guān)于 Haskell Curry 的組合器和 Alonzo Church 的 lambda 演算。Scott 花了很多時間弄清楚組合器如何組合，以及它們?nèi)绾瓮ㄟ^方程式進(jìn)行相互復(fù)制，那段時間，他整個晚上都會做關(guān)于組合器的噩夢。Scott 回憶，我不知道關(guān)于組合器的噩夢是不是加深了我對 lambda 演算的興趣，但這些噩夢確實(shí)是一個起點(diǎn)。
1954 年，Scott 留在伯克利繼續(xù)攻讀博士，師從 Tarski 。
一開始，Tarski 聘請他擔(dān)任助理來對自己的早期著作做翻譯和校對工作。Scott 感到這項(xiàng)工作實(shí)在太無聊了，逐漸心生怠惰?？上攵?，最后 Tarski 氣憤地解雇了他。從這以后，兩人逐漸變得疏遠(yuǎn)。
一位教授聽說了 Scott 的困境，便跟他說：「你為什么不考慮去別的地方？普林斯頓大學(xué)的 Norman Steenrod 正好來這里訪問，去見見他吧。」最終 Scott 獲得了這位教授的推薦，第二年，他便去了普林斯頓。
正在思考 lambda 演算問題的 Scott，很想得到 Alonzo Church 教授的指導(dǎo)，Church 早期提出了基于無類型限制的 lambda 演算的邏輯系統(tǒng)，他認(rèn)為這能解決導(dǎo)致羅素悖論的弗雷格系統(tǒng)中的問題，但后來被證明行不通。Scott 認(rèn)為，Church 其實(shí)對此感到很挫敗，這導(dǎo)致他一直都回避這件事，從來不與學(xué)生討論。
圖注：Alonzo Church
值得一提的是，艾倫·圖靈曾是二戰(zhàn)前 Church 的博士生。當(dāng)時，Church 很固執(zhí)地讓 Turing 在他關(guān)于超限計算的所有工作中都使用 lambda 演算。后來圖靈曾對此抱怨，但為了獲得博士學(xué)位，他不得不聽從導(dǎo)師的要求。Scott 坦言，他覺得這兩人其實(shí)關(guān)系一直不怎么親近，而且，在他讀研究生的時候，從來沒聽導(dǎo)師談起過圖靈。
不過，Church 對 Scott 的博士論文選題倒沒有加以干涉。通常情況下， Church 會與學(xué)生們討論各自感興趣的研究領(lǐng)域，然后放手讓他們?nèi)プ?。對?Church 的放養(yǎng)式指導(dǎo)，Scott 很不客氣地說，Church 主要是糾正了他論文中的拼寫錯誤。在與 Tarski 發(fā)生過不愉快之后，他與 Church 之間的合作又變得不順利了。
1958 年夏天，Scott 在普林斯頓大學(xué)的博士學(xué)位后，就到高級研究所（Institute for Advanced Study）里馮·諾依曼建造的計算機(jī)上做一些編程工作。當(dāng)他來普林斯頓讀博的時候，馮·諾依曼就已經(jīng)躺在了醫(yī)院里，所以一直沒有機(jī)會見到他。馮·諾依曼去世后，他建造的那臺計算機(jī)被轉(zhuǎn)移到普林斯頓，Scott 解釋，這是因?yàn)楦呒壯芯克恢倍疾幌胱龉こ谭矫娴氖虑椤?/span>
圖注：現(xiàn)代計算機(jī)之父馮·諾伊曼
Scott 被聘請在這臺計算機(jī)上做一個項(xiàng)目，他和一起合作的同事選擇了五格骨牌（Pentominoes）的幾何難題。受到 Dick 和 Emma Lehmer 在伯克利開發(fā)的回溯算法的啟發(fā)，他們認(rèn)為完全能夠解決這個難題。
然而，學(xué)校很快發(fā)現(xiàn)，讓這臺機(jī)器運(yùn)轉(zhuǎn)起來，實(shí)在太昂貴了。靜電管受濕度的影響很大，而普林斯頓是個濕度很高的地方，所以，在馮·諾依曼機(jī)器上工作的最佳時間是凌晨 3 點(diǎn)。最后到了秋季的時候，學(xué)校再也不愿讓他們繼續(xù)了，于是關(guān)閉了計算機(jī)。
回顧在普林斯頓的時光，Scott 既十分懷念又感到些許的遺憾：“普林斯頓是一個非常令人興奮的地方，因?yàn)橛泻芏鄶?shù)學(xué)家到那里工作或訪問，師資力量非常強(qiáng)大，但回想起來，如果我那時候能更多地利用我在普林斯頓學(xué)到的東西就好了?！?/span>
與 Scott 一起獲得圖靈獎的 Michael Rabin，當(dāng)時是 Church 的另一位博士生，兩人讀博期間成了非常要好的朋友。1957 年，他們被選中在 IBM 約克鎮(zhèn)高地研究中心進(jìn)行暑期實(shí)習(xí)，一起研究有限狀態(tài)自動機(jī)問題。
圖注：Michael Rabin
一開始，他們感到無從下手，最終還是決定從模型理論和結(jié)構(gòu)的角度來切入。那時，幾篇關(guān)于自動機(jī)的論文激發(fā)了他們對這個方向的興趣。回想起來，Scott 也說不清他們是怎么想到做非確定性自動機(jī)（nondeterministic automata）的，也許是因?yàn)樗麄冊谠噲D創(chuàng)建狀態(tài)來控制各種決策時總是遇到難題。
非確定性自動機(jī)與概率自動機(jī)不同。當(dāng)它從一種狀態(tài)轉(zhuǎn)換到另一種狀態(tài)時，它可以做出許多選擇，而不是特定的一種選擇。所以，不必?fù)?dān)心有行不通的路徑，因?yàn)橹恍枵业狡渲幸粭l成功的路徑。為了證明非確定性自動機(jī)接受與確定性自動機(jī)相同的字符串集，我們可以將所有狀態(tài)的冪集視為新狀態(tài)，并在狀態(tài)集上定義轉(zhuǎn)換函數(shù)。當(dāng)然，狀態(tài)的數(shù)量呈指數(shù)增長。非確定性自動機(jī)有時更好用，因?yàn)樗鼈冃枰臓顟B(tài)要少得多。
夏天結(jié)束時，Scott 和 Rabin 一起參加了康奈爾大學(xué)的一個邏輯學(xué)會議，幾乎所有邏輯領(lǐng)域的學(xué)者都出席了那次會議。他們報告了關(guān)于自動機(jī)的工作，而且又準(zhǔn)備了一篇論文在下一學(xué)年提交。他們的工作收到的評價很好，諸如「證明得很好，而且很簡潔」之類，不過回想起來，Scott 記得當(dāng)時并沒有太多人對他們的方法顯示出特別的熱情。
在普林斯頓的最后一個學(xué)年，Scott 曾遇到了從芝加哥大學(xué)來訪的 Paul Halmos。兩人在代數(shù)邏輯方面有著共同的興趣，也是在 Halmos 的推動下，Scott 被邀請以非終身講師的身份去到芝加哥，在那里擔(dān)任講師，直到 1960 年。
剛到芝加哥大學(xué)任教時，Scott 遇到了 Stanley Tennenbaum。他對 Scott 影響很大，兩人一起做了很多工作。Tennenbaum 發(fā)現(xiàn)不存在滿足一階算術(shù)定律的可計算非標(biāo)準(zhǔn)模型，從而為 Emil Post 在遞歸函數(shù)理論中的問題提出了一個簡潔的證明，在今天被稱為“Tennenbaum 定理”。不過，由于一場盜竊，他們合作的大部分工作都未得以發(fā)表。Tennenbaum 的車被人闖入，那個裝著他們所有文件的盒子被盜走，筆記全部丟失了。Scott 后來肯定地說：當(dāng)小偷看到盒子里是什么時，這些筆記肯定在 10 分鐘內(nèi)就被丟棄了，所以它們從未得見天日。
在芝加哥的兩年任期結(jié)束時，Scott 與 Tarski 建立了全面的和解。所以在 1960 年夏天，Scott 回到伯克利，并且獲得了新成立的米勒研究所的獎學(xué)金。在超乘積及其與大基數(shù)的關(guān)系問題上，他做了許多工作。在 1961 年發(fā)表的一篇論文中，Scott 證明了可測基數(shù)與哥德爾關(guān)于“所有集合都是可構(gòu)造”的觀點(diǎn)相矛盾。非常巧合的是，當(dāng)時布拉格一位才華橫溢的年輕邏輯學(xué)家 Petr Vopnka 也在同一時間發(fā)現(xiàn)了同樣的證據(jù)。
Rabin 去伯克利休假一年，這期間，Scott 和他又一起度過了非常愉快的時光。Rabin 發(fā)現(xiàn)了 Trakhtenbrot 定理的一個新證明，即在有限結(jié)構(gòu)中為真的一階句子的集合是不可公理化的、不可枚舉的。兩人還一起合作，取得了一些其他成果。不過這也是兩人的最后一次合作，Rabin 之后去了耶路撒冷，后來轉(zhuǎn)去哈佛。
比利時的數(shù)值分析師 René De Vogelaere 當(dāng)時也在伯克利。他非常熱衷于宣傳使用 ALGOL 進(jìn)行編程。在伯克利，Scott 還結(jié)識了許多來訪問的邏輯學(xué)家。斯坦福大學(xué)的 John Myhill 和他合作了一篇關(guān)于“序數(shù)可定義性”（Ordinal Definability）的論文，表明可遺傳的序數(shù)可定義集合形成了滿足選擇公理的集合論模型。哥德爾看到這項(xiàng)工作后說：「哦，我?guī)啄昵熬拖氲搅?。但我對可?gòu)造集合的證明要重要得多，我從來沒有告訴過任何人?！?Scott 對此感到有些無奈：「好吧，就這樣了」。
1963 年，John Myhill 離開了斯坦福，所以斯坦福也就空出了一個職位。而此時的 Scott 在伯克利正經(jīng)歷著許多不愉快。伯克利的數(shù)學(xué)系正在大力引進(jìn)教師、擴(kuò)展規(guī)模，并且開始對 Tarski 有一定程度的敵意，因?yàn)樗罅ν苿舆壿媽W(xué)的發(fā)展。Scott 決定擺脫這種環(huán)境。
暑假期間，Scott 經(jīng)常去斯坦福與 Patrick Suppes 一起工作。50 年代 Scott 在伯克利讀本科時，就修讀過他的課程，后來兩人成了親密的朋友。Suppes 一直對如何將邏輯應(yīng)用于數(shù)學(xué)心理學(xué)感興趣，兩人在 1958 年合作寫了一篇將測量理論與概率論聯(lián)系起來的論文，Scott 在其中的貢獻(xiàn)主要是在模型理論方面。
在 60 年代初期，斯坦福大學(xué)的 Georg Kreisel 教授開始定期訪問斯坦福，正是他說服了 Scott 從伯克利搬到斯坦福。
在斯坦福，像 Georg Kreisel 這樣的數(shù)學(xué)家開始倡導(dǎo)計算機(jī)科學(xué)在學(xué)科上應(yīng)該更獨(dú)立一些。以經(jīng)典應(yīng)用數(shù)學(xué)為主的數(shù)學(xué)系很樂意放棄數(shù)值分析的傳統(tǒng)，來幫助組建新系。當(dāng)時，Don Knuth 離開加州理工學(xué)院，加入斯坦福。麻省理工學(xué)院的 John McCarthy 也來斯坦福創(chuàng)辦了他的人工智能實(shí)驗(yàn)室。Scott 倒沒有直接參與計算機(jī)科學(xué)系的籌建，但他認(rèn)識在那里的每個成員。
從芝加哥大學(xué)來到斯坦福的 Paul Cohen 發(fā)明了“forcing”，僅僅在少量信息的基礎(chǔ)上就成功賦予了函數(shù)一些性質(zhì)。而且，他不僅可以將其擴(kuò)展到整數(shù)上的函數(shù)，還可以擴(kuò)展到超有限域，并且他還用它來證明了連續(xù)統(tǒng)假設(shè)（Continuum Hypothesis）((f)) 獨(dú)立于集合論公理。當(dāng)時，所有人都被他的工作驚呆了。伯克利的 Robert Solovay 經(jīng)常訪問斯坦福，為的是能與 Cohen 交流研究，他們觀察到，“forcing” 的概念可以為關(guān)于集合論的陳述賦予布爾值。
在 1966 年的新年假期中，Scott 對自己說：“「等等。我為什么不首先從一個合適的布爾代數(shù)開始，然后用它來解釋集合論，并以不同的方式來證明連續(xù)統(tǒng)假設(shè)的獨(dú)立性？」最終，這個想法在論文中得以呈現(xiàn)，并獲得了 1972 年 Leroy P. Steele 獎。
Scott 在 1970 年代與編程語言設(shè)計先驅(qū) Christopher Strachey 的合作奠定了現(xiàn)代編程語言語義學(xué)方法的基礎(chǔ)。與 Strachey 的相識是在阿姆斯特丹大學(xué)。
圖注：Christopher Strachey
從 1968 年開始，Scott 在阿姆斯特丹大學(xué)休了兩年學(xué)術(shù)假。期間，他還認(rèn)識了 Aad van Wijngaarden，他是 ALGOL 語言的設(shè)計者之一 。
這年夏天，Scott 參加了關(guān)于編程形式化描寫的 IFIP 工作組。在那里，Scott 聽了很多關(guān)于語言設(shè)計的話題之后，后來又遇到了 Strachey，看到他的語言設(shè)計方法后，Scott 對思考計算機(jī)語言產(chǎn)生了濃厚的興趣。
Scott 原本已經(jīng)決定從阿姆斯特丹搬回普林斯頓，但由于對這些新問題的興趣，他特別請求了哲學(xué)系讓我在 1969 年秋季的第一個學(xué)期休假，這樣就可以去牛津大學(xué)訪問并與 Strachey 一起工作。
在遞歸函數(shù)理論方面，Scott 有很豐富的研究經(jīng)驗(yàn)。在斯坦福，他講授過自動機(jī)理論。許多人都已經(jīng)寫過關(guān)于遞歸函數(shù)空間上的運(yùn)算符的文章。Scott 發(fā)現(xiàn)，Strachey 在形式上非常依賴 Church 的無類型 lambda 演算，便跟他說：「如果你考慮有類型的運(yùn)算，結(jié)果就會好得多?！篂榇耍琒cott 還專門寫了一篇關(guān)于可計算函數(shù)邏輯 (LCF)的論文，目的就是為了說服 Strachey 去使用一種數(shù)學(xué)基礎(chǔ)簡單且可以擴(kuò)展的方法。Strachey 也馬上很愉快地采用了這種思路。
在斯坦福大學(xué)，Scott 遇到的一個困難是那里的數(shù)學(xué)系非常注重經(jīng)典分析，而對邏輯的發(fā)展并不真正感興趣。他數(shù)學(xué)和哲學(xué)之間感受到了一種分裂，邏輯在數(shù)學(xué)中并不是特別受歡迎。
在 1968 年離開普林斯頓的哲學(xué)教授 Donald Davidson，后來到阿姆斯特丹訪問，并邀請 Scott 去普林斯頓。
Strachey 于 1970 年代初到普林斯頓拜訪 Scott，那段時間，他們完成了一篇數(shù)學(xué)語義學(xué)（mathematical semantics）方向的論文。這個方向后來被稱為“指稱語義學(xué)”（denotational semantics），以便與 Tony Hoare 所提倡的“公理語義學(xué)”（axiomatic semantics）和 Gordon Plotkin 所提倡的“操作語義”（operational semantics）區(qū)分開來。不過今天，這三種語義學(xué)已經(jīng)融合在了一起，要考慮的是從哪些方面進(jìn)行分析或證明，或者為某種實(shí)現(xiàn)奠定基礎(chǔ)。
在普林斯頓時，正生著病的哥德爾找到 Scott， 請他幫忙保存未發(fā)表的筆記，其中有他基于模態(tài)邏輯對「上帝存在」的本體論證明。Scott 其實(shí)不同意這個結(jié)論，他認(rèn)為，如果你假設(shè)你想證明什么，那你最終就會證明它。不過，有一次，Scott 在未經(jīng)哥德爾許可的情況下于普林斯頓的一次研討會上談到了這一點(diǎn)，哥德爾的想法因此被公布出來，并被廣泛討論。
圖注：哥德爾
1972 年春天，Scott 很驚訝地收到牛津大學(xué)副校長的來信，信中邀請他到牛津做數(shù)理邏輯研究。那時，他和家人剛剛搬到普林斯頓，這么快就又要再次搬家，但 Strachey 和他團(tuán)隊(duì)的工作做得很出色，所以 Scott 決定接受這份邀請。
然而，Strachey 在 1975 年初病倒了，因?yàn)閷懽髂瞧@得 1974 年亞當(dāng)斯獎（Adams Prize）的論文實(shí)在是一項(xiàng)非常艱巨的任務(wù)。那年 5 月，Strachey 英年早逝，Scott 為無法再與這位優(yōu)秀學(xué)者合作而感到非常悲傷。
在 1976 年 10 月 20 日的休斯頓，Scott 與 Rabin 在 ACM 年會上一同接受圖靈獎的榮譽(yù)。Rabin 的演講題目是“計算復(fù)雜性”(Complexity of Computations)，Scott 則就“邏輯與程序設(shè)計語言”（Logic and Programming Language）發(fā)表了演講......
回顧自己的研究生涯，Scott 這樣總結(jié)道：在很大程度上，我的動力來自于我在教學(xué)上得到的激勵，我很幸運(yùn)擁有非常優(yōu)秀的學(xué)生，他們中的許多人都成了與我非常親密的朋友，最讓我感動的，是這些學(xué)生帶給我的啟發(fā)。
雷峰網(wǎng)(公眾號：雷峰網(wǎng))
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
