計算複雜性理論先驅Levin：一箇中學生眼裏的柯爾莫哥洛夫老師_風聞

譯者按：

本文翻譯自Leonid Levin（1948-）為他的老師柯爾莫哥洛夫（Andrey Nikolaevich Kolmogorov，1903-1987）寫的紀念文章Колмогоров глазами школьника и студента ，原為俄文。感謝Levin院士允許我翻譯他的文章。

Leonid Levin院士研究領域是隨機、算法複雜性、信息論、計算理論等。他是NP完全問題的發現者，給出了NP完全定理（Cook-Levin定理）。他被寫入Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists，這本書中也提到了本譯文開頭寫的他與柯爾莫哥洛夫在其創建的數理特長中學的初見。

Lenoid levin

Levin院士描述了柯大師與中學生相處、講課風格、政治風雨中為學生撐開保護傘，文末，作者給出了對柯大師最後歲月的一個移民者的遠觀感受。

文中【安德烈·尼古拉耶維奇】即柯爾莫哥洛夫（有時也譯作“柯爾莫戈洛夫”）。

撰文 | Leonid Levin

翻譯 | 宋維凱HEOM

我第一次見到柯爾莫哥洛夫老師是在15歲那年，當時他參觀了基輔物理和數學寄宿學校（譯者注：一所數理特長中學），我在1963-1964年在那裏就讀。我已經從科普雜誌上知道了他的名字，但他給我的第一印象是出乎意料的：他沒有和在他訪問之際湧入寄宿學校的“大人物”待在一起，而是決定與學生見面。與任何其他院士都會照本宣讀的無聊講座不同，柯爾莫哥洛夫開始用有趣的問題來考我們。他將問題拋給大家，給我們幾分鐘的時間思考，並聽取了回答。我解決了其中的一些問題，他記住了我（我在很久以後才知道，他順便笑着提醒我注意一些可能不太討人喜歡的細節）。也許這在他決定允許我轉到他負責的莫斯科物理和數學寄宿學校（譯者注：即現在的柯爾莫哥洛夫中學）時發揮了作用。（所有其他審定人員都拒絕了，雖然我有一個理由：我父親當時在莫斯科，是一名研究生。但我真的很想去，從不放棄的父親得到了一次交談機會：在一次演講中奇蹟般地“抓住”了柯爾莫哥洛夫。）

在寄宿學校，柯爾莫哥洛夫親自給我們講授課程。他還帶我們去遠足，給我們朗誦詩歌【我記得維克多·索斯諾拉（Victor Sosnora，1939-2019）】，安排古典音樂會，從家裏帶來唱片。他不斷地鼓勵我們不僅要對數學和物理感興趣，而且要全面發展。我們喜歡遠足和詩歌，但對音樂所知甚少——這畢竟需要相關專業知識。學校倡導對“社會科學”感興趣讓我們又笑又惱，柯爾莫哥洛夫本人對此保持沉默是件好事。

他選擇了在學校中很不尋常的講座主題：伽羅瓦理論、直覺邏輯等。後來我反覆聽到讓我吃驚的意見：他們認為柯爾莫哥洛夫是一個糟糕的講師。然而，在十五六歲的我的眼裏，他是最好的講師。很多人認為，孩子們對這麼陌生的想法無法接受，這是一種誤解。孩子在生命的第一年比成年人幾十年裏學到的新事物都多。孩子們比大人做的唯一差的事情就是忍受無聊。但是柯爾莫哥洛夫老師的講座一點也不無聊！當然，內容很難，然而我們充滿激情，全力以赴。此外，講座結束後，我們努力去完成由柯爾莫哥洛夫的助教阿列克謝耶夫（Vladimir Mikhailovich Alekseev，1932-1980）、索辛斯基（Alexei Bronislavowitsch Sossinsky，1937-）精心挑選的題目。

柯爾莫哥洛夫的講座中包括了新近的發現，他鼓勵我們去思考未知的事物。那段時期，我證明了一些新定理，得到了安德烈·尼古拉耶維奇的讚許。他在莫斯科數學會提到了它們，並建議我向《蘇聯科學院報》寫一篇短文。（但我安排事情節奏混亂，直到幾年後才寫成。）

在大學學習期間，我有機會將柯爾莫哥洛夫的講座與馬爾科夫（Andrey Andreyevich Markov，1903-1979）關於類似主題的講座進行比較：對比是驚人的。（譯者注：這是提出“馬爾科夫鏈”那位數學家的兒子，是構造數學和邏輯方面的專家。）馬爾科夫始終如一地講解，一步接着一步。柯爾莫哥洛夫則是一下子把世界上的一切都講出來，他能將意想不到的東西連接起來，但每一個都與若干其他節點連接，眾多連邊若隱若現。他構建了一個指數級快速分支的“網絡”，從整體上很難看清脈絡關聯，但每個部分都很有趣。我開玩笑説，馬爾科夫和柯爾莫哥洛夫的演講風格遵循他們各自給出的算法定義。（馬爾科夫的算法基於線性字符串的逐字母的漸進變換；Kolmogorov–Uspensky的算法基於自由分支圖。）

柯爾莫哥洛夫當時喜歡的話題——複雜性、偶然性、信息的一般概念——讓我非常興奮。像許多年輕人一樣，我一直在試圖追求最基本的概念。但是諸如邏輯或算法理論之類的“基本”理論，它們的“定性”性質使我感到困惑——沒有什麼可以“計算”的。柯爾莫哥洛夫為這些領域帶來了豐富的定量工具。事實上，回到基輔，我試圖給複雜性下一個定義【我稱之為“非自然”（неестественность）】，但我無法證明它的不變性。在莫斯科，我把我的失敗告訴了索辛斯基，他問柯爾莫哥洛夫，給了我一個驚人的回答：柯爾莫哥洛夫剛剛證明了我做不到的事情，他的詳細文章即將發表！然後我決定不惜一切代價進入莫斯科國立大學，成為安德烈·尼古拉耶維奇的學生。

我恐怕柯爾莫哥洛夫老師不止一次後悔做我的導師。我是一個吵鬧、不規矩的學生，對所有問題都有自己的看法，讓責任感強的人不得安寧。對於任何需要替罪羊的人來説，我也是天賜之喜。這種需求是在 1960 年代後期莫斯科國立大學“意識形態工作崩潰”之後出現的。安德烈·尼古拉耶維奇堅定地為我辯護【在莫大傑出的校長彼得羅夫斯基（Ivan Petrovsky，1901-1973）的幫助下】。與領導當局意見相反，我最終得以留在莫斯科國立大學，甚至與柯爾莫哥洛夫一起開了一個討論班。我記得，老師在討論班上抱怨他自己“落後”和“老”了，但他不僅比我們所有人都更快地掌握我們尚未注意和理解的新想法，而且活躍地表達意想不到的深刻見解。

但時代變了。彼得羅夫斯基校長去世了（聽説是在與“高層”進行了艱難的談話後心碎而死）。心懷不軌的莫大黨委書記亞戈金成為莫斯科市委秘書和副手、中央委員會科學部的領導。按照新的標準，謹慎的柯爾莫哥洛夫幾乎變成了持不同政見者。我成為所有與我有聯繫的人的負擔；我無法在正式的科學機構工作，甚至無法參加研討會（參與者被要求上報我的到訪情況）。我在莫斯科的存在開始變得毫無意義。柯爾莫哥洛夫老師甚至告訴我，當局要求他和我談談這件事。幾年來我一直抗拒移民的想法，但最終，在1978年，我下定了決心。

令我感動的是，柯爾莫哥洛夫老師不顧他一貫的謹慎，邀我當面告別，並送給我一本非常美麗的古代俄羅斯建築相冊，甚至題字（儘管他只用了名字中的首字母簽名）。

當然，我不能從美國給他寫信——那會使他面臨不必要的風險。遠遠地，我絕望地看着這位偉大科學家如何被排斥，他的健康如何被破壞，以及他在“改革”伊始逝去，而沒有機會看到新的時代。

本文經授權轉自宋維凱HEOM，https://zhuanlan.zhihu.com/p/446319224，有修訂。原文收錄於《柯爾莫哥洛夫學生回憶集》（Колмогоров в воспоминаниях учеников，МЦНМО, 2006）

特 別 提 示

1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閲不同主題系列科普文章。

2. 『返樸』提供按月檢索文章功能。關注公眾號，回覆四位數組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。