|
圖靈 孫宏安 (江寧師范大學) 圖靈，A．M．(Turing，Alan Mathison)1912年6月23日生于英國倫敦；1954年6月7日卒于英國威姆斯洛(Wilmslow)．數(shù)學、數(shù)理邏輯、計算機科學． 圖靈的父親J．M．圖靈早年就讀于牛津大學科帕斯克斯蒂學院歷史系，后來從政，被派往印度，擔任民政部的官員．圖靈的母親E．S．斯托尼(Stoney)生于一個鐵路工程師家庭，曾就讀于巴黎大學文理學院．圖靈是他們的次子． 圖靈的父親在印度工作，母親也常去印度，孩子們經(jīng)常住在一位朋友家中．圖靈少年時就表現(xiàn)出獨特的直覺創(chuàng)造能力和對數(shù)學的愛好．1926年，他考入倫敦有名的舍本(Sherborne)公學，受到良好的中等教育．他在中學期間表現(xiàn)出對自然科學的極大興趣和敏銳的數(shù)學頭腦．1927年末，年僅15歲的圖靈為了幫助母親理解A．愛因斯坦(Einstein)的相對論，寫了愛因斯坦的一部著作的內(nèi)容提要，表現(xiàn)出他已具備非同凡響的數(shù)學水平和科學理解力．他對自然科學的興趣使他在1930年和1931年兩次獲得他的一位同學C．莫科姆(Morcom)的父母設立的自然科學獎，獲獎工作中有一篇論文題為“亞硫酸鹽和鹵化物在酸性溶液中的反應”(The reaction of sulphurous salt upon halogenide in acidsolution)，受到政府派來的督學的贊賞．對自然科學的興趣為他后來的一些研究奠定了基礎．他的數(shù)學能力使他在念中學時獲得過國王愛德華六世數(shù)學金盾獎章． 1931年，圖靈考入劍橋大學國王學院，由于成績優(yōu)異而獲得數(shù)學獎學金．在劍橋，他的數(shù)學能力得到充分的發(fā)展．1935年，他的第一篇數(shù)學論文“左右殆周期性的等價”(Equivalence on leftand right almost Priodicity)發(fā)表于《倫敦數(shù)學會雜志》(J．Loud．Math．Soc．)上．同一年，他還寫出“論高斯誤差函數(shù)”(On theGaussian error unction)一文．這一論文使他由一名大學生直接當選為國王學院的研究員，并于次年榮獲英國著名的史密斯(Smith)數(shù)學獎，成為國王學院聲名顯赫的畢業(yè)生之一． 1936年5月，圖靈寫出了表述他的最重要的數(shù)學成果的論文“論可計算數(shù)及其在判定問題中的應用”(On computable numbers，with an application to the Entscheidungsproblem)，該文于1937年在《倫敦數(shù)學會文集》(Proc．Loud．Math．Soc．)第42期上發(fā)表后，立即引起廣泛的注意．文中，他分析了計算的過程，給出了理論上可計算任何“可計算序列”——某種0和1的序列——的“通用”計算機概念，并利用這一概念解決了D．希爾伯特(Hil-lbert)提出的一個著名的判定問題．1937年，圖靈發(fā)表的另一篇文章“可計算性與λ可定義性”(Computability andλ-definability)則拓廣了A．丘奇(Church)提出的“丘奇論點”，形成“丘奇-圖靈論點”，對計算理論的嚴格化，對計算機科學的形成和發(fā)展都具有奠基性的意義． 1936年9月，圖靈應邀到美國普林斯頓高級研究院學習，并與丘奇一同工作．在美國期間，他對群論作了一些研究，并撰寫了博士論文，1938年在普林斯頓獲博士學位，其論文題目為“以序數(shù)為基礎的邏輯系統(tǒng)”(Systems of logic based on ordinals)， 1939年正式發(fā)表，在數(shù)理邏輯研究中產(chǎn)生了深遠的影響． 1938年夏，圖靈回到英國，仍在劍橋大學國王學院任研究員，繼續(xù)研究數(shù)理邏輯和計算理論，同時開始了計算機的研制工作．第二次世界大戰(zhàn)打斷了他的正常研究工作，1939年秋，他應召到英國外交部通信處從事軍事工作，主要是破譯敵方密碼的工作．由于破譯工作的需要，他參與了世界上最早的電子計算機的研制工作．他的工作取得了極好的成就，因而于1945年獲政府的最高獎——大英帝國榮譽勛章(O．B．E．勛章)．人們認為，通用計算機的概念就是圖靈提出來的． 1945年，圖靈結束了在外交部的工作，他試圖恢復戰(zhàn)前在理論計算機科學方面的研究，并結合戰(zhàn)時的工作，具體研制出新的計算機來．這一想法得到當局的支持．同年，圖靈被錄用為泰丁頓(Teddington)國家物理研究所的研究人員，開始從事“自動計算機”(ACE)的邏輯設計和具體研制工作．這一年，圖靈寫出一份長達50頁的關于ACE的設計說明書(Proposals for developmentin the mathematlcs divison of an ACE)．這一說明書在保密了27年之后，于1972年正式發(fā)表．在圖靈的設計思想指導下，1950年制出了ACE樣機，1958年制成大型ACE機． 1948年，圖靈接受了曼徹斯特大學的高級講師職務，并被指定為曼徹斯特自動數(shù)字計算機(Madam)項目的負責人助理，具體領導該項目數(shù)學方面的工作．作為這一工作的總結，1950年圖靈編寫并出版了《曼徹斯特電子計算機程序員手冊》(The programmers’handbook for the Manchester electronic computer)．這期間，他繼續(xù)進行數(shù)理邏輯方面的理論研究． 早在1947年，圖靈就提出過自動程序設計的思想，1950年，他提出關于機器思維的問題，他的論文“計算機和智能(Computingmachiery and intelligence)，引起了廣泛的注意和深遠的影響．1956年，在收入一部文集時此文改名為“機器能夠思維嗎？”(Cana machine think？)，至今仍是研究人工智能的首選讀物之一． 1951年，圖靈當選為英國皇家學會會員．1952年，他辭去劍橋大學國王學院研究員的職務，專心在曼徹斯特大學工作．除了日常工作和研究工作之外，他還指導一些博士研究生，還擔任了制造曼徹斯特自動數(shù)字計算機的一家公司——弗蘭蒂公司(Ferran-ti’S)——的顧問． 圖靈少年時就形成的對自然科學的興趣一直使他樂于思考自然科學問題．40年代末他表現(xiàn)出對生物學的濃厚興趣，1951年，他寫成長篇專論“形態(tài)形成的化學基礎”(The chemical basis of morPhogenesis)于次年發(fā)表，他利用數(shù)學工具深刻地闡釋了生物形態(tài)和生物化學的問題，對生物數(shù)學的發(fā)展起了直接的推動作用． 圖靈思想活躍，但性格較內(nèi)向．他愛好體育，在劍橋上學時就當過賽艇劃手，40年代以后更把長跑當作主要的鍛煉和休息形式．他在國家物理學研究所的運動會上得過1英里跑和3英里跑的冠軍；還得過3英里跑的俱樂部冠軍；1947年，他參加了英國業(yè)余體聯(lián)舉辦的馬拉松冠軍賽并進入了前15名，此時他已名揚四海，報紙上稱他為“電子運動員”．圖靈終身未婚．1954年6月7日，圖靈可能由于偶然事故——氰化鉀中毒卒于威姆斯洛他自己的寓所中． 圖靈在科學、特別在數(shù)理邏輯和計算機科學方面，取得了舉世矚目的成就，他的一些科學成果，構成了現(xiàn)代計算機技術的基礎． 1．可計算性理論 計算，可以說是人類最先遇到的數(shù)學課題，并且在漫長的歷史年代里，成為人們社會生活中不可或缺的工具．那么，什么是計算呢？直觀地看，計算一般是指運用事先規(guī)定的規(guī)則，將一組數(shù)值變換為另一(所需的)數(shù)值的過程．對某一類問題，如果能找到一組確定的規(guī)則，按這組規(guī)則，當給出這類問題中的任一具體問題后，就可以完全機械地在有限步內(nèi)求出結果，則說這類問題是可計算的．這種規(guī)則就是算法，這類可計算問題也可稱之為存在算法的問題．這就是直觀上的能行可計算或算法可計算的概念． 在20世紀以前，人們普遍認為，所有的問題類都是有算法的，人們的計算研究就是找出算法來．似乎正是為了證明一切科學命題，至少是一切數(shù)學命題存在算法，G．W．萊布尼茨(Leibniz)開創(chuàng)了數(shù)理邏輯的研究工作．但是20世紀初，人們發(fā)現(xiàn)有許多問題已經(jīng)過長期研究，仍然找不到算法，例如希爾伯特第10問題，半群的字的問題等．于是人們開始懷疑，是否對這些問題來說，根本就不存在算法，即它們是不可計算的．這種不存在性當然需要證明，這時人們才發(fā)現(xiàn)，無論對算法還是對可計算性，都沒有精確的定義！按前述對直觀的可計算性的陳述，根本無法作出不存在算法的證明，因為“完全機械地”指什么？“確定的規(guī)則”又指什么？仍然是不明確的．實際上，沒有明確的定義也不能抽象地證明某類問題存在算法，不過存在算法的問題一般是通過構造出算法來確證的，因而可以不涉及算法的精確定義問題． 解決問題的需要促使人們不斷作出探索．1934年，K．哥德爾(Godel)在J．埃爾布朗(Herbrand)的啟示下提出了一般遞歸函數(shù)的概念，并指出：凡算法可計算函數(shù)都是一般遞歸函數(shù)，反之亦然．1936年，C．克林(Kleene)又加以具體化．因此，算法可計算函數(shù)的一般遞歸函數(shù)定義后來被稱為埃爾布朗-哥德爾-克林定義．同年，丘奇證明了他提出的λ可定義函數(shù)與一般遞歸函數(shù)是等價的，并提出算法可計算函數(shù)等同于一般遞歸函數(shù)或λ可定義函數(shù)，這就是著名的“丘奇論點”． 用一般遞歸函數(shù)雖給出了可計算函數(shù)的嚴格數(shù)學定義，但在具體的計算過程中，就某一步運算而言，選用什么初始函數(shù)和基本運算仍有不確定性．為消除所有的不確定性，圖靈在他的“論可計算數(shù)及其在判定問題中的應用”一文中從一個全新的角度定義了可計算函數(shù)．他全面分析了人的計算過程，把計算歸結為最簡單、最基本、最確定的操作動作，從而用一種簡單的方法來描述那種直觀上具有機械性的基本計算程序，使任何機械(能行)的程序都可以歸約為這些動作．這種簡單的方法是以一個抽象自動機概念為基礎的，其結果是：算法可計算函數(shù)就是這種自動機能計算的函數(shù)．這不僅給計算下了一個完全確定的定義，而且第一次把計算和自動機聯(lián)系起來，對后世產(chǎn)生了巨大的影響，這種“自動機”后來被人們稱為“圖靈機”． 圖靈機是一種自動機的數(shù)學模型，它是一條兩端(或一端)無限延長的紙帶，上面劃成方格，每個方格中可以印上某字母表中的一個字母(亦可為空格，記為S0)；又有一個讀寫頭，它具有有限個內(nèi)部狀態(tài)．任何時刻讀寫頭都注視著紙帶上的某一個方格，并根據(jù)注視方格的內(nèi)容以及讀寫頭當時的內(nèi)部狀態(tài)而執(zhí)行變換規(guī)則所規(guī)定的動作．每個圖靈機都有一組變換規(guī)則，它們具有下列三種形狀之一： qiaRqi，qiaLqi，qiabqj． 意思是：當讀寫頭處于狀態(tài)qi時如果注視格的內(nèi)容為字母a則讀寫頭右移一格，或左移一格，或印下字母b(即把注視格的內(nèi)容由a改成b．a(chǎn)，b可為S0)． 圖靈把可計算函數(shù)定義為圖靈機可計算函數(shù)．1937年，圖靈在他的“可計算性與λ可定義性”一文中證明了圖靈機可計算函數(shù)與λ可定義函數(shù)是等價的，從而拓廣了丘奇論點，得出：算法(能行)可計算函數(shù)等同于一般遞歸函數(shù)或λ可定義函數(shù)或圖靈機可計算函數(shù)．這就是“丘奇-圖靈論點”，相當完善地解決了可計算函數(shù)的精確定義問題，對數(shù)理邏輯的發(fā)展起了巨大的推動作用． 圖靈機的概念有十分獨特的意義：如果把圖靈機的內(nèi)部狀態(tài)解釋為指令，用字母表的字來表示，與輸出字輸入字同樣存貯在機器里，那就成為電子計算機了．由此開創(chuàng)了“自動機”這一學科分支，促進了電子計算機的研制工作． 與此同時，圖靈還提出了通用圖靈機的概念，它相當于通用計算機的解釋程序，這一點直接促進了后來通用計算機的設計和研制工作，圖靈自己也參加了這一工作． 在給出通用圖靈機的同時，圖靈就指出，通用圖靈機在計算時，其“機械性的復雜性”是有臨界限度的，超過這一限度，就要靠增加程序的長度和存貯量來解決．這種思想開啟了后來計算機科學中計算復雜性理論的先河． 2．判定問題 所謂“判定問題”指判定所謂“大量問題”是否具有算法解，或者是否存在能行性的方法使得對該問題類的每一個特例都能在有限步驟內(nèi)機械地判定它是否具有某種性質(zhì)(如是否真，是否可滿足或是否有解等，隨大量問題本身的性質(zhì)而定)的問題． 判定問題與可計算性問題有密切的聯(lián)系，二者可以相互定義：對一類問題若能找到確定的算法以判定其是否具有某種性質(zhì)，則稱這類問題是能行可判定的，或可解的；否則是不可判定的，或不可解的．二者又是有區(qū)別的：判定問題是要確定是否存在一個算法，使對一類問題的每一個特例都能對某一性質(zhì)給以一個“是”或“否”的解答；可計算性問題則是找出一個算法，從而求出一些具體的客體來． 圖靈在判定問題上的一大成就是把圖靈機的“停機問題”作為研究許多判定問題的基礎，一般地，把一個判定問題歸結為停機問題：“如果問題A可判定，則停機問題可判定．”從而由“停機問題是不可判定的”推出“問題A是不可判定的”． 所謂停機指圖靈機內(nèi)部達到一個結果狀態(tài)、指令表上沒有的狀態(tài)或符號對偶，從而導致計算終止．在每一時刻，機器所處的狀態(tài)，紙帶上已被寫上符號的所有格子以及機器當前注視的格子位置，統(tǒng)稱為機器的格局．圖靈機從初始格局出發(fā)，按程序一步步把初始格局改造為格局的序列．此過程可能無限制繼續(xù)下去，也可能遇到指令表中沒有列出的狀態(tài)、符號組合或進入結束狀態(tài)而停機．在結束狀態(tài)下停機所達到的格局是最終格局，此最終格局(如果存在)就包含機器的計算結果．所謂停機問題即是：是否存在一個算法，對于任意給定的圖靈機都能判定任意的初始格局是否會導致停機？圖靈證明，這樣的算法是不存在的，即停機問題是不可判定的，從而使之成為解決許多不可判定性問題的基礎． 1937年，圖靈用他的方法解決了著名的希爾伯特判定問題：狹謂詞演算(亦稱一階邏輯)公式的可滿足性的判定問題．他用一階邏輯中的公式對圖靈機進行編碼，再由圖靈機停機問題的不可判定性推出一階邏輯的不可判定性．他在此處創(chuàng)用的“編碼法”成為后來人們證明一階邏輯的公式類的不可判定性的主要方法之一． 在判定問題上，圖靈的另一成果是1939年提出的帶有外部信息源的圖靈機概念，并由此導出“圖靈可歸約”及相對遞歸的概念．運用歸約和相對遞歸的概念，可對不可判定性與非遞歸性的程度加以比較．在此基礎上，E．波斯特(Post)提出了不可解度這一重要概念，這方面的工作后來有重大的進展． 圖靈參與解決的另一個著名的判定問題是“半群的字的問題”，它是A．圖埃(Thue)在1914年提出來的：對任意給定的字母表和字典，是否存在一種算法能判定兩個任意給定的字是否等價［給出有限個不同的稱為字母的符號，便給出了字母表，字母的有限序列稱為該字母表上的字．把有限個成對的字(A1，B1)，…，(An，Bn)稱為字典．如果兩個字R和S使用有限次字典之后可以彼此變換，則稱這兩個字是等價的］？1947年，波斯特和A．A．馬爾科夫(Markov)用圖靈的編碼法證明了這一問題是不可判定的．1950年，圖靈進一步證明，滿足消元律的半群的字的問題也是不可判定的． 3．電子計算機 電子計算機的出現(xiàn)和廣泛應用是20世紀新技術革命的主要標志之一．很長時期中人們一直認為，第一臺電子計算機是美國人按J．W．莫奇利(Mauchly)提出的方案于1946年制成的“電子數(shù)字積分和自動計算機”(ENIAC)．圖靈在第二次世界大戰(zhàn)中從事的密碼破譯工作涉及到電子計算機的設計和研制，但此項工作嚴格保密．直到70年代，內(nèi)情才有所披露．從一些文件來看，很可能世界上第一臺電子計算機不是ENIAC，而是與圖靈有關的另一臺機器，即圖靈在戰(zhàn)時服務的機構于1943年研制成功的CO-LOSSUS(巨人)機，這臺機器的設計采用了圖靈提出的某些概念．它用了1500個電子管，采用了光電管閱讀器；利用穿孔紙帶輸入；并采用了電子管雙穩(wěn)態(tài)線路，執(zhí)行計數(shù)、二進制算術及布爾代數(shù)邏輯運算，巨人機共生產(chǎn)了10臺，用它們出色地完成了密碼破譯工作． 1946年ENIAC投入運行，以它的計算速度(每秒5000次運算)而震驚了世界．但是在它未完工之前，一些人，包括它的主要設計者就認識到，它的控制方式已不適用了：ENIAC并不是像現(xiàn)在的計算機那樣用程序來進行控制，而是利用硬件即利用插線板和轉換開關所連接的邏輯電路來控制運算．這樣一來，這臺機器固然可以在幾分鐘內(nèi)作完極復雜的運算，但要改變一下運算題目，卻要花十幾小時甚至幾十小時才能做好準備．因此，如何用程序自動控制運算就成為提高電子計算機效率的關鍵性問題． 1945年初，J．馮諾伊曼(von Neumann)、莫奇利等人提出了著名的EDVAC［electronic discret variable automatic comp-uter(離散變量自動電子計算機)］方案，提出關于存貯程序控制的電子計算機的總體設想，指出這種計算機應由計算器、控制器、存貯器及輸入、輸出裝置等五個部分組成(后來形成了左右電子計算機40余年的所謂“馮諾伊曼方式”)，但沒有提出進一步的結構設計．1945年底圖靈寫出的關于ACE的設計說明書中，最先給出了存貯程序控制計算機的結構設計(圖靈后來參與研制的Madam機則是當時世界上存貯量最大的電子計算機)．在圖靈的這份說明書中還最先提出了指令寄存器和指令地址寄存器的概念，提出了子程序和子程序庫的思想，這都是現(xiàn)代電子計算中最基本的概念和思想．令人吃驚的是，在這份說明書中，圖靈已提出了“仿真系統(tǒng)”的思想，所謂仿真系統(tǒng)，指機器可以沒有固定的指令系統(tǒng)，但它能夠模擬許多具有不同指令系統(tǒng)的計算機的功能．英國的ACE機只采用了圖靈的部分思想，而出于保密的需要，圖靈的ACE設計說明書，直到1972年才得以發(fā)表．這期間，人們不得不重新發(fā)現(xiàn)圖靈已經(jīng)發(fā)現(xiàn)過的東西，恰恰也是在1972年，人們才制成具有仿真系統(tǒng)的計算機． 4．人工智能 圖靈是人工智能研究的先驅者之一，實際上，圖靈機，尤其是通用圖靈機作為一種非數(shù)值符號計算的模型，就蘊含了構造某種具有一定的智能行為的人工系統(tǒng)以實現(xiàn)腦力勞動部分自動化的思想，這正是人工智能的研究目標．而且正是從圖靈機概念出發(fā)，在第二次世界大戰(zhàn)時的軍事工作期間，圖靈在業(yè)余時間里經(jīng)?？紤]并與一些同事探討“思維機器”的問題，并且進行了“機器下象棋”一類的初步研究工作． 1947年，圖靈在一次關于計算機的會議上作了題為“智能機器”(intelligent machinery)的報告，詳細地闡述了他關于思維機器的思想，第一次從科學的角度指出：“與人腦的活動方式極為相似的機器是可以制造出來的．”在該報告中，圖靈提出了自動程序設計的思想，即借助證明來構造程序的思想．現(xiàn)在自動程序設計已成為人工智能的基本課題之一．圖靈這一報告中的思想極為深刻、新奇，似乎超出了當時人們的想象力．1959年，這一報告編入圖靈的著作選集首次發(fā)表時，似乎仍未引起人們的重視．只是當1969年，這一報告再次發(fā)表，人工智能已有了相當進展，尤其是R．J．瓦丁格(Waldingger)于1969年重新提出自動程序設計的概念，人們才開始理解了圖靈這一報告的開創(chuàng)性意義． 1950年，圖靈發(fā)表了著名的“計算機和智能”的論文．這篇文章對智能給出一個行為主義的定義，并設計了著名的“圖靈測驗”，即一個人在不接觸對象的情況下，同對象進行一系列的問答(可借助電傳打寫機)，如果他根據(jù)這些問答無法判斷對象是人還是計算機，那么就可以認為這個計算機具有同人相當?shù)闹橇?，圖靈還預言，20世紀末將會出現(xiàn)這樣的機器．1956年圖靈的這篇文章以“機器能夠思維嗎？”為題重新發(fā)表．此時，人工智能也進入了實踐研制階段．圖靈的機器智能思想無疑是人工智能的直接起源之一．而且隨人工智能領域的深入研究，人們越來越認識到圖靈思想的深刻性：它們至今仍然是人工智能的主要思想之一． 5．其他成果 圖靈思想活躍，他的創(chuàng)造力也是多方面的．據(jù)同事們回憶，他在戰(zhàn)時的秘密工作中，曾創(chuàng)造好幾種新的統(tǒng)計技術，但都未形成論文發(fā)表，后來又重新為他人所創(chuàng)建，由A．瓦爾德(Wald)重新發(fā)現(xiàn)并提出的“序貫分析”就是其中之一．他對群論也有所研究．在“形態(tài)形成的化學基礎”一文中，他用相當深奧而獨特的數(shù)學方法，研究了決定生物的顏色或形態(tài)的化學物質(zhì)(他稱之為成形素)在形成平面形態(tài)(如奶牛體表的花斑)和立體形態(tài)(如放射形蟲和葉序的分布方式)中的分布規(guī)律性，試圖闡釋“物理化學規(guī)律可以充分解釋許多形態(tài)形成的事實”這一思想．在生物學界，80年代才開始探討這一課題．圖靈還進行了后來被稱為“數(shù)學胚胎學”的奠基性研究工作．他還試圖用數(shù)學方法研究人腦的構造問題，例如估算出一個具有給定數(shù)目的神經(jīng)元的大腦中能存貯多少信息的問題等．這些，至今仍然是吸引著眾多科學家的新穎課題． 人們認為，圖靈是一位科學史上罕見的具有非凡洞察力的奇才：他的獨創(chuàng)性成果使他生前就已名揚四海，而他深刻的預見使他死后倍受敬佩．當人們發(fā)現(xiàn)后人的一些獨立研究成果似乎不過是在證明圖靈思想超越時代的程度時，怎能不為他的英年早逝感到由衷的惋惜呢！為了紀念他對計算機科學的巨大貢獻，美國計算機協(xié)會從60年代起設立一年一度的圖靈獎，以表彰在計算機科學中做出突出貢獻的人． |
|
|
來自： l1hf > 《數(shù)學家》
