米凱爾·拉賓 - 導(dǎo)語

——非確定性有限狀態(tài)自動機(jī)理論的開創(chuàng)者

1976年度的圖靈獎由當(dāng)時在以色列希伯萊大學(xué)任教授的米凱爾，拉賓(Michael O．Rabin)和在英國牛津大學(xué)任數(shù)理邏輯教授的達(dá)納·斯科特(Dana Steward Scott)共同獲得。拉賓和斯科特是師兄弟，兩人在20世紀(jì)50年代中期先后師從著名的邏輯學(xué)家和計算機(jī)專家阿隆索·邱奇(Alonzo Church，他因與Curry一起發(fā)明了λ-演算以及提出了“任何計算，如果存在一有效過程，它就能被圖靈機(jī)所實現(xiàn)”這一被稱為“邱奇論題”的命題而聞名于世)，并在有限自動機(jī)及其判定問題的研究中進(jìn)行合作，奠定了非確定性有限狀態(tài)自動機(jī)的理論基礎(chǔ)。之后，他們的研究方向不盡相同，拉賓側(cè)重于計算理論，而斯科特側(cè)重于邏輯學(xué)在計算機(jī)科學(xué)中的應(yīng)用，在各自的領(lǐng)域中又分別獲得重大成果，作出了創(chuàng)造性貢獻(xiàn)。

米凱爾·拉賓 - 個人簡歷

拉賓1931年9月1日生于德國的布雷斯勞(Breslau，第二次世界大戰(zhàn)以后成為波蘭的城市并改名為弗羅茨瓦夫)。他父親是一名猶太教教士，也是一位博士，在當(dāng)時很著名的布雷斯勞神學(xué)院教猶太歷史和哲學(xué)，還當(dāng)過院長。拉賓的母親也是知識分子，有文學(xué)博士頭銜，年輕時即開始從事兒童文學(xué)的創(chuàng)作。納粹希特勒上臺以后，拉賓的父親因為曾經(jīng)在俄羅斯呆過，憑著政治敏感性，預(yù)感到會有動蕩和麻煩，曾建議神學(xué)院遷往耶路撒冷，未獲同意，于是全家于1935年遷回了巴勒斯坦，躲過了一劫。1948年以色列建國以后，他們成為以色列公民。

拉賓在瀕臨地中海的港口城市海法度過了他的童年和少年時代。由于閱讀了著名微生物學(xué)家保羅·德克呂夫(PaulDeKmif)所著的《微型獵人》一書，激起了拉賓的想象，幻想自己成為微生物學(xué)家。一次他和比他高好幾班的學(xué)生比試解歐幾里德幾何題，他贏了他們，這又使他對數(shù)學(xué)產(chǎn)生了興趣，因此，從萊利學(xué)院(RealiCollege)畢業(yè)以后，他進(jìn)入希伯萊大學(xué)學(xué)習(xí)數(shù)學(xué)，在那里，他通過數(shù)學(xué)家克林(S．C．Kleene，因提出不動點定理——theoremonfixpoint及正則集定理一theoremonregularset而聞名于世)所著的《元數(shù)學(xué)》一書首次接觸到圖靈關(guān)于可計算性的概念和圖靈機(jī)這一理論計算模型，立即被深深吸引。但為了打好自己的數(shù)學(xué)墓礎(chǔ)，他的碩土論文沒有以此為課題，而選擇了當(dāng)時由德國女?dāng)?shù)學(xué)家埃米·諾特(EmmyNoether，1882—1932)創(chuàng)立不久的抽象代數(shù)中關(guān)于可交換環(huán)理論中的一個問題。獲得數(shù)學(xué)碩士學(xué)位以后，拉賓去了美國，因為20世紀(jì)50年代初，以色列建國伊始，經(jīng)濟(jì)與科技都還不夠發(fā)達(dá)，很少有人研究計算這類問題，甚至連計算機(jī)都沒有。拉賓到美國后，先在賓夕法尼亞大學(xué)，后來轉(zhuǎn)到普林斯頓大學(xué)攻讀博士學(xué)位。拉賓的博士論文課題將他所熟悉的抽象代數(shù)和他感興趣的可計算性問題聯(lián)系在一起：群(GROUP)的可計算性問題。拉賓在論文中證明了與群有關(guān)的許多問題，如群是否符合交換律等，都是不能由計算機(jī)解答的。

米凱爾·拉賓 - 學(xué)習(xí)研究過程

但是使拉賓成名的并非其博士論文而是源于IBM研究中心于1957年向他和他的師弟斯科特提供的一份暑期工作。公司允許他們作他們感興趣的任何工作，于是拉賓和斯科特就聯(lián)手研究有限狀態(tài)自動機(jī)(finitestateautomata，縮寫FSA)。前人在研究這種機(jī)器時的基本信條是：機(jī)器在輸入相同時，其“心智狀態(tài)”也相同，即對于具有給定指令集的機(jī)器而言，一定輸入的機(jī)器總是按同一方式運行的。拉賓和斯科特認(rèn)為，這種具有“確定性”行為的機(jī)器帶來了局限性。因此，他們定義了一種新的、“非確定性”的有限狀態(tài)自動機(jī)(nondeterministicfinitestateautomata，縮寫為NDFSA)，這種機(jī)器在讀取到一定的輸入后，有一個可以進(jìn)入的可能的新的狀態(tài)的“菜單”可供選擇，這樣對給定的輸入計算便不單一了，每個選擇代表一種可能的計算。拉賓和斯科特將圖靈的有限狀態(tài)自動機(jī)從確定性一種形態(tài)擴(kuò)展到非確定性的另一種形態(tài)，極大地推動了有限狀態(tài)自動機(jī)理論的發(fā)展。雖然非確定性有限狀態(tài)自動機(jī)的能力并不比確定性的有任何增加(拉賓和斯科特自己已經(jīng)證明任何可以用非確定性機(jī)器解決的問題都可以在確定性機(jī)器上解決，而且提出了將非確定性機(jī)器轉(zhuǎn)換為確定性機(jī)器的方法問題)，但是它可以簡化機(jī)器描述和加快解題速度。后來的實踐證明，非確定性有限狀態(tài)自動機(jī)在機(jī)器翻譯、文獻(xiàn)檢索和字處理程序等應(yīng)用中都起了重要的作用。拉賓和斯科特的研究成果過了兩年才在IBM公司的研究和開發(fā)雜志上發(fā)表，這就是論文“有限自動機(jī)及其判定問題”(Finiteantomataandtheirdecisionproblems，IBMJournalofResearchandDevelopment，3(1959)，114—125頁)。

米凱爾·拉賓 - 參考文獻(xiàn)

ACM圖靈獎(1966-2001增訂版計算機(jī)發(fā)展史的縮影) 吳鶴齡，崔林編

參考資料：

1 http://www.math.org.cn/forums/index.php?showtopic=45808

2 http://deercrane.spaces.live.com/blog/cns!8BEF692B75EB8095!221.entry