計算機文化基礎(chǔ)系列常識-圖靈獎獲獎?wù)呓榻B連載(十二)

計算機文化基礎(chǔ)系列常識-圖靈獎獲獎?wù)呓榻B連載（十二）米凱爾，拉賓(MichaelO．Rabin)米凱爾，拉賓(MichaelO．Rabin)達納·斯科特(DanaStewardScott)——非確定性有限狀態(tài)自動機理論的開創(chuàng)者

1976年度的圖靈獎由當時在以色列希伯萊大學任教授的米凱爾，拉賓(MichaelO．Rabin)和在英國牛津大學任數(shù)理邏輯教授的達納·斯科特(DanaStewardScott)共同獲得。拉賓和斯科特是師兄弟，兩人在20世紀50年代中期先后師從著名的邏輯學家和計算機專家阿隆索·邱奇(AlonzoChurch，他因與Curry一起發(fā)明了λ-演算以及提出了“任何計算，如果存在一有效過程，它就能被圖靈機所實現(xiàn)”這一被稱為“邱奇論題”的命題而聞名于世)，并在有限自動機及其判定問題的研究中進行合作，奠定了非確定性有限狀態(tài)自動機的理論基礎(chǔ)。之后，他們的研究方向不盡相同，拉賓側(cè)重于計算理論，而斯科特側(cè)重于邏輯學在計算機科學中的應(yīng)用，在各自的領(lǐng)域中又分別獲得重大成果，作出了創(chuàng)造性貢獻。拉賓1931年9月1日生于德國的布雷斯勞(Breslau，第二次世界大戰(zhàn)以后成為波蘭的城市并改名為弗羅茨瓦夫)。他父親是一名猶太教教士，也是一位博士，在當時很著名的布雷斯勞神學院教猶太歷史和哲學，還當過院長。拉賓的母親也是知識分子，有文學博士頭銜，年輕時即開始從事兒童文學的創(chuàng)作。納粹希特勒上臺以后，拉賓的父親因為曾經(jīng)在俄羅斯呆過，憑著政治敏感性，預(yù)感到會有動蕩和麻煩，曾建議神學院遷往耶路撒冷，未獲同意，于是全家于1935年遷回了巴勒斯坦，躲過了一劫。1948年以色列建國以后，他們成為以色列公民。

拉賓在瀕臨地中海的港口城市海法度過了他的童年和少年時代。由于閱讀了著名微生物學家保羅·德克呂夫(PaulDeKmif)所著的《微型獵人》一書，激起了拉賓的想象，幻想自己成為微生物學家。一次他和比他高好幾班的學生比試解歐幾里德幾何題，他贏了他們，這又使他對數(shù)學產(chǎn)生了興趣，因此，從萊利學院(RealiCollege)畢業(yè)以后，他進入希伯萊大學學習數(shù)學，在那里，他通過數(shù)學家克林(S．C．Kleene，因提出不動點定理——theoremonfixpoint及正則集定理一theoremonregularset而聞名于世)所著的《元數(shù)學》一書首次接觸到圖靈關(guān)于可計算性的概念和圖靈機這一理論計算模型，立即被深深吸引。但為了打好自己的數(shù)學墓礎(chǔ)，他的碩土論文沒有以此為課題，而選擇了當時由德國女數(shù)學家埃米·諾特(EmmyNoether，1882—1932)創(chuàng)立不久的抽象代數(shù)中關(guān)于可交換環(huán)理論中的一個問題。獲得數(shù)學碩士學位以后，拉賓去了美國，因為20世紀50年代初，以色列建國伊始，經(jīng)濟與科技都還不夠發(fā)達，很少有人研究計算這類問題，甚至連計算機都沒有。拉賓到美國后，先在賓夕法尼亞大學，后來轉(zhuǎn)到普林斯頓大學攻讀博士學位。拉賓的博士論文課題將他所熟悉的抽象代數(shù)和他感興趣的可計算性問題聯(lián)系在一起：群(GROUP)的可計算性問題。拉賓在論文中證明了與群有關(guān)的許多問題，如群是否符合交換律等，都是不能由計算機解答的。但是使拉賓成名的并非其博士論文而是源于IBM研究中心于1957年向他和他的師弟斯科特提供的一份暑期工作。公司允許他們作他們感興趣的任何工作，于是拉賓和斯科特就聯(lián)手研究圖靈提出的計算模型，也就是圖靈機。圖靈機是一種禁止往磁帶上寫的計算機，叫有限狀態(tài)自動機(finitestateautomata，縮寫FSA)。圖靈在研究這種機器時的基本信條是：機器在輸入相同時，其“心智狀態(tài)”也相同，即對于具有給定指令集的機器而言，一定輸入的機器總是按同一方式運行的。拉賓和斯科特認為，這種具有“確定性”行為的機器帶來了局限性。因此，他們定義了一種新的、“非確定性”的有限狀態(tài)自動機(nondeterministicfinitestateautomata，縮寫為NDFSA)，這種機器在讀取到一定的輸入后，有一個可以進入的可能的新的狀態(tài)的“菜單”可供選擇，這樣對給定的輸入計算便不單一了，每個選擇代表一種可能的計算。拉賓和斯科特將圖靈的有限狀態(tài)自動機從確定性一種形態(tài)擴展到非確定性的另一種形態(tài)，極大地推動了有限狀態(tài)自動機理論的發(fā)展。雖然非確定性有限狀態(tài)自動機的能力并不比確定性的有任何增加(拉賓和斯科特自己已經(jīng)證明任何可以用非確定性機器解決的問題都可以在確定性機器上解決，而且提出了將非確定性機器轉(zhuǎn)換為確定性機器的方法問題)，但是它可以簡化機器描述和加快解題速度。后來的實踐證明，非確定性有限狀態(tài)自動機在機器翻譯、文獻檢索和字處理程序等應(yīng)用中都起了重要的作用。拉賓和斯科特的研究成果過了兩年才在IBM公司的研究和開發(fā)雜志上發(fā)表，這就是論文“有限自動機及其判定問題”(Finiteantomataandtheirdecisionproblems，IBMJournalofResearchandDevelopment，3(1959)，114—125頁)。

1958年夏天，拉賓又一次來到IBM。當時，“人工智能之父”麥卡錫(J．McCarthy，1971年圖靈獎獲得者)正在那兒研究往巴克斯(J．Backus，1977年圖靈獎獲得者)發(fā)明不久的Fortran語言中加入表處理功能。他給拉賓出了一道難題：設(shè)計一種口令，即使口令被敵方竊去，也無法進入系統(tǒng)。拉賓經(jīng)過艱苦探索，終于利用由馮·諾伊曼開發(fā)的一個單向函數(shù)解決了這個問題。所謂單向函數(shù)簡單說來就是正向極易于計算而反向極難計算的函數(shù)，例如“平方取中”：y=[x2中間一半的位所組成的數(shù)].這樣，當x為100位的數(shù)時，x2為200位的數(shù)，y則為這200位的中間100位所組成的數(shù)。由z算y是容易的，而由y求出x則非常困難，因為可能的x非常之多。正是這個問題促使拉賓進一步研究計算任務(wù)的最小計算量這一一般性問題，也就是計算的固有難度問題，從而成為最早研究計算復(fù)雜性問題的先驅(qū)之一。1959年和1960年，拉賓在耶路撒冷先后發(fā)表了有關(guān)此問題的兩篇論文，即“計算速度和遞歸集合的分類”(Speedofcomputationandclassificationofrecursivesets，3rdConventionofSci．Sco，Israel，1959)及“函數(shù)的計算難度和遞歸集合的偏序“(DegreeOfdifficultyOfcomputingafunctionandapartialorderingofrecursivesets，Tech．Rep．No．1，O．N．R·，Jerusalem，1960)。論文雖然沒有用“計算復(fù)雜性”這個名詞而用了“計算速度”和“計算難度’’這類名詞，但學術(shù)界公認這兩篇論文是研究計算復(fù)雜性的最早、最權(quán)威的論文中的兩篇，對1964年正式提出“計算復(fù)雜性”這一術(shù)語的哈特馬尼斯(J．Hartmanis)和斯特恩斯(R．E．Sterns，這兩人是1993年圖靈獎獲得者)以及計算復(fù)雜性理論的另一奠基人布盧姆(M．Blum，1995年圖靈獎獲得者)都曾產(chǎn)生過深刻影響。其中布盧姆正是聽了拉賓的有關(guān)演說才開始研究計算復(fù)雜性并完成其博士論文的。

拉賓的研究成果在一定程度上改變了人們的研究方向。例如，波蘭數(shù)學家普里斯伯克(M．Presburger)在1930年于華沙舉行的一次國際數(shù)學家會議上所發(fā)表的論文中提出了這樣一個命題：只包括自然數(shù)相加運算的數(shù)學系統(tǒng)是完備的，也就是說這樣的系統(tǒng)在圖靈機上都是可計算的。因此這被稱為普里斯伯格算術(shù)系統(tǒng)，不少計算機科學家試圖編寫出能證明這個系統(tǒng)中的定理的計算機程序。但拉賓指出，這是極其困難而無法實現(xiàn)的。對于只有100個符號的這樣的系統(tǒng)，即使是1萬億臺每秒運行1萬億次的計算機，也要運行1萬億年才能得出結(jié)果。1974年在斯德哥爾摩的IFIP大會上他作了一次學術(shù)演講，公布了他和耶魯大學的費歇爾(M．Fisher)的這項研究成果，宣稱“這就是通向人工智能的理論障礙”。拉賓演說那天，正好是美國總統(tǒng)尼克松因水門事件被迫宣布辭職這一天，拉賓原以為代表們都去看尼克松演說的電視轉(zhuǎn)播而不會有多少人來聽講，卻不料演說一開始人們就潮水一樣涌了進來，對演說的反應(yīng)十分強烈，拉賓講完以后人們在麥克風前排成長隊向他提問。對于從事普里斯伯格系統(tǒng)研究的許多人來說，他們聽了拉賓演說以后的感覺是非常難受，似乎“世界末日”到了似的。但拉賓本人則并不悲觀，他認為應(yīng)該放棄的只是以完全確定的方式去獲得結(jié)果的企圖，但完全可以利用隨機性以某種方式很快獲得結(jié)果，這種結(jié)果可能出錯，然而出錯的可能性微乎其微，也就是說可以把概率算法(probabilisticalgorithm，或叫隨機算法，randomizealgorithm)用到這類問題中來，這是拉賓的又一個貢獻。

所謂概率算法，就是帶有隨機操作的一類算法。這種算法在計算的某一步或某些步產(chǎn)生符合規(guī)定要求的隨機數(shù)，然后根據(jù)產(chǎn)生出韻隨機數(shù)決定下一步的計算。例如，在計算的某一步有兩種選擇：執(zhí)行A或執(zhí)行B。此時隨機產(chǎn)生一個0或1。若產(chǎn)生的是0則執(zhí)行A，若產(chǎn)生的是1則執(zhí)行B。這相當于根據(jù)擲一枚硬幣的結(jié)果(正面或反面)決定下一步的計算。

將概率的思想用到算法中始于數(shù)值計算，在計算方法中通常稱作蒙特卡羅法，是在20世紀40年代中葉提出的。它的基本思想是建立概率模型，通過統(tǒng)計模擬或抽樣得到問題的近似解。通常要求計算結(jié)果的期望值等于問題的精確解，并且計算誤差的期望值隨可供使用的時間增加減小。近20年來概率算法在非數(shù)值計算中得到很好的應(yīng)用。例如，已經(jīng)設(shè)計出關(guān)于排序和搜索、素數(shù)判定、有限域上的多項式分解和求根、字符串的模式匹配等方面的有效概率算法。概率算法同樣也應(yīng)用到并行計算中，得到概率并行算法。

利用這種概率算法的思想拉賓在1974年斯德哥爾摩演說時就已有了萌芽，但還不夠成熟。第二年休假時他去了麻省理工學院，得知了加里·米勒(GaryMiller)的研究工作。米勒證明，利用著名的黎曼假設(shè)(G．P．B．Riemann，1826—1866，德國的數(shù)學家兼物理學家)，可以用一般的確定性算法判斷很大的數(shù)是否是素數(shù)。拉賓利用米勒的研究結(jié)果和數(shù)論中關(guān)于素數(shù)密度的理論，終于在1976年提出了一個判定素數(shù)的概率算法，取得了極大成功。這個算法的理論根據(jù)是：當n是合數(shù)時，在1到n—1的整數(shù)中有一半以上是n為合數(shù)的“見證人”。算法的基本做法是：隨機地產(chǎn)生一個1與n—1之間的整數(shù)b，檢查6是否是n為合數(shù)的“見證人”。若6是“見證人”，則計算結(jié)束并得出n為合數(shù)的結(jié)論；否則重復(fù)這個過程。至多進行K次，若產(chǎn)生的K個隨機數(shù)^都不是n為合數(shù)的“見證人”，則得出n為素數(shù)的結(jié)論。算法所需要的時間為O(1OG3n)。當計算的結(jié)果是n為合數(shù)時，結(jié)果肯定是正確的。但是，“n為素數(shù)”的結(jié)果有可能是錯誤的。此時n為合數(shù)的概率，即得出錯誤結(jié)果的概率不超過1／2k。當k足夠大時，這是一個很小的數(shù)。譬如，取K=10，錯誤的概率小于0.001。這已經(jīng)是在實驗中不大可能發(fā)生的事件了。實驗表明，算法在實際使用中幾乎不會給出錯誤的結(jié)論。

拉賓的一個同事普拉特(V．R．Pratt)用拉賓的算法編寫了一個程序，在1975年冬找到了當時最大的素數(shù)2400—593以及最大的孿生素數(shù)AX338+821和KX338+823(A是小于300的所有素數(shù)的乘積)，創(chuàng)造了世界記錄。拉賓的算法目前仍然是尋找素數(shù)的最快算法之一。

概率算法在分布式計算、通信、信息檢索、計算幾何、密碼學等方面都有廣泛的應(yīng)用。目前，在連接高度并行的計算機的專用網(wǎng)絡(luò)上發(fā)送信息的算法就是拉賓的另一個同事瓦里安特(L．Valiant)所設(shè)計的一種隨機算法，這種算法不將信息直接發(fā)往目的地，而是先發(fā)送到任意一個節(jié)點，然后再由該節(jié)點發(fā)往目的地。瓦里安特證明這種看上去似乎瘋了的方法能有效地減少網(wǎng)絡(luò)中的競爭，避免阻塞。這正是隨機化的威力和魅力所在。在密碼技術(shù)中目前廣泛采用的公開密鑰體制(publickey)和RSA算法(Rivest—Shsmjr—Adlemanalgorithm)也使用了拉賓的隨機化和概率技術(shù)。當然，好的技術(shù)也可以用來干壞事：1988年11月在Internet上廣泛傳播的病毒正是拉賓在哈佛大學時的一個大學生羅伯特·莫里斯(RobertTappanMorris)利用學到的隨機化技術(shù)設(shè)計出來并加以傳播的。

斯科特比拉賓小一歲，1932年10月11日生于加利福尼亞州，在加州大學伯克利分校獲得學士學位以后，進入普林斯頓大學研究生院深造，與拉賓一起師從阿隆索·邱奇。邱奇對學生要求很嚴，布置的問題也很難，斯科特開始時難以適應(yīng)，精神很緊張，經(jīng)常夜里做惡夢。但經(jīng)過努力，終于可以從容應(yīng)付。1957年暑假他與師兄拉賓一起完成了對圖靈機的研究，提出非確定性有限狀態(tài)自動機的理論以后，在1958年取得博士學位。之后他先后在芝加哥大學、加州大學伯克利分校、斯坦福大學、荷蘭的阿姆斯特丹大學、普林斯頓大學和英國牛津大學等國際知名的高等學府任教。1981年被卡內(nèi)基—梅隆大學聘為計算機科學、數(shù)理邏輯和哲學教授。

斯科特的主要興趣和研究方向是邏輯學。他對邏輯學的研究涉及面很廣，包括集合論、模型論、自動機理論、非經(jīng)典邏輯中的模態(tài)邏輯(modallogic，表達“必然”與“可能”這樣一些概念的邏輯)和直覺主義邏輯(intuitionismlogic)。直覺主義邏輯是為克服數(shù)學研究中出現(xiàn)的悖論而提出的，由荷蘭數(shù)學家布勞維(L．E．J．Brawer，1881—1966)所創(chuàng)立。直覺主義邏輯認為數(shù)學是第一位的，邏輯是第二位的，邏輯只是數(shù)學思維的抽象，是正確的數(shù)學實踐的反映。而數(shù)學的唯一來臣源是數(shù)學思維中固有的一種帶構(gòu)造性的直覺。這些觀點和現(xiàn)今計算機科學與人工智能的研究相吻合，因而受到計算機科學家和人工智能專家的極大重視。斯科特在這些領(lǐng)域中都有不同程度的貢獻。

但斯科特的最大貢獻則是他與斯特雷奇(C．Strachey，1916—1975)合作，在20世紀60年代提出了程序設(shè)計語言的“標志語義模型”(denotationalsemanticmodel)，為標志語義學(denotationalsemantics)又稱數(shù)學語義學(mathematicalsemantics)奠定了堅實的基礎(chǔ)。在標言語義學出現(xiàn)之前，英國學者霍爾(，C．A．R．Hoare，1980年圖靈獎獲得者)已經(jīng)在對一階謂詞演算擴充了一組公理和一組推導(dǎo)規(guī)則的情況下建立起了公理語義學(axiomaticsemantics)作為程序設(shè)計語言語義形式化的一種方法，并曾被成功地用來描述Pascal等語言。但公理語義學是不完備的。標志語義學把語言中的每一成分與一個數(shù)學對象相對應(yīng)，稱為從前者到后者的映射，后者即稱為前者的“標志”(標志語義學的名稱即由此而來)。這個數(shù)學對象是某個區(qū)域的元素，該區(qū)域從數(shù)學上來說是一個“格”(1attice)，格中的偏序以“定義范圍小于等于”來確定。標志語義學還規(guī)定，這種映射是層次結(jié)構(gòu)的，映射函數(shù)則往往是遞歸的。這樣，語言中的每一元素既可解釋為一個函數(shù)，又可解釋為一個數(shù)據(jù)元素，這正好與程序的以下特性相吻合：既可把程序當作函數(shù)予以執(zhí)行，又可把程序當作二進制位串加以處理。標志語義學一經(jīng)誕生，就獲得了學術(shù)界廣泛的歡迎，不但被成功地用來定義Ada等大型程序設(shè)計語言，還被成功地用來定義大型數(shù)據(jù)庫和大型操作系統(tǒng)等，充分顯示了它的生命力。IBM公司的維也納實驗室后來還開發(fā)出元語言METAⅣ，成為用標志語義描述大型軟件的強有力工具。后來它進一步發(fā)展為維也納開發(fā)方法VDM(ViennaDevelopmentMethod)，成為支持程序開發(fā)的一般的形式化方式。國際標準化組織ISO正在制定有關(guān)VDM的規(guī)約語言VDM—SL(VDM—SpecificationLanguage)。

在建立標志語義學的過程中，為了奠定其