導語
——非確定性有限狀態自動機理論的開創者
1976年度的圖靈獎由當時在以色列希伯萊大學任教授的米凱爾，拉賓(Michael O．Rabin)和在英國牛津大學任數理邏輯教授的達納·斯科特(Dana Steward Scott)共同獲得。拉賓和斯科特是師兄弟，兩人在20世紀50年代中期先後師從著名的邏輯學家和計算機專家阿隆索·邱奇(Alonzo Church，他因與Curry一起發明了λ-演算以及提出了“任何計算，如果存在一有效過程，它就能被圖靈機所實現”這一被稱為“邱奇論題”的命題而聞名於世)，並在有限自動機及其判定問題的研究中進行合作，奠定了非確定性有限狀態自動機的理論基礎。之後，他們的研究方向不盡相同，拉賓側重於計算理論，而斯科特側重於邏輯學在計算機科學中的套用，在各自的領域中又分別獲得重大成果，作出了創造性貢獻。
個人簡歷
拉賓1931年9月1日生於德國的布雷斯勞(Breslau，第二次世界大戰以後成為波蘭的城市並改名為弗羅茨瓦夫)。他父親是一名猶太教教士，也是一位博士，在當時很著名的布雷斯勞神學院教猶太歷史和哲學，還當過院長。拉賓的母親也是知識分子，有文學博士頭銜，年輕時即開始從事兒童文學的創作。納粹希特勒上台以後，拉賓的父親因為曾經在俄羅斯呆過，憑著政治敏感性，預感到會有動盪和麻煩，曾建議神學院遷往耶路撒冷，未獲同意，於是全家於1935年遷回了巴勒斯坦，躲過了一劫。1948年以色列建國以後，他們成為以色列公民。
拉賓在瀕臨地中海的港口城市海法度過了他的童年和少年時代。由於閱讀了著名微生物學家保羅·德克呂夫(PaulDeKmif)所著的《微型獵人》一書，激起了拉賓的想像，幻想自己成為微生物學家。一次他和比他高好幾班的學生比試解歐幾里德幾何題，他贏了他們，這又使他對數學產生了興趣，因此，從萊利學院(RealiCollege)畢業以後，他進入希伯萊大學學習數學，在那裡，他通過數學家克林(S．C．Kleene，因提出不動點定理——theoremonfixpoint及正則集定理一theoremonregularset而聞名於世)所著的《元數學》一書首次接觸到圖靈關於可計算性的概念和圖靈機這一理論計算模型，立即被深深吸引。但為了打好自己的數學墓礎，他的碩土論文沒有以此為課題，而選擇了當時由德國女數學家埃米·諾特(EmmyNoether，1882—1932)創立不久的抽象代數中關於可交換環理論中的一個問題。獲得數學碩士學位以後，拉賓去了美國，因為20世紀50年代初，以色列建國伊始，經濟與科技都還不夠發達，很少有人研究計算這類問題，甚至連計算機都沒有。拉賓到美國後，先在賓夕法尼亞大學，後來轉到普林斯頓大學攻讀博士學位。拉賓的博士論文課題將他所熟悉的抽象代數和他感興趣的可計算性問題聯繫在一起：群(GROUP)的可計算性問題。拉賓在論文中證明了與群有關的許多問題，如群是否符合交換律等，都是不能由計算機解答的。
學習研究過程
但是使拉賓成名的並非其博士論文而是源於IBM研究中心於1957年向他和他的師弟斯科特提供的一份暑期工作。公司允許他們作他們感興趣的任何工作，於是拉賓和斯科特就聯手研究有限狀態自動機(finitestateautomata，縮寫FSA)。前人在研究這種機器時的基本信條是：機器在輸入相同時，其“心智狀態”也相同，即對於具有給定指令集的機器而言，一定輸入的機器總是按同一方式運行的。拉賓和斯科特認為，這種具有“確定性”行為的機器帶來了局限性。因此，他們定義了一種新的、“非確定性”的有限狀態自動機(nondeterministicfinitestateautomata，縮寫為NDFSA)，這種機器在讀取到一定的輸入後，有一個可以進入的可能的新的狀態的“選單”可供選擇，這樣對給定的輸入計算便不單一了，每個選擇代表一種可能的計算。拉賓和斯科特將圖靈的有限狀態自動機從確定性一種形態擴展到非確定性的另一種形態，極大地推動了有限狀態自動機理論的發展。雖然非確定性有限狀態自動機的能力並不比確定性的有任何增加(拉賓和斯科特自己已經證明任何可以用非確定性機器解決的問題都可以在確定性機器上解決，而且提出了將非確定性機器轉換為確定性機器的方法問題)，但是它可以簡化機器描述和加快解題速度。後來的實踐證明，非確定性有限狀態自動機在機器翻譯、文獻檢索和字處理程式等套用中都起了重要的作用。拉賓和斯科特的研究成果過了兩年才在IBM公司的研究和開發雜誌上發表，這就是論文“有限自動機及其判定問題”(Finiteantomataandtheirdecisionproblems，IBMJournalofResearchandDevelopment，3(1959)，114—125頁)。
參考文獻
ACM圖靈獎(1966-2001增訂版計算機發展史的縮影) 吳鶴齡，崔林編
參考資料：
1 http://www.math.org.cn/forums/index.php?showtopic=45808
2 http://deercrane.spaces.live.com/blog/cns!8BEF692B75EB8095!221.entry
