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