可判定性：一個語言L，是一個集合，且其補集為
。當L是圖靈機可識别時，語言L則稱為半可判定。當語言L不是圖靈機可識别，則為不可判定語言。當且僅當L和都是圖靈機可識别的時候，L才能稱為可判定語言。
數理邏輯中的一個重要問題。它表現為尋求一種能行的方法、一種機械的程式或者算法，進而能夠對某類問題中的任何一個在有窮步驟内确定是否具有某一特定的性質。例如，命題邏輯的任一公式是不是常真這個問題，就可以在有窮步内按照一定的程式用真值表判定。如果對某類問題已經獲得這種能行的方法，就說明這類問題是可判定的，或者說其判定問題是可解的；如能夠證明某類問題不可能存在這樣的方法，就說這類問題不是能行可判定的。判定問題有不同的陳述。從語義方面考慮，判定問題是要确定一公式是否常真，亦即是否普遍有效，或者可否滿足；在文法方面，它是要确定某一公式是可證，還是可否證。
邏輯系統的判定問題 命題邏輯的任一公式是否常真以及是否可證都是能行可判定的。20世紀30年代美國數學家A.丘奇和英國的A.M.圖林分别證明了謂詞邏輯的判定問題是不可解的。對謂詞邏輯公式可以用前束範式分類，前束範式是一公式，其中一切量詞都未被否定地處于公式的最前方，謂詞邏輯的每一公式都和一前束範式等值或者可以互推。有些前束範式類是可判定的，例如隻含有全稱量詞的前束範式。1962年A.S.柯爾、E.F.摩爾和美籍華人學者王浩證明了不可判定的謂詞邏輯公式都可以歸約為凬ヨ凬式。這種不可判定的公式類型被稱為歸納類。
在數學系統裡，C.H.朗格弗德于1927年證明了自然數的線性序理論的判定問題是可解的。1929年，M.普利斯貝格證明了自然數的加法理論的判定問題是可解的。50年代初，A.塔爾斯基解決了初等幾何理論的判定問題。1970年，蘇聯學者Ю.В.馬季亞謝維奇證明了 D.希爾伯特所提出的23個著名數學問題中的第10個問題是不可解的。希爾伯特第10個問題是指尋找一個算法，用它能确定一任給的整系數多項式方程
p(x1,...,xn)=0
是否有整數解。結果證明，這樣的算法是不存在的。
證明一個理論的判定問題可解，隻需給出一個算法，并證明這算法就是所要求的，問題就解決了。要證明一個理論的判定問題是不可解的，首先需要把算法（機械程式）概念精确化，并給出算法概念的嚴格的數學定義，使一切算法的類成為明确的數學對象，進而能用嚴格的數學方法證明對某個理論來說不存在解決它的判定問題的算法。判定問題的研究推動了對算法理論或稱可計算性理論的研究，促進了遞歸函數論（見遞歸論）和圖林機器理論的建立。
能行性和可行性 從計算複雜性方面對可解的判定問題的研究證明，一些理論雖然原則上是可判定的，但它的判定程式（算法）所需的計算步數太大，以緻在實踐上是不可行的。例如，就可判定的自然數的加法理論來說，已經證明，對于該理論的每一判定算法，都有長度（即符号數目）為
n的語句（公式），使得依據該算法判定此語句是否可證需要計算
22cn步（c為>0的常數）。假如取n=10，那末即使使用每秒運算一億次的高速計算機作判定,也需要很多億個世紀。一個重要的問題是:是否存在某些可判定的理論。而且其判定方法是快速的,在實踐上是可行的。對于這個問題迄今未能作出肯定的或否定的回答。70年代以來，通過研究命題邏輯的判定方法的複雜性，發現了許多已知的組合型的判定問題都可化歸為命題邏輯的判定問題，如果能找到判定命題邏輯中的公式是否為重言式的快速算法，則可随之而獲得一大批判定問題的快速算法。但迄今這仍是懸案，既未能找到命題邏輯的快速判定算法，也未能證明不存在它的快速判定算法。
1936年，圖靈作出了他一生最重要的科學貢獻，他在其著名的論文《論可計算數在判定問題中的應用（On Computer numbers with an Application to the Entscheidungs -problem）》一文中，以布爾代數[i]為基礎，将邏輯中的任意命題（即可用數學符号）用一種通用的機器來表示和完成，并能按照一定的規則推導出結論。這篇論文被譽為現代計算機原理開山之作,它描述了一種假想的可實作通用計算的機器，後人稱之為“圖靈機”。 馮·諾依曼 1903年12月28日生于匈牙利，1957年2月8日死于美國。我想知道計算機的 人一定對他不會陌生，它可以稱為計算機之父了，現在我們面前計算機内采用的體系結構就是以他的命名的馮·諾依曼結構。
馮·諾依曼小時就十分聰明，1936到1938圖靈（另一位偉大的計算機科學家）是普林斯頓大學數學系的研究所學生，馮·諾依曼邀請圖靈當他的助手，可是圖靈鐘情于劍橋而未能如馮·諾依曼所願，一年後，二次世界大戰使圖靈卷入了戰争，1934年圖靈曾經發表的論文“On Computable Numbers with an Application to the Entscheidungs-problem”。不可不提，在這篇論文中，圖靈提出了通用機的概念，馮·諾依曼應該知道了這個思想，至少後來他是不是應用了這個思想卻不得而知。馮·諾依曼迅速發現了這種後來被稱之為計算機的通用機器的用處在于解決一些實際問題，而不是一個擺設，因為戰争的原因馮·諾依曼開始接觸到許多數學的分支，使他開始萌生了使用一台機器進行計算的想法，雖然我們現在都知道第一台計算機ENIAC有他的努力，可是在此之前他碰到的第一台計算機器是Harvard Mark I (ASCC)電腦。馮·諾依曼有一種非凡的溝通能力，能夠在不同的科學家之間擔任一個中介者的角色，雖然這些科學家并不想讓别人知道自己的秘密。馮·諾依曼建造的機器名為IAS機，一些由國家實驗室建造的計算機不過是IAS機的複本而已。
戰後馮·諾依曼繼續緻力于IAS機的開發工作，并幫助解決氫彈研制中的計算問題。在他死後，它在計算機界的名聲并不大，以至于他的傳記作家對他在計算機上的貢獻也隻一筆帶過。 “Entscheidungs”是德文，意為“decision”，中文“判定”。希爾伯特23問題中的一個。問題陳述如下：
尋找一種算法，這種算法的輸入為–>一個數學命題和描述這個數學問題的語言的全部資訊，輸出–>根據這個數學問題正确與否輸出“是”或“否”。這個算法不需要對它的結論給出任何另外的證明，隻需要給出“是”或“否”的回答，且回答必需正确。這個問題來源于萊布尼茲（Gottfried
Leibniz，就是開創微積分的人之一，用“高數”折騰無數中華學子）。他建立了一個機械式計算機，想用來判斷一個數學命題的真假。但他突然意識到需要一種規則的語言将數學命題描述清楚，于是就忙着處理這個問題去了。當然最後将這個問題被證明無解了。給出回答的是Church和Turing兩個人，他們分别從兩個不同方向對這個問題的無解性給出了回答。
Church開創了一種 叫λ
calculus的理論，用來定義“algorithm”，即什麼是算法。
Turing推出了他的一個思想模型“圖靈機”用來定義算法，後來被證明與Church的 λ
calculus理論是等價的。
最後Church把Entscheidungs
problem劃歸為自己的理論範疇内，并證明了這個問題的無解。Turing把圖靈機的不可解問題——Halting
Problem——約化成了Entscheidungs problem。
人們現在将Church和Turing的結論稱為：Church-Turing
Thesis。
Turing, A.M. (1936).
On Computable Numbers, with an Application to the Entscheidungs problem.
Proceedings of the London Mathematical Society. No.2, Vol.42:
230–65.
邱奇-圖靈論題
| 邱奇-圖靈論題(The Church-Turing thesis)是計算機科學中以數學家阿隆佐·邱奇(Alonzo Church)和阿蘭·圖靈命名的論題。該論題最基本的觀點表明，所有有計算或算法都可以由一台圖靈機來執行。以任何正常程式設計語言編寫都計算機程式都可以翻譯成一台圖靈機，反之任何一台圖靈機也都可以翻譯成大部分程式設計語言大程式，是以該論題和以下說法等價：正常的程式設計語言可以足夠有效的來表達任何算法。該論題被普遍假定為真，也被稱為邱奇論題或邱奇猜想和圖靈論題。 論題之等價形式本論題的另外一種說法就是邏輯和數學中的有效或機械方法可由圖靈機來表示。通常我們假定這些方法必須滿足以下的要求： 一個方法由有限多多簡單和精确的指令組成，這些指令可由有限多的符号來描述。 該方法總會在有限的步驟内産生出一個結果。 基本上人可以僅用紙張和鉛筆來執行。 該方法的執行不需人類的智慧來了解和執行這些指令。 此類方法的一個範例便是用于确定兩個自然數的最大公約數的歐基裡德算法。 “有效方法”這個想法在直覺上是清楚的，但卻沒有在形式上加以定義，因為什麼是“一個簡單而精确的指令”和什麼是“執行這些指令所需的智力”這兩個問題并沒有明确的答案。 (如需歐幾裡得算法之外的範例，請參見數論中的有效結果。) 論題之起源在他1936年年的論文“論可計算數字，及其在判定性問題(Entscheidungsproblem--德語，譯者注)中的應用”中，阿蘭·圖靈試圖通過引入圖靈機來形式地展示這一想法。在此篇論文中，他證明了“判定性問題”是無法解決的。幾個月之前，阿隆佐·邱奇在“關于判定性問題的解釋”(A Note on the Entscheidungsproblem)一文中證明出了一個相似的論題，但他采用但是遞歸函數和Lambda可定義函數來形式地描述有效可計算性。Lambda可定義函數由阿隆佐·邱奇和史蒂芬·克林(Stephen Kleene) (Church 1932, 1936a, 1941, Kleene 1935)，而遞歸函數由庫爾特·歌德爾(Kurt G?del)和雅克斯·赫爾不蘭特(Jacques Herbrand) (G?del 1934, Herbrand 1932)提出的。這兩個機制描述的是同一集合的函數，正如邱奇和克林(Church 1936a, Kleene 1936)所展示的正整數函數那樣。在聽說了邱奇的建議後，圖靈很快就證明了他的圖靈機實際上描述的是同一集合的函數(Turing 1936, 263ff).y 論題之成功之後用于描述有效計算的許多其他機制也被提了出來，比如寄存器機器(register machine), 埃米爾·波斯特(Emill Post)的波斯特體系, 組合可定義性(combinatory definability)以及馬可夫算法(Markov 1960)等。所有這些體系都已被證明在計算上和圖靈機擁有基本相同的能；類似的系統被稱為圖靈完全。因為所有這些不同的試圖描述算法的努力都導緻了等價的結果，是以現在普遍認為邱奇.圖靈論題是正确的。但是，該論題不據有數學定理一般的地位，也無法被證明;如果能有一個方法能被普遍接受為一個有效的算法但卻無法在圖靈機上允許，則該論題也是可以被駁斥的。在20世紀初期，數學家們經常使用一種非正式的說法即可有效計算, 是以為這個概念尋找一個好的形式描述也是十分重要的。當代的數學家們則使用圖靈可計算 (或簡寫為可計算)這一定義良好的概念. 由于這個沒有定義的用語在使用中已經淡去，是以如何定義它的問題幾經不是那麼重要了。 論題之哲學内涵邱奇.圖靈論題對于心智哲學(philosophy of mind)有很多寓意。有很多重要而懸而未決的問題也涵蓋了邱奇.圖靈論題和實體學之間的關系，還有超計算性(hypercomputation)的可能性。應用到實體學上，改論題有很多可能的意義： 宇宙是一台圖靈機(由此，在實體上對非遞歸函數的計算是不可能的)。此被定義為大邱奇.圖靈論題. 宇宙不是一台圖靈機(也就是說，實體的定律不是圖靈可計算的)，但是不可計算的實體事件卻不能阻礙我們來建立超計算機(hypercomputer)。比如，一個實體上實數作為可計算實數的宇宙就可以被劃為此類。 宇宙是一台超計算機, 因為建造實體裝置來控制這一特征并來計算非遞歸函數是可能的。比如，一個懸而未決的問題是量子力學的的事件是圖靈可計算的，盡管我們已經證明了任何由qubit所構成的系統都是(最佳)圖靈完全的。約翰·盧卡斯 (和羅格·本羅澤(Roger Penrose) 曾經建議說人的心靈可能是量子超計算的結果。 實際上在這三類之外或其中還有許多其他的技術上的可能性，但這三類隻是為了闡述這一概念。 |
補充材料
• Hofstadter,
Douglas R., Gödel, Escher, Bach: an Eternal Golden Braid, Chapter
17.
參考文獻
• Church, A., 1932, "A set of Postulates for the Foundation
of Logic", Annals of Mathematics, second series, 33, 346-366.
• Church,
A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal
of Mathematics, 58, 345-363.
• Church, A., 1936, "A Note on the
Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
• Church,
A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University
Press.
• Gödel, K., 1934, "On Undecidable Propositions of
Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the
Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The
Undecidable, New York: Raven.
• Herbrand, J., 1932, "Sur la
non-contradiction de l\'arithmetique", Journal fur die reine und angewandte
Mathematik, 166, 1-8.
• Kleene, S.C., 1935, "A Theory of Positive
Integers in Formal Logic", American Journal of Mathematics, 57, 153-173,
219-244.
• Kleene, S.C., 1936, "Lambda-Definability and Recursiveness",
Duke Mathematical Journal 2, 340-353.
• Markov, A.A., 1960, "The Theory
of Algorithms", American Mathematical Society Translations, series 2, 15,
1-14.
• Turing, A.M., 1936, "On Computable Numbers, with an Application
to the Entscheidungsproblem", Proceedings of the London Mathematical Society,
Series 2, 42 (1936-37), pp.230-265.
• Pour-El, M.B. & Richards,
J.I., 1989, Computability in Analysis and Physics, Springer
Verlag.
正如美國電腦界有馮·諾依曼一樣，在英國電腦的進展中，也有一個有巨大影響力的天才，他就是阿倫·圖靈（Alan
Turing）。此人對于電腦技術的發展，有着無可替代的影響。
英國現代計算機的起步的是從納粹德國的“謎”開始的。“謎”（Enigma）是一種密碼電報機，由德國人在一戰和二戰之間研制成功。“謎”能把日常語言變為代碼，通過無線電或電話線路秘密傳送。它是一個木箱子，配有一台打字機，箱上有26個閃爍不停的小燈泡，與打字機鍵盤的26個字母相對應。“謎”的設計無懈可擊，有一套極精密的解碼設定，非一般的電報密碼所能比拟。在内行人看來，平白如話，但在旁人，又是無從索解的天書。是以，這台看似平常的機器，有了“謎”的稱号。這樣，德國的“謎”引起了英國情報部門高度的興趣。正常的解碼方式奈何不了“謎”，怎麼辦？
這時，天才的數學家圖靈出現了。1931年圖靈進入劍橋大學國王學院，開始了他的數學天涯。一到那裡，圖靈開始嶄露頭角，畢業後去美國普林斯頓大學攻讀博士學位，在那裡就發明過一個解碼器（Encipher），二戰爆發後回到劍橋。
在劍橋，圖靈是一個婦孺皆知的怪才，常有出人意表的舉動。他每天騎自行車到離較高價的電梯大廈3公裡的一個叫布雷奇萊公園（Bletchley
Park）的地方上班，因常患過敏性鼻炎，一遇花粉，鼻涕不止，圖靈就常戴防毒面具騎車上班，招搖過市，成為劍橋的一大奇觀。
他的自行車鍊條經常在半道上掉落，要是換了别人，早就去車鋪修理了。而圖靈偏不，他在琢磨，發現這鍊條總是踏到一定的圈數時下滑，圖靈在騎車時就特别留心計算，于是能做到在鍊條下滑前一刹那戛然停車！讓旁人歎服不已，以為是在玩雜耍。後來他居然在踏腳旁裝了一個小巧的機械計數器，到圈數時就停，好換換腦筋想些别的問題。圖靈的腦袋轉得比自行車飛輪還快。
用圖靈的腦袋來破譯德國的“謎”看來不是什麼難事。二戰爆發後，圖靈成為英國外交部通信部門戰時公務員，主要負責解碼。他果然不負衆望，成功破譯了“謎”。而德國人還蒙在鼓裡，還以為他們的“謎”能一直迷下去，照用不誤，洩露了大量的核心機密，在戰事上屢屢遭挫，戰後，圖靈被授予帝國勳章。至于圖靈如何破譯“謎”的，由于英國政府嚴格的保密法令，一直沒有公之于世。是以圖靈破譯“謎”也成為一個“謎”。
早在30年代初，圖靈就發表了一篇著名的論文《論數字計算在決斷難題中的應用》，他提出了一種十分簡單但運算能力極強的理想計算裝置，用它來計算所有能想象得到的可計算函數。它由一個控制器和一根假設兩端無界的工作帶組成，工作帶起着存儲器的作用，它被劃分為大小相同的方格，每一格上可書寫一個給定字母表上的符号。控制器可以在帶上左右移動，控制帶有一個讀寫頭，讀寫頭可以讀出控制器通路的格子上的符号，也能改寫和抹去這一符号。
這一裝置隻是一種理想的計算模型，或者說是一種理想中的計算機。正如飛機的真正成功得力于空氣動力學一樣，圖靈的這一思想奠定了整個現代計算機的理論基礎。這就是電腦史上與“馮·諾依曼機器”齊名的“圖靈機”。
圖靈機被公認為現代計算機的原型，這台機器可以讀入一系列的零和一，這些數字代表了解決某一問題所需要的步驟，按這個步驟走下去，就可以解決某一特定的問題。這種觀念在當時是具有革命性意義的，因為即使在50年代的時候，大部分的計算機還隻能解決某一特定問題，不是通用的，而圖靈機從理論上卻是通用機。在圖靈看來，這台機器隻用保留一些最簡單的指令，一個複雜的工作隻用把它分解為這幾個最簡單的操作就可以實作了，在當時他能夠具有這樣的思想确實是很了不起的。他相信有一個算法可以解決大部分問題，而困難的部分則是如何确定最簡單的指令集，怎麼樣的指令集才是最少的，而且又能頂用，還有一個難點是如何将複雜問題分解為這些指令的問題。
此後圖靈在國家實體學實驗室（NPL）工作，并繼續為數字式計算機努力，在那裡人發明了自動計算機（Automatic
Computing
Engine，ACE），在這一時期他開始探索計算機與自然的關系。他寫了一篇名為《智能機》的文章于1969發表，這時便開始有了人工智能的雛形。
圖靈相信機器可以模拟人的智力，他也深知讓人們接受這一想法的困難，今天仍然有許多人認為人的大腦是不可能用機器模仿的。而在圖靈認為，這樣的機器一定是存在的。圖靈經常和其它科學家發生争論，争論的問題就是機器實作人類智能的問題，在今天我們看來這沒有什麼，但是在當時這可不太容易被人接受。他經常問他的同僚，你們能不能找到一個計算機不能回答的問題，當時計算機處理多選問題已經可以了，可是對于文章的處理還根本不可能，但今天的發展證明了圖靈的遠見，今天的計算機已經可以讀寫一些簡單的文章了。
圖靈相信如果模拟人類大腦的思維就可以做出一台可以思考的機器，它于1950寫文章提出了著名的“圖靈測試”，測試是讓人類考官通過鍵盤向一個人和一個機器發問，這個考官不知道他現在問的是人還是機器。如果在經過一定時間的提問以後，這位人類考官不能确定誰是人誰是機器，那這個機器就有智力了。這個測試在我們想起來十分簡單，可是偉大的思想就源于這種簡單的事物之中。
現在已經有軟體可以通過圖靈測試的子測試，軟體這個人類智慧的機器反映應該可以解決一些人類智力的問題。在完成ACE之前，圖靈離開了NPL，它在曼徹斯特大學開發曼徹斯特自動計算機（Manchester
Automatic Digital
Machine，MADAM）。他相信在2000年前一定可以制造出可以模拟人類智力的機器，圖靈開始創立算法，并使用MADAM繼續他的工作。
圖靈對生物也十分感興趣，他希望了解生物的各個器官為什麼是這個樣子而不是那個樣子，他不相信達爾文的進化論，他覺得生物的發展與進化沒什麼關系。對于生物學，他也用它鐘愛的數學進行研究，它的研究對他進行計算機的研究有促進作用。它把生物的變化也看做是一種程式，也就是圖靈機的基本概念，按程式進行。最後，這位偉大的計算機先驅于1954年6月7日去世，他終生未娶。
約翰.麥卡錫
--"人工智能之父"和LISP語言的發明人
1971年的圖靈獎授予提出"人工智能"這一術語并使之成為一個重要的學科領域的斯坦福大學教授約翰.
麥卡錫（ John
McCarthy)。
麥卡錫1927年9月4日生于波士頓。他的父親是一個愛爾蘭移民，做過木匠和漁夫，同時也是一個發明家和工會積極分子，擁有撚船縫機和桔汁冷凍機兩項專利。麥卡錫的母親是來自立陶宛的猶太人，熱心于*女*權運動，當過記者。夫妻兩人在20世紀30年代都曾參加美國gcd。受父母的影響，麥卡錫對社會問題也比較關注，參與過在加州的Palo
Alto 創辦自由大學的活動，倡議過修改"人*權*法*案"（the Bill of
Rights，這是美國于1789年通過的對美國憲法的第一次修正案）。但與他在計算機科學上所做的工作和貢獻相比，麥卡錫主要還是一個科學家而非社會活動家。此外，麥卡錫還喜歡攀登、跳傘、駕駛滑翔機等有刺激性和危險性的運動，曾和他的第二任妻子維拉.沃特森(Vera
Watson)一起攀登過世界上不少大山高峰。沃特森是一位程式員，也是世界知名的女登山運動員，是第一位獨自攀上西半球第一高峰、位于阿根廷和智利邊界的安第斯山脈的阿空加瓜山（海拔6960米）的女性，後來在一次攀登位于尼泊爾中部的阿那波爾那峰（海拔8
075米）的婦女探險活動中不幸遇難犧牲。
麥卡錫是一個天賦很高的人，還在上國中時，他就弄了一份加州理工大學的課程目錄，按目錄自學了大學低年級的高等數學教材，做了教材上的所有練習題。這使他1944年進入加州理工學院以後可以免修頭兩年的數學，并使他雖因戰時環境（第二次世界大戰當時正在進行之中，美國也在珍珠港事件後宣布參戰）要在軍隊中充任一個小職員，占去了部分時間，仍得以在1948年按時完成學業。然後到普林斯頓大學研究所學生院深造，于1951年取得數學博士學位。麥卡錫留校工作兩年以後轉至斯坦福大學，也隻呆了兩年就去達特茅斯學院任教（達特茅斯學院位于新罕布什爾州的漢諾威）。在那裡，他發起了并成功舉辦了成為人工智能起點的有曆史意義的"達特茅斯會議"。1958年麥卡錫到MIT任職，與明斯基(L.
Minsky,1969年圖靈獎獲得者)一起組建了世界上第一個人工智能實驗室，并第一個提出了将計算機的批處理方式改造成為能同時允許數十甚至上百使用者使用的分時方式（time-sharing）的建議，并推動MIT成立組織開展研究。其結果就是實作了世界上最早的分時系統--基于IBM
7094的CTSS和其後的MULTICS。麥卡錫雖因主持該課題的負責人産生沖突而于1962年離開MIT重返斯坦福，未能将此項目堅持到底，但學術界仍公認他是分時概念的創始人。麥卡錫到斯坦福後參加了一個基于DEC
PDP -1的分時系統的開發，并在那裡組建了第二個人工智能實驗室。
麥卡錫對人工智能的興趣始于他當研究所學生的時候。1948年9月，他參加了一個"腦行為機制"的專題讨論會，會上，馮.諾伊曼發表了一篇關于自複制自動機制論文，提出了可以複制自身的機器的設想，這激起了麥卡錫的極大興趣和好奇心，自此就開始嘗試在計算機上模拟人的智能。1949年他向馮.諾伊曼談了自己的想法，後者極表贊成和支援，鼓勵他搞下去。在達特茅斯會議前後，麥卡錫的主要研究方向是計算機下棋。下棋程式的關鍵之一是如何減少計算機需要考慮的棋步。麥卡錫經過艱苦探索，終于發明了著名的α-β搜尋法中，麥卡錫将結合的産生與求評價函數值（或稱返上值或倒推值）兩者巧妙地結合起來，進而使某些子樹結點根本不必産生與搜尋（這謂之"修剪"--pruning或cutoff）。之是以稱為α-β搜尋法，是因為将處于取最大值級的結點的返上值或候選返上值PBV（Provisional
Back-up
value）稱為該結點的α值，而将處于取最小值級的結點的候選返上值或返上值稱為該結點的β值。這樣，在求得某結點以下的α值時，就可與其先輩結點的α值相比較，若α≥β，
則可終止該結點以下的搜尋，即從該結點處加以修剪，這叫β修剪；而在求得某結點以下的β值時，就可與其先輩結點的α值相比較，若β≤α，則可終止該結點以下的搜尋，即從該結點處加以修剪，這叫α修剪。為了說明α-β修剪，我們舉一個最簡單的例子。設在取火柴棍的遊戲中，A、B兩人輪流從N根火柴中取1根或2根，不得多取，也不能不取。取走最後一根火柴者勝。用A(n)、B(n)表示輪到A或B時有n根火柴的狀态，當n
=
5時輪到A取，則如下圖所示，A有兩種可能，一是取2根火柴進入B（3），另一是取1根火柴進入B（4）。顯然，進入B（3）後，不管B取幾根，A必勝，故A必走這一步，餘下的分支不必再搜尋了。α-β搜尋法至今仍是解決人工智能問題中一種常用的高效方法。
至于達特茅斯會議，當東道主的麥卡錫是主要發起人，另外3個發起人是當時在哈佛大學的明斯基（1969年圖靈獎獲得者），IBM公司的羅傑斯特(N.
Rochster)，資訊論的創造人香農。麥卡錫發起這個會議時的目标非常宏偉，是想通過10來個人2個有共同努力設計出一台具有真正智能的機器。會議的經費是洛克菲勒基金會資助的，包括每個代表1200美元加上外地代表的往返車票。會議的原始目标雖然由于不切實際而不可能實作，但由于麥卡錫在下棋程式尤其是α-β搜尋法上所取得的成功，以及卡内基-梅隆大學的西蒙(H.
A.Simon)和紐厄爾（A.
Newell,這兩人是1975年圖靈獎獲得者）帶來了已能證明數學名著《數學原理》一書第二章52個定理中的38個定理的啟發式程式"邏輯理論家"LT（Logic
Theorist）,明斯基帶來的名為Snarc的學習機的雛形（主要學習如何通過迷宮），這使會議參加者仍能充滿信心地宣布"人工智能"這一嶄新學科的誕生。
1959年，麥卡錫基于阿隆索.邱奇(Alonzo
Church)的λ-演算和西蒙、紐厄爾首創的"表結構"，開發了著名的LISP語言（LISt Processing
language），成為人工智能界第一個最廣泛流行的語言。LISP是一種函數式的符号處理語言，其程式由一些函數子程式組成。在函數的構造上，和數學上遞歸函數的構造方法十分類似，即從幾個基本函數出發，通過一定的手段構成新的函數。LISP語言還具有自編譯能力。具體說來，LISP有以下幾個主要特點：
1．計算用的符号表達式而不是數； 2．具有表處理能力，即用連結清單形式表示所有的資料；
3．控制結構基于函數的複合，以形成更複雜的函數； 4．用遞歸作為描述問題和過程的方法；
5．用LISP語言書寫的EVAL函數既可作為LISP語言的解釋程式，又可以作為語言本身的形式定義；
6．程式本身也同所有其他資料一樣用表結構形式表示。
已經證明，LISP的這些特點是解決人工智能核心問題的關鍵。此外，精巧的表機制也是進一步簡化LISP程式設計的友善而有力的工具，是以，LISP自發明以來，已經被廣泛用于數學中的符号微積分計算，定理證明，謂詞演算，博奕論等領域。它和後來由英國倫敦大學的青年學生柯瓦連斯基（R.
Kowaliski）提出、由法國馬賽大學考爾麥勞厄（A.
Colmerauer）所上司的研究小組于1973年首先實作的邏輯式語言PROLOG(PROgramming in
LOGic)并稱為人工智能的兩大語言，對人工智能的發展起了十分深遠的意義也吸引了負責設計Algol語言的國際委員會，麥卡錫是以而被吸收為該委員會的成員。Algol中後來采納了LISP關于遞歸和條件表達式這些思想。
麥卡錫在20世紀50年代末研究的另一個課題是如何程式能接受勸告進而改善其自身的性能。為此他提出過一個名為Advice
Taker的系統的設想。有資料說，這是世界上第一個展現知識擷取工具思想的系統，1968年建成。實際上，這個系統并未最後完成，隻是完成了一部分，用LISP語言建立起了一個具有常識(common
sense)的軟體，能了解告訴它的是什麼，并能評估其行動的後果。但正是在Advice
Taker的開發過程中，啟發麥卡錫提出了用"分時系統"代替"批處理系統"的建議，使計算機的使用方式引發了一場革命。
除了人工智能方面的研究和貢獻這外，麥卡錫也是最早對程式邏輯進行研究并取得成果的學者之一。１963年他發表的論文"計算的數學理論的一個基礎"一文（收錄于P.
Braffort和D. Hirschberg編輯的《計算機程式設計和形式系統》--Computer Programming and Formal
Systems, North Holland,
33-70頁）集中反映了他這方面的成果。麥卡錫在這篇論文中系統地論述了程式設計語言形式化的重要性，以及它同程式正确性、語言的正确實作等問題的關系，并提出在形式語義研究中使用抽象文法和狀态向量等方法，開創了"程式邏輯(logics
of
programs)研究的先河。程式邏輯就是一種"語言"，用這種語言可以無二義地表達程式的各種性質，其語義規定了該語言中各種表達式的意義，而它的一組規則則用同意義相關的方式去操作這些表達式以計算該語言中的各種斷言(assertation)的真值。研究程式的邏輯對于幫助人們了解軟體是否合理十分重要，它可以用于程式的邏輯對于幫助人們了解軟體是否合理十分重要，它可以用于程式驗證(program
verification)，自動程式設計，為優化和審計而進行的程式分析等方面。麥卡錫在上述論文中提出的方法是用遞歸函數作為程式的模型。他以兩個連結清單(list)的"附加"(append)操作為例說明可以用遞歸的方法定義這個函數，并可以用形式化的方法證明連結清單的附加操作是滿足結合律的(associative
law ),即x @ (y @ z) = (x @ y) @
z。麥卡錫進而證明了用一系列遞歸定義的函數就完全可能建造大型的軟體系統，并用歸納法證明這些系統所具有的性質。麥卡錫所提出的方法是有關程式邏輯研究中第一個比較系統而成熟的方法，曾被廣泛地采用。
20世紀70年代以後，麥卡錫又開始研究非單調邏輯。在經典邏輯中，由已知事實推出的結論，決不會在已知事實增加時反而喪失其有效性，是以是"單調的"(monotonic)。但在人類思維過程中，由于資訊的不完全和認識的局限性，常常有随着事物的發展變化，原有結論被否定和取消的情況，這就導緻了所?"非單調邏輯"(nonmonotonic
logic)。非單調邏輯中有一類是基于最小化語義的最小化非單調邏輯。1980年，麥卡錫在一篇論文中提出了"限制邏輯"或稱"限界邏輯"，成為這類非單調邏輯中比較成功的一個體系(見J.
McCarthy：Circumscription--a form of nonmonotonic reasoning. Artificial
Intelligence
,Vol.13，1980，27-39頁)。限制邏輯的基本思想是："限制"某個謂詞P也就是排除以P的原有事實為基礎所建立的大部分模型，而隻保留有關P的最小模型。這與人類思考問題時總是在某些條件限制下考慮，也就是隻考慮所涉及的個體或關系，而決不去涉及其他個體或關系，是比較相符的。1986年，麥卡錫在AI雜志上就限制邏輯的應用發表了進一步的研究論文："限制邏輯在常識知識形式化中的應用"(Applications
of Circumscription to Formalizing Common Sense Knowledge, AI,
Vol.28，1986，89-116頁)，對倡導常識推理和常識研究起了十分重要的作用。
麥卡錫的主要著作有：
《自動機研究》（Automata Studies, Princeton Uni. Pr.,1956,與香農合編）
《資訊學：科學美國人之書》(Information：A Scientific American Book, Freeman, 1966)
《形式化的常識：麥卡錫論文選集》(Formalizing Common Sense：Papers by John McCarthy , Ablex
Pub.
Co., 1990, 蒝. Lifschitz 編輯)
除了獲得圖靈獎以外，麥卡錫在1988年獲得由日本INAMORI基金會所設立的KYOTO獎，這個獎主要獎勵在高科技方面作出傑出貢獻的科學家，麥卡錫是這個獎的第5位獲得者。1990年麥卡錫獲得美國全國科學獎章
(National Medal of Scien- -ce)。 麥卡錫的圖靈獎演說題為"人工智能研究的現狀"(The
Present State of Research on Artificial
Intelligence)。但不知什麼原因，這篇演說沒有發表。在《前20年的圖靈獎演說集》(ACM Turing Award
Lectures--The First 20 Years：1966-1985 ，ACM
Pr.)中，則以"附錄"(postscript)的形式約請麥卡錫另寫了一篇"人工苣一般原理"(Generality
in Artificial
Intelligence),刊于該書257-268頁。
麥卡錫現仍在斯坦福大學計算機科學系任教，其電子信箱為： [email protected] 出自《ACM圖靈獎——計算機發展史的縮影》（高等教育出版社）
Rule of Simplicity
(by C.A.R. Hoare) -
-
"There
are a number of ways of constructing a software design.
One way is to make it
so simple that there are obviously no deficiencies,
and the other way is to
make it so complicated that there are no obvious deficiencies." -- C.A.R.
Hoare
查爾斯·霍爾
---從QUICKSORT、CASE到程式設計語言程式設計語言的公理化
學過“資料結構”或“算法設計與分析”的人都知道著名的快速排序算法QUICKSORT；編過程式的人大概也都用過實作條件轉移的最友善的語句CASE語句。但是你知道這個算法和這個語句是誰發明的嗎?它們的發明者就是1990年IEEE計算機先驅獎和1980年圖靈獎的獲得者英國牛津大學計算機科學家查爾斯·霍爾(Charles
AntonyRichard
Hoare)。當然霍爾之是以獲得這兩項大獎決不僅僅是因為他發明了QUICKSORT和CASE，而是因為他在計算機科學技術的發展中，尤其是在程式設計語言的定義和設計、資料結構和算法、作業系統等許多方面都起了重要的作用，有一系列發明創造，QUICKSORT和CASE隻是其中的一小部分而已。
霍爾于1934年1月11日誕生于英國南部。在坎特伯雷(Canter·bury)的國王學校(King’s
Sch001)度過中學階段以後，進入牛津的莫頓學院(Merton
College)學習數學，1960年取得碩士學位。之後他進入倫敦一家不大的計算機生産廠家Elliott Brothers公司，為該公司的Elliott
803計算機編寫庫子程式，從此開始他的計算機生涯。QUICK，SORT就是他在那個時候用原有的SHELLSORT(以算法的發明人D．L．Shell命名的通過調換并移動資料項實作排序的一種算法，發明于1959年)程式設計時分析了它的缺點而發明出來的。QUICKSORT具有“快刀斬亂麻”的特點，能迅速地對亂序作大幅度調整，特别适合于因多次追加、删除而變得雜亂無章的資料集合。QUICKSORT是利用“分治法”(divide
and
conquer)進行算法設計的一個成功範例，它的發明是霍爾在計算機方面的天才的第一次顯露，受到老闆的贊賞和重視。第二年，霍爾接受了一個新的任務，為公司的新機型Elliott
503設計一個新的進階語言。但就在其時，他弄到了一份Algol
60報告的影印件，還參加了一個由狄克斯特拉(E．W．D恥stra，首屆計算機先驅獎獲得者)等人在布賴頓舉辦的Algol
60教育訓練班，感到與其自己沒有把握地去設計一個新的語言，還不如将比較成熟的Algol 60在Elliott
503上加以實作。霍爾和他的同僚們的這個想法獲得公司同意以後，由霍爾主持設計與實作了Algol
60的一個子集的版本。霍爾在開發初首先制定了明确的目标，即系統要安全可靠，生成的目标碼要簡潔，工作區資料要緊湊，過程和函數的人口和出口要清晰、嚴密等，還明确了整個編譯過程采用一次掃描等原則。這樣，ElliottAl-gol的開發十分順利與成功，它在1963年中推出以後大受歡迎，成為世界各國所開發的Algol
60的各種版本中在效率、可靠性和友善性等方面的性能名額都首屈一指的一個版本，霍爾本人也從此受到國際學術界的重視。國際資訊處理聯盟IFIP後來任命霍爾為2．1工作組(WorkingGroup
2．1)的負責人，這個工作組的任務是維護和發展Algol。霍爾果然不負衆望，主持設計了Algol
X以繼承與發展Algol60。正是在AlgolX的設計中，霍爾發明了CASE語句。CASE語句具有如下形式的文法結構：
CASE E of
C1:S1；
C2:S2；
.
.
.
Cn-1:Sn-1;
Otherwise:Sn
End
其中E是一個表達式，稱為“選擇子”(Selector)，每個Ci的值為常數，稱為“分情形标号”，Si則為可執行語句。CASE語句的含義是：若E的值等于某個Ci的值，則執行其後的Si(i=1，2，3，…，n—1)，否則執行Sn。某個Si或S。執行完之後，整個CASE語句也就執行完畢。由于CASE語句構成多路分支，程式結構清晰、直覺，是以CASE語句後來幾乎成為程式設計語言的标準，被各種語言廣泛采用。在C語言中，沒有獨立的CASE語句，但它的SWITCH語句(開關語句)實際上是在CASE語句的基礎上形成的：
switch E
{case
C1:S1；
case
C2:S2；
.
.
.
case
Cn-1:Sn-1;
[default:Sn]
不同之處有二：一是C；可以是表達式，但計算結果必須仍是常數；二是E的結果若不等于某個Ci(i=1，2，3，…，n—1)的值，則視有無default子句，若有，執行Sn；若無，則什麼也不執行，控制轉向SWITCH後的語句。顯然，這些都是對CASE語句的進一步改進。
霍爾于1968年離開Elliott，離開産業界，原因是作為學者他對程式設計浯言的形式化定義這類更偏重于學術性和理論性的課題更感興趣。離開Elliott以後，他任職過一年英國國家計算中心主任，發現自己也不适于從事行政管理，是以又轉入愛爾蘭的昆土大學(Queen’s
University)，從事教學和研究，1977年轉入牛津大學。離開Elliott以後，霍爾在計算機科學理論的研究中發揮其特長，作出了許多創造性的重大貢獻。首先是1969年10月，霍爾在Communications
of ACM上發表了他那篇有裡程碑意義的論文“計算機程式設計的公理基礎”(An Axiomatic Basis for Computer
Programming)。在這篇論文中，霍爾提出了程式設計語言的公理化定義方法，即公理語義學(axiomatic
semantics)，也就是用一組公理和一組規則描寫語言應有的性質，進而使語言與具體實作的機器無關，而且也易于證明程式的正确性。這是繼麥卡錫(J．McCarthy，1985年計算機先驅獎獲得者)在1963年提出用遞歸函數定義程式、弗洛伊德(R．W．Floyd，1991年計算機先驅獎獲得者)在1967年提出基于程式流程圖的歸納斷言法以後，在程式邏輯研究中所取得的又一個重大技術進展。霍爾提出的方法在邏輯上與弗洛伊德提出的方法類似，但不是用流程圖而是用代數法，即控制流用以下一些結構表示：
begin al；a2；a3；…；an end
if p
then a1 else a2
while p do a
後面為了友善，我們用到第一個結構時省略首尾的begin和end。
相應于弗洛伊德的驗證條件，霍爾引入下列符号：
p{a}q
其意義是：如果在執行。之前P(叫做precondition)成立，則當α執行完了後q(叫做postcondition)成立。
霍爾給出了以下一組證明規則(proof rule)或叫推導規則：
p’ pp{a}qq→q’
1.
p’{a}q’
這個規則中的p’→和q’→q是普通數理邏輯中的斷言命題，表示若p’(或q’)成立，則p(或q)成立。這個規則表示，若橫線以上的p’→p、p{a}q、q→q’成立，則橫線以下的p’{a}q1成立。
2．
P(e){x:=e}p(x)
這個規則表示，如果在将e賦給x之前p(e)成立，則其後p(x)成立。
3．
P{a}qq{b}r
p{a;b}r
這個規則表示的是“傳遞律”(transitive
law)，即如果執行α之前p成立，α執行完了以後q成立；而如果執行b之前q成立，b執行完了以後r成立，則若在動作序列。和^執行之前P成立，則a和b執行完了以後r成立。
4. p∧r{a}qp∧～r(b)q
p{if r then a else b}q
這個規則中的∧和～是一般數理邏輯中的合取(conjunction)和否定(negation)連接配接詞。這個規則定義了if-then-else的執行取決于precondition
r的值。
5.
p∧q{a}p
p{while q do a}p∧～q
這個規則定義了while循環：p是循環不變量（loop invariant），而q是終止循環的條件。
下面我們舉一個例子說明如何用霍爾建立的系統驗證程式的正确性。設有計算n的階乘n！的如下程式：
A: x:1;B
B: while y>0 do
C
C:
x:y×x;y:=y-1
則通過下列霍爾斷言可以證明上述程式是正确的，因為這些斷言都是真的，而且在霍爾的系統中是可以被證明的，而最後一個斷言正是我們所要尋求的結論，是以它們形成對上述階乘程式正确性的說明。
i.
y>0∧x×y! =n! {x:=y×x}y>0∧x×(y-1)! =n!
[首先y>0∧x×y!
=n!→y>0∧(y×x)×(y-1)! =n!]
然後用規則（2），用x代替y×x]
ii. y>0∧x×(y-1)!
=n!{y:=y-1}y≥0∧x×y! =n!
[類似（i），利用規則（2）]
iii．y>0∧x×y! =n!
{C}y≤0∧x×y! =n!
[對(i)和(ii)用規則(3)]
iv．Y≥0∧y=n∧x=1{B}x=n!
[因為] y=n∧x=1→x×y!
=n!
又因為0！ =1，是以Y≥0∧x×y!
=n! ∧y≤0→y=0∧x=n! →x×y! =n!
根據（iii），利用規則（5），令（5）中p=y≤0∧x×y!
=n!，q=y>0，孥可得(iv)]
v.
y≥0∧y=n{x:=1}y≥0∧y!=n∧x=1
[因為p{x:=1}p∧x=1]
vi.
y≥0∧y=n{A}x=n!
[對（V）和(Vi)利用規則(3)]
因為(vi)中的precondition正好是n的初始條件，而postcondition給出了所需結果，這樣就證明了程式可算出n!。
為了給出證明，應該從程式的最後一行開始逐漸後推。在這個例子中，(iii)步是最關鍵的，其中y≥0∧x×y! =n!就是循環不變量或歸納假設(induction
hypothesis)。
利用霍爾提出的這種方法，已經成功地描述了PASCAL等語言，說明了這個方法的巨大威力。但應該指出的是，霍爾的這個方法是不完備的，因為霍爾在開發和建立這個系統時并沒有追求系統的完備性，而更多地追求系統的實用性。
在資料類型、資料結構和作業系統設計等方面，霍爾也做了許多開創性的工作。目前廣泛流行與應用着的許多概念都源于霍爾的工作。例如，關于抽象資料類型的規格說明(Specification，也叫規約)與其實作是否一緻，就是由霍爾于1972年公式化了的。霍爾通過前後斷言方法用已經定義了的(抽象)資料類型給出所要定義的新類型的抽象模型，這成為抽象資料類型規格說明的兩種主要方法之一，即模型方法(另一方法為基于異調代數理論的代數方法)。對于作業系統的設計與實作十分關鍵的monitor(監控程式)的概念也是霍爾首先提出，并界定了它的作用與功能，即作為作業系統的核心，在把作業系統看做虛拟機擴充時，monitor是硬體的第一次擴充，它完成中斷處理、程序控制與程序通信、存儲區動态配置設定，建立軟時鐘，驅動裝置通道，進行處理機排程。monitor為外面各層的設計提供良好的環境，并提高系統的安全性。
20世紀70年代後期，霍爾又深入研究了運作在不同的機器上的若幹個程式之間如何互相通信、互相交換資料的問題，實作了面向分布式系統的程式設計語言CSP。在該語言中，一個并發系統由若幹并行運作的順序程序組成，每個程序不能對其他程序的變量指派。程序之間隻能通過一對通信原語實作協作：Q?x表示從程序Q輸入一個值到變量x中；P!e表示把表達式e的值發送給程序戶。當戶程序執行Q?x，同時口程序執行戶!‘時，發生通信，e的值從Q程序傳送給戶程序的變量x。CSP語言後來成為著名的并行處理語言OCCAM(由INMOS公司為Transputer開發)的基礎。20世紀80年代中期，霍爾又和布魯克斯(S．Brooks)等人合作，提出了“CSP理論”TCSP(Theory
Of Communicating Sequential
Processes)，它與上述CSP不同，但又有聯系，這是一個代數演算系統，其基本成分是事件(或動作)。程序由事件和一組算子構造而成。TCSP采用“廣播式通信”，而不像程式設計語言CSP中那樣采用握手式通信，即隻有當并行運作的各程序都執行同一動作時，才發生通信。此外，TCSP采用失敗等價作為确定程序等價的準則，這就是著名的“失敗語義”。利用失敗可以構造TCSP的指稱模型。霍爾為失敗等價建立了一些公理系統，可以對語義上的等價關系進行形式推導。霍爾在這方面的工作開創了用代數方法研究通信并發系統的先河，形成了所謂“程序代數”(process
algebra)這一新的研究領域，産生了很重要的影響。
霍爾的論著極多，而且都很有份量，有很高的學術水準。有評論說，霍爾每發表一篇論文，幾乎就要改變一次人們對程式設計的認識。這雖然是一種誇張的說法，但也說明霍爾的論著确實非常重要。ACM在1983年評選出最近四分之一個世紀中發表在Communications
of
ACM上的有裡程碑式意義的25篇經典論文，隻有兩名學者各有2篇論文人選，霍爾就是其中之一(另一名是首屆計算機先驅獎獲得者狄克斯特拉)。霍爾人選的兩篇論文分别是1969年10月的“計算機程式設計的公理基礎”(An
Axiomatic Basis for Computer
Programming，這篇論文的要點我們前面已經介紹過了)，另一篇是1978年8月的“通信順序程序”(Communicating Sequential
Processes)，該論文奠定了前述CSP語言的基礎。CSP現在已推廣為“混合通信／頃序程序”(Hybrid Communicating Sequential
Processes)。在這個語言中，有一種特殊的語句稱為“連續構件”，可表示一個具體給定初值的微分方程；而原有的通信語句可用來表達事件的起源和發生；語言中的順序算子、條件算子等則用來刻畫連續構件和通信間的耦合關系。
值得指出的是，霍爾還和我國軟體學者、中國科學院軟體所的周巢塵研究員等合作，在20世紀80年代末由于Esprit的ProCos項目的需要而對基于時态邏輯的邏輯型混合計算模型進行了研究，在這個模型中引入了時段和切變的概念，建立了時段演算，已引起該領域同行的廣泛重視。時段用以刻畫系統在一個時間區間上的連續變化，而切變則表示事件的發生(離散變量的變化)。在單個時段上，借助連續數學(微分方程理論)推導系統的行為；而在相鄰時段間，則用時态邏輯中切變算子的規則，推導系統行為的轉化。這種混合計算模型對于設計要求絕對安全。
馮·諾依曼1903年12月28日生于匈牙利，1957年2月8日死于美國。我想知道計算機的人一定對他不會陌生，它可以稱為計算機之父了，現在我們面前計算機内采用的體系結構就是以他的命名的馮·諾依曼結構。
馮·諾依曼小時就十分聰明，6歲時就能夠心算8位數字的除法，它在匈牙利接受了他的初等教育，并于18歲發表了第一篇論文！在1925年取得化學文憑後，他把興趣轉向了喜愛已久的數學，并于1928年取得博士學位，它在集合論等方面取得了引人注目的成就。1930年他應邀通路普林斯頓大學，這所大學的高等研究所于1933年建立，他成為最早的6位數學教授之一，直到他去世，它一直是這個研究所的數學教授。後來他為成為美國公民。
1936到1938圖靈（另一位偉大的計算機科學家）是普林斯頓大學數學系的研究所學生，馮·諾依曼邀請圖靈當他的助手，可是圖靈鐘情于劍橋而未能如馮·諾依曼所願，一年後，二次世界大戰使圖靈卷入了戰争，1934年圖靈曾經發表的論文"On
Computable Numbers with an Application to the
Entscheidungs-problem"不可不提，在這篇論文中，圖靈提出了通用機的概念，馮·諾依曼應該知道了這個思想，至少後來他是不是應用了這個思想卻不得而知。
馮·諾依曼迅速發現了這種後來被稱之為計算機的通用機器的用處在于解決一些實際問題，而不是一個擺設，因為戰争的原因馮·諾依曼開始接觸到許多數學的分支，使他開始萌生了使用一台機器進行計算的想法，雖然我們現在都知道第一台計算機ENIAC有他的努力，可是在此之前他碰到的第一台計算機器是Harvard
Mark I
(ASCC)電腦。馮·諾依曼有一種非凡的溝通能力，能夠在不同的科學家之間擔任一個中介者的角色，雖然這些科學家并不想讓别人知道自己的秘密。馮·諾依曼建造的機器名為IAS機，一些由國家實驗室建造的計算機不過是IAS機的複本而已。
戰後馮·諾依曼繼續緻力于IAS機的開發工作，并幫助解決氫彈研制中的計算問題。在他死後，它在計算機界的名聲并不大，以至于他的傳記作家對他在計算機上的貢獻也隻一筆帶過。
取自"http://60.190.84.214:100/wiki/index.php/馮·諾伊曼"
1936年，阿蘭·圖靈提出了一種抽象的計算模型 ── 圖靈機 (Turing Machine)。圖靈的基本思想是用機器來模拟人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：
在紙上寫上或擦除某個符号；
把注意力從紙的一個位置移動到另一個位置；
而在每個階段，人要決定下一步的動作，依賴于 (a) 此人目前所關注的紙上某個位置的符号和(b) 此人目前思維的狀态。為了模拟人的這種運算過程，圖靈構造出一台假想的機器，該機器由以下幾個部分組成：
一條無限長的紙帶。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符号，字母表中有一個特殊的符号 表示空白。紙帶上的格子從左到右依此被編号為 0, 1, 2, ... ，紙帶的右端可以無限伸展。
一個讀寫頭。該讀寫頭可以在紙帶上左右移動，它能讀出目前所指的格子上的符号，并能改變目前格子上的符号。
一個狀态寄存器。它用來儲存圖靈機目前所處的狀态。圖靈機的所有可能狀态的數目是有限的，并且有一個特殊的狀态，稱為停機狀态。
一套控制規則。它根據目前機器所處的狀态以及目前讀寫頭所指的格子上的符号來确定讀寫頭下一步的動作，并改變狀态寄存器的值，令機器進入一個新的狀态。
注意這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，是以這種機器隻是一個理想的裝置。圖靈認為這樣的一台機器就能模拟人類所能進行的任何計算過程
圖靈機停機問題(The Halting Problem)的不可判定性
圖靈機停機問題: 能否給出一個判斷任意一個圖靈機是否停機的一般方法? 答案是NO.
這個問題實際上是問: 是否存在一台"萬能的"圖靈機 H, 把任意一台圖靈機 M 輸入給 H, 它都能判定 M 最終是否停機, 輸出一個明确的 "yes" 或 "no" 的答案? 可以利用反證法來證明這樣的 H 不可能存在. 假定存在一個能夠判定任意一台圖靈機是否停機的萬能圖靈機 H(M), 如果 M 最終停機, H 輸出 "halt"; 如果 M 不停機, H 輸出 "loop". 我們把 H 當作子程式, 構造如下程式 P:
function P(M) {
if (H(M)=="loop") return "halt";
else if (H(M)=="halt") while(true); // loop forever
}
因為 P 本身也是一台圖靈機, 可以表示為一個字元串, 是以我們可以把 P 輸入給它自己, 然後問 P(P) 是否停機. 按照程式 P 的流程, 如果 P 不停機無限循環, 那麼它就停機, 輸出"halt"; 如果 P 停機, 那麼它就無限循環, 不停機; 這樣無論如何我們都将得到一個沖突, 是以假設前提不成立, 即不存在這樣的 H. 或者說, 圖靈機停機問題是不可判定的(undecidable)。 圖靈
世界上第一台電子計算機ENIAC,1946年2月誕生于美國賓夕法尼亞大學莫爾學院。但學術界公認，電子計算機的理論和模型是由英國數學家圖靈在此前10年即1936年發表的一篇論文“論可計算數及其在判定問題中的應用”(On
Computable Numbers With an Application to the Entscheidungs
Problem)中奠定了基礎的。是以，當美國計算機協會ACM在1966年紀念電子計算機誕生20周年，也就是圖靈的有曆史意義的論文發表30周年的時候，決定設立計算機界的第一個獎項(在此之前，作出傑出貢獻的計算機科學家隻能獲得數學方面或電氣工程方面的獎項)，并且很自然地把它命名為“圖靈獎”以紀念這位計算機科學理論的創始者。被稱為“計算機界的諾貝爾獎”的這個獎設立至今，已經頒發了34屆，共有40名計算機科學家獲此殊榮。
阿倫·圖靈(Alan
Mathison
Turing)1912年6月23日生于倫敦近郊的自治鎮帕丁頓(Paddington，現歸屬倫敦Westminster區，英國議會大廈和世界聞名的威斯敏斯特大教堂就在這裡)。圖靈的父親是英國在印度的行政機構的一名官員，母親平常也在印度陪伴其丈夫。1926年圖靈的父親退休以後，因為終身俸不高，為了節省，他們夫婦又選擇在生活費用較低的法國居住，沒有回英國定居，是以圖靈和他的一個叫約翰的哥哥很少見到父母親，他們是由從軍隊中退休的沃德(Ward)夫婦帶大的。童年時缺乏父愛和母愛，也許正是圖靈自幼起性格和行為就比較怪僻，并最終釀成悲劇結局的一個重要原因。圖靈13歲進入寄宿的謝博恩中學(SherboumeSch001)，學習成績并不特别好，隻有數學例外，演算能力特别強。此外，就是擅長賽跑，我們現在還能看到圖靈在運動會上參加賽跑中沖過終點時留下的照片。
1931年中學畢業以後，圖靈想進劍橋大學最負盛名的“三聖學院”(Trinity
College)，但兩次未被錄取，隻好進了劍橋的另外一所學院——“國王學院”(King’s
College)攻讀數學。第一年的課比較淺，圖靈很厭煩，沒有好好學，結果在劍橋大學特設的一種叫Tripos的榮譽學位考試中隻得了“二等”。好在他急起直追，最後畢業時的數學學位考試還是拿了第一等，取得這個成績的學生在劍橋大學有一個特别的榮譽稱号，叫Wrangler。圖靈的學位論文課題是關于機率論的中心極限定理(the
Central Limit Theorem of
Probability)的。實際上，由于他在研究這個課題時對前人在這方面所做的工作一無所知，可以說是圖靈自己又重新發現了這個定理。1936年圖靈因就同一課題所發表的論文而獲得史密斯獎(Smith
Prize)。
1935年，圖靈開始對數理邏輯發生興趣。數理邏輯(mathematical logic)又叫形式邏輯(formal 10gic)或符号邏輯(symbolic
logic)，是邏輯學的一個重要分支。數理邏輯用數學方法，也就是用符号和公式、公理的方法去研究人的思維過程、思維規律，其起源可追溯到17世紀德國的大數學家萊布尼茨(Gottfried
Wilhelm
Leibniz，1646—1716)，其目的是建立一種精确的、普遍的符号語言，并尋求一種推理演算，以便用演算去解決人如何推理的問題。在萊布尼茨的思想中，數理邏輯、數學和計算機三者均出于一個統一的目的，即人的思維過程的演算化、計算機化，以至在計算機上實作。但萊布尼茨的這些思想和概念還比較模糊，不太清晰和明朗。兩個多世紀來，許多數學家和邏輯學家沿着萊布尼茨的思路進行了大量實質性的工作，使數理邏輯逐漸完善和發展起來，許多概念開始明朗起來。但是，“計算機”到底是怎樣一種機器，應該由哪些部分組成，如何進行計算和工作，在圖靈之前沒有任何人清楚地說明過。正是圖靈上述1936年那篇标題有些古怪(其中“判定問題”用的是“外文”——德文!)的論文第一次回答了這些問題，提出了一種計算機的抽象模型，利用這種計算機，可以把推理化作一些簡單的機械動作。圖靈提出的計算模型現在被大家稱作“圖靈機”(Turing
Machine)。
說來有趣，具有重大科學價值和曆史意義的計算模型，并非圖靈那篇論文的主題。圖靈那篇論文主要是回答同樣是德國大數學家的戴維·希爾伯特(David
I-Hilbert，1862—1943)在1900年舉行的世界數學家大會上提出的著名的“23個數學難題”中的一個問題的，這個問題涉及邏輯的完備性，即是否所有的數學問題在原則上都是可解的。圖靈的論文回答了這個問題：有些數學問題是不可解的。而自動計算機的理論模型則是圖靈在其論文的一個腳注中“順便”提出來的。這可正謂“歪打正着”——圖靈這篇傳世的論文主要是因為這個腳注，其正文的意義和重要性反而退居其次了。值得回味的是，在科學技術的發展史上，這樣的事例并不鮮見。
圖靈的論文發表以後，立刻引起了大洋彼岸的美國科學家的重視。年輕的英國數學家的深刻見解和重大創新令他的美國同行十分驚歎，普林斯頓大學立即向圖靈發出邀請，于是圖靈首次遠涉重洋，到美國和邱奇合作，并于1938年在普林斯頓大學取得博士學位。他的博士論文課題是“基于序數的邏輯系統”(Systems
of logic Based ordinals)。在這裡，圖靈還研究了由喬治·布爾(George
Boole，1815—1864)于1854年建立的邏輯代數，自己動手用繼電器搭邏輯門組成了乘法器。這方面的知識和經驗為他後來破譯德國人的密碼打了一個很好的基礎。在美國，圖靈還遇到了計算機科學理論的另一位重要創始者、出生在匈牙利的天才科學家馮·諾伊曼(John
yon
Neumann，1903—1957)。馮·諾伊曼因研究博奕論并把博奕論用于商業及軍事方面而出名，1930年移居美國後也在普林斯頓大學任教。馮·諾伊曼對圖靈十分欣賞并邀請他到他那裡工作，但圖靈沒有接受這個邀請，1938年回到英國劍橋大學。在戰争爆發以前，圖靈從事的研究工作是Z函數的計算方法(method
for the calculation of the ZetaFunction)。
第二次世界大戰爆發後，因圖靈正值服役年齡，隻能像其他科學家一樣，為戰争服務。1939年秋季開始，圖靈就進入英國外交部設在布萊奇利(Bletchley，在倫敦東北約80km處)的科學研究機構中工作。由于高度機密，英國的保密制度又特别嚴格，圖靈在戰時工作的細節至今不得而知。從一些零星透露出來的資料看，圖靈這個時期所做的主要工作是破譯德軍的密碼。他用繼電器做成被叫做“霹靂彈”(Bombe，因為繼電器工作時發出“霹靂啪啦”的聲音而得名)的譯碼機破譯了德軍的不少“恩尼格瑪”(Enigma，這是德國使用的密碼機的名稱)密報，發現了德軍的動向，特别是德軍在大西洋上的潛艇的動向，為盟軍戰勝德國法西斯立了不少功勞。是以戰後圖靈被光榮授勳，被稱為OBE(Officer
Order of the British
Empire，這是對非戰鬥人員的極高榮譽)。“霹靂彈”後來改用電子管，命名為“巨人”(Colossus)，内含1800多個電子管，被認為是第一台投入運作的數字電子計算機。但英國政府直到20世紀90年代初才解密“巨人”的資料。有人說第一台“巨人”就是由圖靈監制的。
關于圖靈在戰時的表現，流傳着不少故事。除了不修邊幅、講話木讷、孤僻等以外，最不可思議和令人難以置信的是，圖靈由于對英國在戰争中獲勝沒有信心，把所有的積蓄換成兩塊銀條埋了起來，但後來卻記不起埋在哪兒了。
戰争期間，圖靈曾在1942年因公務再次通路美國，會見了普林斯頓的老朋友，了解了美國在計算機研制方面的最新進展。戰後，他沒有接受他的母校國王學院的聘請，而去了英國國家實體實驗室NPL(National
Physical Laboratory)建立立的“數學部”(Mathematics
Division)，開始了設計與建造電子計算機的宏大工程。他把自己在計算模型方面的理論研究成果和戰時在脈沖技術和電子學方面的實踐經驗結合起來，提出了一個設計方案，這個方案經英國皇家學會的一些院士組成的“評估委員會”(review
committee)讨論通過，同意實行，并授權圖靈自行招聘一些适當的從業人員。但在1946年5月以前，圖靈一直未能找到稱心的助手，是以長期“單槍匹馬”。後來終于來了詹姆斯·威爾金森(James
Hardy
Wilkinson，1919—1986，他是1970年圖靈獎獲得者)。威爾金森也是劍橋大學的畢業生，戰時在劍橋數學實驗室的軍械研究所工作，解決有關彈道方面的問題，精通計算數學。經過一次長談，雙方一拍即合，威爾金森成了圖靈得力的助手。他們研制的計算機被起名為ACE(Automatic
Computing Engine)，這個名稱是NPL數學部主任沃沫史萊(J．R．Womersley)起的，用以紀念查爾斯·巴貝奇(Charles
Babbage，1792—1871)的Analytical
Engine。威爾金森到來時，圖靈設計的ACE已到了第五版。但圖靈是一個不善于也不重視保管文檔資料的人，前四版的設計早已不知丢到哪裡去了。根據圖靈的設計，ACE是一台串行定點計算機，字長32bit，主頻1MHz，用水銀延遲線作存儲器，是一種存儲程式式計算機。關于“存儲程式”(stored
program)的概念，是現代電子計算機的最基本概念之一，也是現代電子計算機的最基本特征之一。ENIAC雖然是世界上第一台電子計算機，但不是存儲程式式的，程式要通過外接電路闆輸入。馮·諾伊曼在ENIAC研制過程中就發現了這個問題，并提出了解決方案。
1945年6月30日，馮·諾伊曼發表了題為“關于離散變量自動電子計算機的草案”的長文，正式提出了存儲程式的概念，是以存儲程式式計算機被稱為“馮·諾伊曼結構”，而他所建議的“離散變量自動電子計算機”也就是後來由賓夕法尼亞大學莫爾學院建成的EDVAC計算機(Electronic
Discrete Variable Automatic
Computer)。但圖靈在設計ACE時的存儲程式思想并非受馮·諾伊曼論文的影響，而是他自己的構思。馮·諾伊曼本人也從來沒有說過存儲程式的概念是他的發明，卻不止一次地說過圖靈是現代計算機設計思想的創始人。圖靈在設計ACE時很重視機器速度問題，采取了一系列方法使機器在一定主頻下能有較快的指令執行周期，比如後來被稱為“最佳編碼”(optimum
coding)或“等待時間最少的編碼”(minimum latency
coding)的技術，就是ACE首創的。ACE的其他創造包括實作浮點運算的一組子程式(這是圖靈交給威爾金森的第一個任務)及雙倍字長指令等。
但是ACE計劃的實作卻遇到了很大困難。當時采取的是“設計”和“工程實施”分離的辦法，設計由NPL負責，工程卻由另一個政府部門即供應部(Ministry of
Supply)負責，那裡有一些搞過雷達、進而對脈沖技術比較熟悉的工程技術人員。雙方的難以磨合導緻計劃進度遲緩，使圖靈心情極壞，而NPL的主任查爾斯·達爾文爵土(Sir
Charles
Darwin，提出“進化論”的著名生物學家達爾文的曾孫)是個不太聽得進意見的人，眼看問題成堆仍一意孤行，直到1947年才勉強同意在NPL中成立一個電子學小組(Electronics
Group)實施ACE計劃，領頭的是托馬斯博士(Dr．Thomas)。不幸的是，圖靈和托馬斯兩人又互不相容，導緻圖靈于1948年離開NPL。圖靈離開NPL以後，威爾金森接手負責這個項目，采取了一些措施，此外環境條件也有所改善，ACE的樣機即Pilot
ACE得以在1950年5月完成。Pilot ACE不是根據圖靈在離開NPL時留下的第八版完成的，而是根據早先的第五版設計實作的。Pilot
ACE後來由英國電氣公司EEC(English Electric Company)生産了約30台，其商品名為DEUCE.Pilot
ACE(DEUCE)和劍橋大學的莫裡斯·威爾克斯(Maurice Vincent
Wilkes，1967年圖靈獎獲得者)研制的EDSAC(LEO)計算機使英國的計算機技術水準和産業化程度在20世紀50年代處于世界領先水準，可以和美國平起平坐，其中圖靈的功勞是不可抹殺的，雖然他沒有親自把ACE的開發負責到底。
離開NPL以後，圖靈到曼徹斯特大學新成立的皇家學會計算實驗室(Royal
Society Computing
Laboratory)當副主任。曼徹斯特大學在計算機發展史上曾經起過重大的作用，以威廉斯管的發明人F．C．Williams(1911—1977)和湯姆·基爾蓬(Tom
Kilburn)為首的研究小組曾在1948年6月開發出了被稱為世界上第一台存儲程式式計算機的MARK I，其原型則被稱為“嬰兒機”(Baby
Machine)。注意，20世紀40年代曾經出現過兩個被稱為MARK I的計算機，一個是這裡所說的MARK I，另一個是美國哈佛大學的霍沃德·艾肯(Howard
Aiken，1900---1973)在IBM的支援下于1944年開發成功的機電式MARK
I，這也正是IBM走上計算機産業之路的開始。為了差別，常常把前者稱為“曼徹斯特MARK I”，而把後者稱為"IBM MARK I”。曼徹斯特MARK
I後來由Ferranti公司商品化，其第一台于1951年2月安裝于曼徹斯特大學，有資料把它說成是世界上第一個商品化計算機型号。圖靈加盟曼徹斯特大學不但為它提供了強大的理論支援，也為它做了許多實際工作，據資料記載，圖靈在這裡曾和其他人合作，設計了紙帶輸入／輸出系統，還編寫了程式設計手冊。是以，有些圖靈傳記中說圖靈到曼徹斯特大學以後并未參與計算機的實際開發工作，是不太确切的。在這段時間裡圖靈為計算機科學所作出的又一個傑出貢獻是他在1950年10月發表的論文“計算機和智能”(Computing
Machinery and
Intelligence)。在這篇經典的論文中，圖靈進一步闡明了他認為計算機可以有智能的思想，并提出了測試機器是否有智能的方法，他稱之為“模仿遊戲”(lmitation
Game)，而大家現在稱之為“圖靈測試”(Turing
Test)。在這個測試中，讓一個提問者通過電傳打字機(現在可以通過計算機鍵盤)在遠處同人或計算機相聯系，提出各種各樣問題。提問者根據對方的回答确定對方是人還是計算機。如果在提出足夠多的問題後提問者仍無法确定對方是人還是計算機，那末就可以認為機器具有人的智能。對自己的論點的正确性，圖靈固然有十分的把握，但對它的實作的前景，圖靈隻是作了非常審慎的估計。圖靈預言，在50年以内，計算機可以被編出程式來有效地玩這個遊戲，給提問者5min的提問時間，讓他作出恰當的判斷的機會不多于70％。今年正好是圖靈預言以後的50年。對圖靈預言是否已經實作，學術界有不同的看法。有人認為圖靈預言早就已經實作，因為随着計算機技術的迅猛發展和人工智能技術的進展，計算機早已有了相當程度的智能，其明顯标志是計算機會下棋，而且愈來愈精，近年來甚至把卡斯帕羅夫這樣的國際特級大師都打敗了。另外一種意見則認為圖靈預言尚未實作，計算機要通過圖靈測試還有待時日。有人估計要30年以後才能出現真正具有人那樣智能的計算機。不管專家們意見如何相左，圖靈在這個問題上的高瞻遠矚同樣是他的偉大天才的一個印證，這是沒有疑問的。
在曼徹斯特大學期間，圖靈發表的論文中還包括對黎曼(BernardRiemann，1826—1866)Z函數的進一步研究成果，這是他戰前曾經感興趣而研究過的一個課題。這個時期，他對生物學和化學也産生了興趣，曾經發表有關器官形成的化學基礎的論文，探讨海星為什麼呈五軸對稱，原腸胚在特定的點上形成溝槽等現象。
由于圖靈的一系列傑出貢獻和重大創造，1951年他被選為英國皇家學會院士。但這之後，他就因私生活方面的問題而陷入困境。圖靈是一位同志者。在曼徹斯特，他和一位19歲的所謂“街頭青年”默裡(Amold
Murray)有染。默裡把他的一個同夥帶到圖靈住處，這個同夥本是慣偷，臨走時順手牽羊拿走了圖靈一些不太值錢的東西。圖靈不知就裡，報了案，警察偵破後在審訊中得知了圖靈和默裡的關系。20世紀50年代，社會對同志不像現在這樣比較寬容，而被認為嚴重傷風敗俗。1952年圖靈被法院傳訊，指控行為“極端不當”(grossindecency)。但由于他戰後受過勳，社會地位比較高，而且是一個名人，是以沒有判他人獄，而是給予一年監外察看，并給予藥物治療，注射雌性荷爾蒙。兩年以後，1954年6月7日，離開他的42周歲生日不到兩個星期，圖靈因吃了在氰化物溶液中浸泡過的蘋果而在家中死去。圖靈的母親曾力圖使官方宣布圖靈為意外死亡，但未被理睬；外界一直說圖靈是服毒自殺。但圖靈的同僚始終認為圖靈的死是一個不解的謎，因為對圖靈的荷爾蒙治療早已在一年前結束，這雖然為圖靈留下了污點，但圖靈畢竟已度過了這場變故，而且他的事業并未受到影響。他既沒有留下任何字條，也沒有任何線索暗示他要走這一步。不管如何衆說紛纭，劃時代的科學奇才圖靈就這樣在他壯年時期無聲無息地離開了這個世界，一顆光芒四射的巨星從此隕落，為世人留下了無限的惋惜。
圖靈去世後12年開始設立的圖靈獎是美國計算機協會ACM(Association for Computing
Machinery)設立的第一個獎項。ACM成立于1947年，也就是世界上第一台電子計算機ENIAC誕生以後的第二年，美國一些有遠見的科學家意識到它對于社會進步和人類文明的巨大意義，是以發起成立了這個協會，以推動計算機科學技術的發展和學術交流。
ACM于1947年9月15日在紐約的哥倫比亞大學成立之初的名稱是“東部計算機協會”(Eastern
Association for Computing
Machinery)，後來才把Eastern這個詞去掉而成為ACM。它的章程和附則是兩年後才通過的。章程規定協會的目的有三：
1．推進資訊處理科學和技術，包括計算機、計算技術和程式設計語言的研究、設計、開發和應用，也包括過程的自動控制和模拟。
2．促進資訊處理科學和技術在專業人員和大衆中的自由交流。
3．維護資訊處理科學和技術從業人員的權益。
ACM建立以來，積極地開展了活動，目前已成為計算機界最有影響的兩大國際性學術組織之一(另一為IEEE的計算機協會，即IEEE Computer
Society)。一些知名的計算機科學家，包括圖靈獎獲得者佩利、哈明和ENIAC的主要設計者之一莫奇利等都擔任過ACM的主席。它下面又建立了幾十個專業委員會(正式名稱是所謂SIG---Special
Interest
Group)，幾乎每個SIG都有自己的雜志。據筆者不完全統計，由ACM出版社出版的定期、不定期刊物有40多種，覆寫了計算機科學技術的幾乎所有領域。
圖靈獎是ACM于1966年第一個設立的獎項，專門獎勵那些在計算機科學研究中做出創造性貢獻、推動了計算機科學技術發展的傑出科學家。雖然沒有明确規定，但從實際執行過程來看，圖靈獎偏重于在計算機科學理論和軟體方面作出貢獻的科學家。獎金金額不算太高，設獎初期為2萬美元，1989年起增至2萬5千美元，獎金通常由計算機界的一些大企業提供(通過與ACM簽訂協定)。由于圖靈獎對獲獎條件要求極高，評獎程式又極嚴，一般每年隻獎勵一名計算機科學家，隻有極少數年度有兩名合作者或在同一方向作出貢獻的科學家共享此獎。是以它是計算機界最負盛名、最崇高的一個獎項，有“計算機界的諾貝爾獎”之稱。從1966年到1999年的34屆圖靈獎，共計有40名科學家獲此殊榮，其中美國學者最多，此外還有英國、瑞土、荷蘭、以色列等國少數學者。值得指出的是，迄今為止的圖靈獎獲得者名單中，不要說沒有一個中國人(包括美籍華裔學者)，連法國、德國、日本這樣一些發達國家的學者也一個都沒有，這是令人遺憾的。當然，如同任何獎都不可能絕對客觀、公正、公平一樣，圖靈獎出現的這種不平衡是可以了解的，因為這個組織畢竟發源于美國，總部也設在美國，受美國人控制；就計算機科學技術而言，确實也是美國的水準最高，貢獻最突出。我們隻能這樣評論：每個圖靈獎獲得者确實都是出類拔萃的；但出類拔萃的計算機科學家還有很多由于種種原因而沒有獲得圖靈獎。我們相信，隻要中國的計算機學者不斷努力，勇于創新，随着中國改革開放的逐漸深入和對外學術交流的加強，總有一天，會有中國學者昂首走上圖靈獎的領獎台。
圖靈”趣話
小晏
對于每一個行業和領域來說，幾乎都存在一兩項令其領域内所有人視為“終極榮譽”的大獎，例如電影業的奧斯卡獎、新聞領域的普利策獎，數學領域的沃爾夫獎和費爾茲獎等等。随着計算機通訊業的迅猛發展，“圖靈”這個詞頻頻出現在各個場合，尤其是去年比爾.蓋茨攜微軟高層人員來華一行，期間多次提到“圖靈獎”一詞，而且大家對獲得該獎項的人士更是恭敬有加，好奇之餘，我便查閱資料，不想卻發現了許多趣事，于是寫來與大家分享。
“圖靈（Turing）獎”是美國計算機協會（ACM，Association
for Computer Machinery）幹
1966年設立的，專門獎勵那些對計算機科學研究與推動計算機技術發展有卓越貢獻的傑出科學家。設立的初衷是因為計算機技術的飛速發展，尤其到20世紀60年代，其已成為一個獨立的有影響的學科，資訊産業亦逐漸形成，但在這一産業中卻一直沒有一項類似“諾貝爾”、“普利策”等的獎項來促進該學科的進一步發展，為了彌補這一缺陷，于是“圖靈”獎便應運而生，它被公認為計算機界的“諾貝爾”獎。
“圖 靈”為 何
如此 幸 運
不少人夢寐以求的國際計算機的最高獎項——圖靈獎，為何它如此幸運，真是說來話長。
阿蘭·圖靈（Alan
Turing），1912年6月23日出生于英國倫敦，他被認為成二十世紀最著名的數學家之一，誰也沒有想到他的名字會和計算機産業挂鈎。
20世紀的數學界正在熱烈的讨論本世紀最偉大的科學發現之一
——昆特.哥德爾的不完全性定理，在那以前，數學家們總認為，一個數學問題雖然要找到答案也許會很困難，但理論上總有一個确定的答案，一個數學命題，要麼是真的，要麼是假的。而哥德爾的不完全定理指出：在一個稍微複雜一點的的數學公理系統中，總存在那樣的命題，我們既不能證明它是真的，也不能證明它是假的。數學家們大吃一驚，發現以往大家認為絕對嚴密的數學中，原來有令人如此不安的不确定性。每個邏輯學家都在苦苦思索，試圖為陷入了危機的數學找到一條出路，這些邏輯學家包括當時在劍橋的貝特朗.羅素(
Bertrand Russell ) 、阿爾弗雷德.懷特海（Alfred Whitehead）、路德維格.維特斯根坦 ( Ludwig
Wittgenstein)
等著名的邏輯學家。這時的圖靈正在劍橋求學，他也同樣為此問題陷入了困境。
1936年，圖靈作出了他一生最重要的科學貢獻，他在其著名的論文《論可計算數在判定問題中的應用（On
Computer numbers with an Application to the Entscheidungs
-problem）》一文中，以布爾代數[i]為基礎，将邏輯中的任意命題（即可用數學符号）用一種通用的機器來表示和完成，并能按照一定的規則推導出結論。這篇論文被譽為現代計算機原理開山之作,它描述了一種假想的可實作通用計算的機器，後人稱之為“圖靈機”。
這種假想的機器由一個控制器和一個兩端無限長的工作帶組成。工作帶被劃分成一個個大小相同的方格，方格内記載着給定字母表上的符号。控制器帶有讀寫頭并且能在工作帶上按要求左右移動。随着控制器的移動，其上的讀寫頭可讀出方格上的符号，也能改寫方格上的符号。這種機器能進行多種運算并可用于證明一些著名的定理。這是最早給出的通用計算機的模型。圖靈還從理論上證明了這種假想機的可能性。盡管圖靈機當時還隻是一紙空文，但其思想奠定了整個現代計算機發展的理論基礎。
1945年，圖靈被調往英國國家實體研究所工作。他結合自己多年的理論研究和戰時制造密碼破譯機的經驗，起草了一份關于研制自動計算機器（ACE：Automatic
Computer Engine
）的報告，以期實作他曾提出的通用計算機的設計思想。通過長期研究和深入思考，圖靈預言，總有一天計算機可通過程式設計獲得能與人類競争的智能。1950年10月，圖靈發表了題為《機器能思考嗎？》的論文，在計算機科學界引起巨大震撼，為人工智能學的創立奠定了基礎。同年，圖靈花費4萬英鎊，用了約800個電子管的ACE樣機研制成功，它的存儲容量比愛尼亞克[ii]大了許多。在公開示範會上，被認為是當時世界上速度最快、功能最強的計算機之一。圖靈還設計了著名的“模仿遊戲試驗”，後人稱之為“圖靈測試”。該實驗把被提問的一個人和一台計算機分别隔離在兩間屋子，讓提問者用人和計算機都能接受的方式來進行問答測試。如果提問者分不清回答者是人還是機器，那就證明計算機已具備人的智能（1993年美國波士頓計算機博物館舉行的著名的“圖靈測試”
[iii]充分驗證了圖靈的預言）。
這讓我想起前幾年IBM公司研制的計算機“深藍”與國際象棋世界冠軍卡斯帕羅夫進行的那場人機大戰，最終以“深藍”戰勝卡斯帕羅夫而宣告結束，讓我們不得不佩服圖靈的天才預言。
現代計算機之父馮·諾依曼[iv]生前曾多次謙虛地說：如果不考慮巴貝奇[v]等人早先提出的有關思想，現代計算機的概念當屬于阿蘭·圖靈。馮·諾依曼能把“計算機之父”的桂冠戴在比自己小10歲的圖靈頭上，足見圖靈對計算機科學影響之巨大。
毒 液 浸 透 蘋 果，如 睡 之 死 滲 入 ……
身為一名數學家,
圖靈模型研制計算機的夢想在第二次世界大戰的爆發中粉碎。當時，德國法西斯正對英倫三島狂轟濫炸，圖靈的祖國危在旦夕,懷着一腔報國熱情，圖靈前往英國外交部承擔“超級機密”研究工作，即主持對德軍通訊密碼的破譯工作。圖靈便和曆史上著名的布萊奇利公園以及加密電子機械裝置ENIGMA聯系在了一起。
ENIGMA是德國發明家亞瑟.謝爾比烏斯（Arthur
Scherbius）發明的一種加密電子器,它被證明是有史以來最可靠的加密系統之一，二戰期間它開始被德軍大量用于鐵路、企業當中。英國第40局（英國政府負責破譯密碼的間諜機構）開始恐慌，因為出現了大量他們無法破譯的電文。在整整13年裡，英國人和法國人都認為ENIGMA是不可破譯的。針對這一情況，40局新設了它的機構——英國政府代碼及加密學校（GC&CS
,Government Code and Cipher
School），總部坐落在白金漢郡的布萊奇利公園。在布萊奇利公園有一大批為破譯ENIGMA作出卓越貢獻的人們，圖靈無疑是他們當中最值得叙述的一個。圖靈發明了綽号為“炸彈”
（Bombes）的解密機器，他被看成一位天才解密分析專家。戰争結束，布萊奇利公園被關閉，“炸彈”被拆毀，所有戰時有關密碼分析和破譯的檔案資料都被銷毀，直到1967年波蘭出版第一本關于波蘭破譯ENIGMA方面的書，以及1974年溫特伯坦姆寫的《超級機密The
Ultra
Secret》一書出版，人們才知道圖靈在分析解密方面的貢獻。
1938年迪斯尼公司著名的卡通片《白雪公主和七個小矮人》上映，圖靈也觀看了這部影片，在後來的日子裡，他的同僚常常聽見他哼電影中巫婆王後泡制毒蘋果的台詞：“毒液浸透蘋果如睡之死滲入……”而圖靈的一生正是在這首歌詞中結束。
圖靈在他生命的最後時光，沒有機會看到自己被當作一個解密英雄來尊敬，相反，由于他同志的性傾向而倍受折磨。1952年因小偷入室行竊，圖靈向警察報了案，但他卻忘了向警察掩藏他和另一位男士同居的事實，同年他被警方逮捕，以“有傷風化罪”罪名遭到起訴，并被判為有罪。而這期間，他不得不忍受報紙媒體對他案件的公開全面報道。性傾向被公開，私生活曝光于大衆，政府也取消了他情報部門的工作。他的脾氣變的躁怒不安，性格陰沉郁悒。1954年6月8日，人們在圖靈的寓所發現了他的屍體。他在自己的住處服用沾過氰化物的蘋果而自殺。臨死的前夜，也許圖靈的耳邊還回響着那首歌：“毒液浸透蘋果如睡之死滲入……”
迄今為止，作為計算機界“諾貝爾獎”的圖靈獎已走過了36個春秋。40多位圖靈獎得主均對計算機科學與技術的發展創新做出了傑出貢獻。他們在珍惜自己所獲崇高榮譽的同時，也深切懷念阿蘭·圖靈這位在計算機創新史上永放光芒的先驅。
--------------------------------------------------------------------------------
[i]
1854年，英國數學家喬治·布爾（George
Boode）出版了名著《布爾代數》。書中用“真”、“假”兩種邏輯值和“與”、“或”、“非”三種邏輯運算把形式邏輯歸結為一種代數。
[ii]
“愛尼亞克”是世界第一台實用數字電子計算機，1946年2月15日在賓西法尼亞大學正式投入運作。
[iii]該次測試評判員與封閉在密室的計算機或人進行15分鐘的交談，然後根據交談的印象判斷交談對方是人還是計算機。其中“PC理療3号”
讓評判員誤認為“他”是一名聊天高手，而另有兩位評判員誤将一位小姐指認為計算機。是以充分證明了圖靈預言的正确性。
[iv] 約翰·馮·諾依曼 （ John
Von
Nouma，1903－1957），美藉匈牙利人。提出了著名的"馮·諾依曼機"設想，其中心就是有存儲程式原則——指令和資料一起存儲．這個概念被譽為\'計算機發展史上的一個裡程碑"，它标志着電子計算機時代的真正開始，指導着以後的計算機設計。
[v] 查爾斯·巴貝奇, 英國人。
他寫出了世界上第一部關于計算機程式的專著，他發明的解析機是現代電子計算機的雛形。
