圖靈機(jī)和通用圖靈機(jī)

“大學(xué)生IT創(chuàng)新教學(xué)實(shí)踐”活動(dòng)

培養(yǎng)好的心智與理想

擁有豐富的專業(yè)理論知識(shí)與實(shí)踐能力

鍛煉強(qiáng)健的身體西北大學(xué)信息科學(xué)與技術(shù)學(xué)院1圖靈（AlanTuring）的偉大貢獻(xiàn)

--紀(jì)念圖靈誕辰100周年

郝克剛

2011.10.學(xué)術(shù)報(bào)告會(huì)2圖靈和圖靈機(jī)就如同文學(xué)院的學(xué)生都熟悉曹雪芹和紅樓夢(mèng)，物理系的學(xué)生都熟悉愛(ài)因斯坦和相對(duì)論一樣，計(jì)算機(jī)有關(guān)專業(yè)和學(xué)科的學(xué)生，不能不知曉計(jì)算機(jī)和計(jì)算機(jī)科學(xué)理論的奠基人圖靈以及圖靈機(jī)等的基本知識(shí)和概念。1912-19543圖靈（AlanTuring）英國(guó)數(shù)學(xué)家圖靈（AlanTuring）是計(jì)算機(jī)和計(jì)算機(jī)科學(xué)理論的奠基人。他出生于1912年6月23日，明年是他誕辰100周年。為了紀(jì)念他對(duì)計(jì)算機(jī)科學(xué)的偉大貢獻(xiàn)，從今年年底開(kāi)始世界計(jì)算機(jī)界要舉行一系列的紀(jì)念活動(dòng)，。

2012年是圖靈年AlanTuringYear4提綱：一串待思考的問(wèn)題圖靈的生平什么是圖靈機(jī)和通用圖靈機(jī)為什么說(shuō)它是電子計(jì)算機(jī)的理論基礎(chǔ)有超越圖靈機(jī)計(jì)算能力的模型嗎是否存在計(jì)算機(jī)不可解的問(wèn)題怎么度量計(jì)算的能力和復(fù)雜度圖靈測(cè)試，計(jì)算機(jī)能思維嗎圖靈獎(jiǎng)，對(duì)年輕人的期盼和希望51.圖靈的生平圖靈AlanMathisonTuring1912年6月23日出生于英國(guó)倫敦近郊。父親是英國(guó)駐印度的官員。寄養(yǎng)在別人家中。1926年后中學(xué)寄宿，喜歡賽跑。6劍橋大學(xué)King‘sCollege1930年圖靈進(jìn)入劍橋大學(xué)King‘sCollege攻讀數(shù)學(xué)。1934年他22歲時(shí)，完成了學(xué)位論文，7圖靈機(jī)器概念的提出

1935年圖靈對(duì)數(shù)理邏輯發(fā)生興趣。1936年發(fā)表“論可計(jì)算數(shù)及其在判定問(wèn)題中的應(yīng)用”一文。圖靈機(jī)器就是為此提出的一個(gè)概念。論文發(fā)表后引起美國(guó)科學(xué)家的重視，應(yīng)邀到美國(guó)普林斯頓大學(xué)，1938取得博士學(xué)位8破譯了德軍密碼光榮受勛1938年回英國(guó)劍橋大學(xué)。1939年進(jìn)入英國(guó)政府的一研究機(jī)構(gòu)，破譯了德軍密碼，戰(zhàn)后光榮受勛。戰(zhàn)后進(jìn)入英國(guó)國(guó)家物理實(shí)驗(yàn)室，開(kāi)始了設(shè)計(jì)和建造英國(guó)的電子計(jì)算機(jī)工程（ACE）。1951被選為英國(guó)皇家學(xué)會(huì)院士。。1954年6月7日因吃了含氰化物的蘋(píng)果，在家中死亡，享年不足42歲。死因成不解之謎。自殺或意外。2008.9布朗的政府道歉。92.圖靈機(jī)和通用圖靈機(jī)圖靈機(jī)器是圖靈在他的論文中提出的一個(gè)抽象的計(jì)算機(jī)模型。模型非常簡(jiǎn)單，由下面幾部分構(gòu)成：n個(gè)符號(hào)S={s1,…,sn},

其中有空格符號(hào)b

S；m個(gè)狀態(tài)Q={q1,…,qm},

其中有初始狀態(tài)q1

Q10無(wú)窮長(zhǎng)的由格子組成的帶子。一條兩個(gè)方向或一個(gè)方向是潛在無(wú)窮長(zhǎng)的由格子組成的帶子。每個(gè)格子可存放一個(gè)符號(hào)。帶子邊附有一個(gè)讀寫(xiě)頭，qj

Si讀寫(xiě)頭處于某個(gè)狀態(tài)并指向某個(gè)格子，可以讀寫(xiě)所指格子上的符號(hào)，并在帶子上左右移動(dòng)。 11一組有窮條形如下式的規(guī)則：si,qj

sk,ql,d.

其中d=H,L或R.執(zhí)行開(kāi)始時(shí)，在圖靈機(jī)帶子的一串格子上放上由符號(hào)（除b外）組成的初始字。讀寫(xiě)頭處于初始狀態(tài)q1，并指向初始字的第一個(gè)格子。然后如下執(zhí)行。如果所指的符號(hào)是si,讀頭的狀態(tài)是qj，在所指格子上寫(xiě)符號(hào)sk，讀頭變換狀態(tài)為ql，根據(jù)d的值（d=H,L或R）讀頭位置保持不動(dòng)(H)，左移(L)或右移(R)一格。12圖靈機(jī)器

演示siqjS

：{s1,…,sn

}Q：{q1,…,qm

}…si,qj

sk,ql,d

其中d=H,L或Rskqlqlql…13通用圖靈機(jī)的概念演示存在這樣的一個(gè)圖靈機(jī)T，稱為通用圖靈機(jī)(UniversalTuringMachine):對(duì)任給的圖靈機(jī)A，只要把它(A)的規(guī)則和初始字，并列起來(lái)作為通用圖靈機(jī)T的初始字，讓通用圖靈機(jī)T運(yùn)行，運(yùn)行結(jié)果就是圖靈機(jī)A的運(yùn)行結(jié)果。正是這個(gè)思想奠定了10年后通用電子計(jì)算機(jī)出現(xiàn)的理論基礎(chǔ)。143.

電子計(jì)算機(jī)出現(xiàn)的理論基礎(chǔ)第一臺(tái)電子數(shù)字計(jì)算機(jī)ENIAC(ElectronicNumericalIntegratorandComputer)1946.2誕生于美國(guó)賓州大學(xué)莫爾學(xué)院。

ENIAC是一臺(tái)為各種炮火計(jì)算彈道的專用計(jì)算機(jī)，程序是用外接電路板輸入。后查證，世界上第一臺(tái)專用電子計(jì)算機(jī)，1939年愛(ài)荷華（Iowa）州立大學(xué)用電子管開(kāi)發(fā)了Atanasoff–BerryComputer(簡(jiǎn)稱ABC)，另外，二戰(zhàn)中德國(guó)也研制了計(jì)算機(jī)。15馮·諾伊曼的設(shè)計(jì)思想1945年馮·諾伊曼（VonNeumann）發(fā)表“關(guān)于離散變量自動(dòng)電子計(jì)算機(jī)的草案”。最早提出“存儲(chǔ)程序式”的通用計(jì)算機(jī)的設(shè)計(jì)思想。計(jì)算機(jī)EDVAC(ElectronicDiscreteVariableAutomaticComputer)由他設(shè)計(jì)的，建造合同1946年4月簽訂。預(yù)算是十萬(wàn)美元,但最后耗資五十萬(wàn)。1949年8月交付美國(guó)軍隊(duì)的彈道研究實(shí)驗(yàn)室，1951年開(kāi)始運(yùn)行。1903-195716馮·諾伊曼的設(shè)計(jì)思想來(lái)自圖靈第一臺(tái)“存儲(chǔ)程序式”計(jì)算機(jī)。EDSAC(ElectronicDelayStorageAutomaticCalculator)英國(guó)劍橋大學(xué)威爾克斯（MauriceVincentWilkes）領(lǐng)導(dǎo)設(shè)計(jì)和制造的,1949年5月6日試運(yùn)行成功。1951年批量生產(chǎn)投入市場(chǎng)但是他的設(shè)計(jì)思想完全來(lái)自馮·諾伊曼的EDVAC的設(shè)計(jì)。而馮·諾伊曼的設(shè)計(jì)思想?yún)s又來(lái)自圖靈1936年的文章中引入的概念—圖靈機(jī)器和通用圖靈機(jī)。17圖靈機(jī)奠定了通用電子計(jì)算機(jī)設(shè)計(jì)的理論基礎(chǔ)之所以這么快就由硬件連線構(gòu)成的專用計(jì)算機(jī)過(guò)渡到“存儲(chǔ)程序式”的通用計(jì)算機(jī)，完全歸功于通用圖靈機(jī)概念的引入。因而我們說(shuō)，是圖靈的圖靈機(jī)理論奠定了通用電子計(jì)算機(jī)設(shè)計(jì)的理論基礎(chǔ)。這種理論準(zhǔn)備同電子技術(shù)的結(jié)合才最終產(chǎn)生了20世紀(jì)最偉大的奇跡。18最早設(shè)計(jì)可編程計(jì)算機(jī)巴貝奇Babbage是最早設(shè)計(jì)可編程計(jì)算機(jī)的人。他設(shè)計(jì)了分析機(jī)，以蒸汽為動(dòng)力的計(jì)算器械，目的是編制各類數(shù)學(xué)表，可用穿孔卡寫(xiě)出程序控制計(jì)算過(guò)程；說(shuō)明計(jì)算過(guò)程可自動(dòng)化。描述了一系列設(shè)計(jì)，到1871年Babbage死去還未造出機(jī)器。Charles

Babbage1791-187119歷史上第一個(gè)編程序的人AugustaAdaKing充分了解Babbage機(jī)器，1842年－1843年的9個(gè)月里，她在一篇文章的注記中用分析機(jī)器的指令寫(xiě)下如何計(jì)算伯努利（Bernoulli）數(shù)的詳細(xì)步驟，這證明了分析機(jī)器的能力．史學(xué)家們認(rèn)為這注記是歷史上第一個(gè)程序。1979年，美國(guó)國(guó)防部以她的名字命名了他們的語(yǔ)言Ada語(yǔ)言1998年起英國(guó)計(jì)算機(jī)學(xué)會(huì)建立Ada

獎(jiǎng)。由2008年起搞一年一度的女學(xué)生計(jì)算機(jī)科學(xué)競(jìng)賽。AugustaAdaKing1815-1852204.有超越圖靈機(jī)計(jì)算能力的模型嗎圖靈機(jī)是為直觀的“計(jì)算”給出一個(gè)嚴(yán)格的形式化的定義。它的神妙之處還在于它的組成和執(zhí)行規(guī)則相當(dāng)簡(jiǎn)單，但是功能卻非常強(qiáng)大。試圖對(duì)其擴(kuò)展來(lái)擴(kuò)大它的計(jì)算能力都不成功。例如多增加幾個(gè)無(wú)窮長(zhǎng)的帶子和讀頭，最后證明它的計(jì)算能力還是等價(jià)于原來(lái)的圖靈機(jī)。即使是非確定的圖靈機(jī)的能力也等價(jià)于確定的圖靈機(jī)。21丘奇-圖靈論題圖靈1937年被邀請(qǐng)到美國(guó)普林斯頓和丘奇(AlonzoChurch)一起合作，他們提出了一個(gè)后來(lái)被叫做丘奇-圖靈論題。這個(gè)論題斷言圖靈機(jī)同直觀的有效的函數(shù)計(jì)算具有等價(jià)的問(wèn)題求解機(jī)制。即所有“能解”的問(wèn)題都存在一個(gè)圖靈機(jī)，只要把問(wèn)題放在圖靈機(jī)帶子上，若有解則停機(jī)后帶子內(nèi)容即是解答。這個(gè)斷言叫做“論題”是由于他無(wú)法嚴(yán)格證明。1903-199522全都被證明同圖靈機(jī)等價(jià)那個(gè)時(shí)代和后來(lái)曾經(jīng)提出過(guò)不少的形式化計(jì)算模型，如λ演算、遞歸函數(shù)、正規(guī)算法、POST系統(tǒng)、遞歸算法（胡世華）等，全都被證明同圖靈機(jī)等價(jià)。這些事實(shí)在一定程度上加強(qiáng)了這個(gè)論題。1912-199823有一些對(duì)此論題的質(zhì)疑當(dāng)然在學(xué)界也有一些對(duì)此論題的質(zhì)疑，例如有人認(rèn)為交互式機(jī)器超越了圖靈機(jī)（PeterWegner），有人認(rèn)為量子計(jì)算機(jī)，生物計(jì)算機(jī)可能會(huì)超越圖靈機(jī)，但是這些意見(jiàn)都還沒(méi)有能給出具有說(shuō)服力的論證，從而也沒(méi)有為普遍學(xué)者所認(rèn)可。在紀(jì)念圖靈誕辰100周年之際，關(guān)于是否有超越圖靈機(jī)計(jì)算能力的模型也是一個(gè)爭(zhēng)論的熱門(mén)話題。245.是否存在計(jì)算機(jī)不可解的問(wèn)題由于圖靈機(jī)是為“計(jì)算”給出的一個(gè)嚴(yán)格的形式化的定義。從而使嚴(yán)格證明某些問(wèn)題是“不可計(jì)算”（“不可解”或“不可判定”）成為可能。要知道這種否定的證明通常是相當(dāng)困難的，所以說(shuō)這也是圖靈的一個(gè)重要貢獻(xiàn)。25許多實(shí)際數(shù)學(xué)問(wèn)題是不可判定的。首先可以證明圖靈機(jī)的停機(jī)問(wèn)題是不可判定的。接著證明了推導(dǎo)系統(tǒng)的字的問(wèn)題是不可判定的。后來(lái)又證明了邏輯系統(tǒng)以外的許多實(shí)際數(shù)學(xué)問(wèn)題是不可判定的。如有名的希爾伯特第十問(wèn)題是不可解的，即不存在這樣的算法，它能判定一個(gè)任意的丟番圖方程(DiophantineEquation)是否有整數(shù)解。DavidHilbert1862-194326丟番圖方程(DiophantineEquation)整系數(shù)代數(shù)多項(xiàng)式方程，有無(wú)整數(shù)解？x2+y2=z2，勾3股4弦五5中國(guó)古代已知有整數(shù)解。xn+yn=zn

在n>2時(shí)沒(méi)有非零整數(shù)解，費(fèi)爾馬(Pierre

de

Fermat,

1601-1665)猜想，隔了三百多年(1995)才得到證明。

聰明的俄國(guó)年輕人馬蒂亞塞維奇(YuriMatiyasevich,)1970年（23歲）成功地證明了羅賓遜猜想，最終解決了希爾伯特第十問(wèn)題,證明它是不可解的。Matiyasevich1947-27不可解的問(wèn)題程度層次的不同，即使是不可解的問(wèn)題，也有程度層次的不同，克林(StephenKleene)曾對(duì)其進(jìn)行了分層。筆者早期也曾涉及此類研究，提出過(guò)“可構(gòu)造實(shí)數(shù)論中若干謂詞在Kleen分層下所屬的類型”（《數(shù)學(xué)學(xué)報(bào)》1964年第四期。）286.怎么度量計(jì)算的能力和復(fù)雜度圖靈機(jī)的提出，影響深遠(yuǎn)，可以說(shuō)它為以后整個(gè)計(jì)算機(jī)科學(xué)的研究奠定了重要的理論基礎(chǔ)。例如關(guān)于形式語(yǔ)言和自動(dòng)機(jī)的理論和算法復(fù)雜度的理論研究就以圖靈機(jī)作為基礎(chǔ)，它對(duì)計(jì)算機(jī)編譯系統(tǒng)和操作系統(tǒng)技術(shù)以及應(yīng)用軟件的發(fā)展起著重要作用。29機(jī)器的計(jì)算能力判斷一類機(jī)器的計(jì)算能力，可以以其能計(jì)算的函數(shù)類型和所能接受的字的類型來(lái)劃分。說(shuō)某機(jī)器M接受某個(gè)字

w，是指如果以字w作為機(jī)器M的輸入（對(duì)圖靈機(jī)來(lái)說(shuō)就是作為他的初始字），運(yùn)行后以某指定的接受狀態(tài)結(jié)束計(jì)算。也就是說(shuō)，如果M在其他狀態(tài)結(jié)束計(jì)算，或計(jì)算不終止，則M不接受該字

w。

30語(yǔ)言進(jìn)行分類喬姆斯基（AvramNoamChomsky）曾按生成文法的不同對(duì)語(yǔ)言進(jìn)行分類。所謂語(yǔ)言就是某字母表上字的集合。而后來(lái)發(fā)現(xiàn)語(yǔ)言又和接受它的機(jī)器類型有關(guān)1928-31理論研究證明如下的對(duì)應(yīng)關(guān)系：語(yǔ)言類型生成文法接受的機(jī)器類型0型語(yǔ)言0型文法圖靈機(jī)一型語(yǔ)言上下文有感文法線性有界自動(dòng)機(jī)二型語(yǔ)言上下文無(wú)關(guān)文法下推自動(dòng)機(jī)三型語(yǔ)言正則文法有窮自動(dòng)機(jī)32關(guān)于算法復(fù)雜度的研究同樣是算法，在機(jī)器上運(yùn)行時(shí)所需要的時(shí)間和空間資源的數(shù)量時(shí)常相差很大。因而需要定義算法的復(fù)雜度來(lái)作為度量算法優(yōu)劣的一個(gè)重要指標(biāo)。假定算法在圖靈機(jī)上計(jì)算的輸入字的長(zhǎng)度是l，那么完成此計(jì)算所需要的最長(zhǎng)時(shí)間（即運(yùn)算的最長(zhǎng)步數(shù)）是l的一個(gè)函數(shù)，稱此函數(shù)為此算法的時(shí)間復(fù)雜度。同樣，完成此計(jì)算所需要的最大空間（即運(yùn)算涉及的格子最大數(shù)量）也是l的一個(gè)函數(shù)，稱此函數(shù)為此算法的空間復(fù)雜度。33時(shí)間、空間復(fù)雜度例如函數(shù)不超過(guò)多項(xiàng)式函數(shù)，就說(shuō)此算法具有多項(xiàng)式時(shí)間或多項(xiàng)式空間復(fù)雜度。函數(shù)不超過(guò)指數(shù)函數(shù)，就說(shuō)此算法具有指數(shù)時(shí)間或指數(shù)空間復(fù)雜度。34指數(shù)比多項(xiàng)式函數(shù)增長(zhǎng)快得多n22n35“實(shí)際可行的(feasible)”算法例如：多項(xiàng)式函數(shù)t=n3,n=60,t=216000，一臺(tái)百萬(wàn)次計(jì)算機(jī)，0.2秒即可完成。而指數(shù)函數(shù)。t=3n,n=60,t=360

4x1028，若能用10億臺(tái)百萬(wàn)次計(jì)算機(jī)并行運(yùn)算，需要運(yùn)行一百萬(wàn)年。因而常認(rèn)為具有多項(xiàng)式時(shí)間復(fù)雜度的算法是“實(shí)際可行的(feasible)”算法。而具有指數(shù)時(shí)間復(fù)雜度的算法是實(shí)際不可行的。36“千僖年數(shù)學(xué)難題”這里再順便介紹一下懸賞獎(jiǎng)金一百萬(wàn)美元巨獎(jiǎng)，被稱為“千僖年數(shù)學(xué)難題”之一的“P=NP?”問(wèn)題。這個(gè)問(wèn)題是：“在多項(xiàng)式時(shí)間界限下，確定的和非確定的圖靈機(jī)器是否具有同等的功能？”37確定的和非確定的圖靈機(jī)如果執(zhí)行中每次只可能有一個(gè)規(guī)則匹配，也就是說(shuō)所有規(guī)則的左端都不完全相同，圖靈機(jī)的執(zhí)行是唯一確定的，稱這樣的機(jī)器為確定的圖靈機(jī)。反之，有兩個(gè)或更多的規(guī)則的左端完全相同時(shí)，圖靈機(jī)的執(zhí)行就不是唯一確定的，稱這樣的機(jī)器為非確定的圖靈機(jī)。38有些情況功能是相同的確定的和非確定的有窮自動(dòng)機(jī)的功能是相同的，它們所接受的語(yǔ)言都是正則集合。如果不加多項(xiàng)式時(shí)間的限制，確定的和非確定的圖靈機(jī)的功能也是相同的，它們所接受的語(yǔ)言都是遞歸可枚舉集。如果對(duì)圖靈機(jī)加上空間的限制，在多項(xiàng)式空間界限下，確定的和非確定的圖靈機(jī)也具有同樣的功能。39不是都具有同樣的功能但是，并不是在所有情況下確定的和非確定的機(jī)器都具有同樣的功能。例如，對(duì)具有一個(gè)下推存貯的有窮機(jī)器來(lái)講兩者的功能是不相同的，非確定性的下推自動(dòng)機(jī)所接受的語(yǔ)言是上下文無(wú)關(guān)語(yǔ)言，而確定的下推自動(dòng)機(jī)所接受的語(yǔ)言卻是上下文無(wú)關(guān)語(yǔ)言的一個(gè)真正的子類。40問(wèn)題至今仍未解決那么在多項(xiàng)式時(shí)間界限下，確定的和非確定的圖靈機(jī)器是否具有同等的功能呢？即是否P=NP?這個(gè)問(wèn)題的提法相當(dāng)清晰，但是要解答這個(gè)問(wèn)題卻不容易。當(dāng)代很多有名的計(jì)算機(jī)科學(xué)家都研究過(guò)這個(gè)問(wèn)題，問(wèn)題至今仍未解決。解決這個(gè)問(wèn)題似乎需要在方法上有重大突破。41NP完全的理論上世紀(jì)70年代提出的NP完全的理論，對(duì)解決此問(wèn)題有很大的推進(jìn)，但仍未最終解決。筆者30年前曾寫(xiě)過(guò)一篇綜述文章，"NP完全問(wèn)題及有關(guān)理論研究"（《計(jì)算機(jī)科學(xué)》，1980年1期。）不久前，有一位HP公司的工程師宣稱他證明了P!=NP，不過(guò)目前還尚未被認(rèn)可。427.圖靈測(cè)試，計(jì)算機(jī)能思維嗎人們驚奇地發(fā)現(xiàn)它的能力大大超出原來(lái)的預(yù)期。計(jì)算機(jī)不僅可以做大量的計(jì)算，還能進(jìn)行復(fù)雜的推理。于是就把它同人的大腦進(jìn)行比較，提出“計(jì)算機(jī)能思維嗎(Canmachinesthink?)”的問(wèn)題。這里涉及到對(duì)“什么是思維”的理解和界定，涉及哲學(xué)、認(rèn)知學(xué)以及社會(huì)學(xué)等各個(gè)方面，相當(dāng)復(fù)雜眾說(shuō)紛紜，很難有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)。43圖靈測(cè)試圖靈1950年10月在英國(guó)曼徹斯特大學(xué)發(fā)表論文“計(jì)算機(jī)和智能”，巧妙地把這個(gè)問(wèn)題轉(zhuǎn)化為一種可操作的方法，那就是測(cè)試。后來(lái)被稱為圖靈測(cè)試。簡(jiǎn)單說(shuō)就是與其爭(zhēng)論什么是“思維”，不如我們?nèi)プ鰧?shí)驗(yàn)測(cè)試。計(jì)算機(jī)通過(guò)了測(cè)試就說(shuō)該計(jì)算機(jī)能思維，否則就說(shuō)還達(dá)不到思維的水平。44圖靈測(cè)試的設(shè)計(jì)測(cè)試分測(cè)試人員和被測(cè)試方兩部分。被測(cè)試方由A和B構(gòu)成，A和B分別是一個(gè)人和一臺(tái)被測(cè)試的計(jì)算機(jī)。測(cè)試人員和被測(cè)試方是分開(kāi)的，測(cè)試人員并不知道A和B那個(gè)是人那個(gè)是計(jì)算機(jī)。AB45通過(guò)測(cè)試被認(rèn)為是能夠思維的測(cè)試人員分別向A和B提問(wèn)，如果測(cè)試人員能夠通過(guò)問(wèn)題的回答，分不出A和B誰(shuí)是機(jī)器誰(shuí)是人，那這個(gè)機(jī)器就通過(guò)圖靈測(cè)試。圖靈指出：“如果機(jī)器在某些條件下，能夠非常好地模仿人回答問(wèn)題，以至提問(wèn)者在相當(dāng)長(zhǎng)時(shí)間里誤認(rèn)它不是機(jī)器，那么機(jī)器就可以被認(rèn)為是能夠思維的?！?6圖靈預(yù)言，50年內(nèi)通過(guò)圖靈測(cè)試當(dāng)時(shí)的計(jì)算機(jī)根本無(wú)法通過(guò)這一測(cè)試。圖靈預(yù)言，50年內(nèi)，即在20世紀(jì)末會(huì)有計(jì)算機(jī)通過(guò)圖靈測(cè)試。圖靈測(cè)試沒(méi)有規(guī)定問(wèn)題的范圍和提問(wèn)的標(biāo)準(zhǔn)，如果想要制造出能通過(guò)試驗(yàn)的機(jī)器，必須在電腦中儲(chǔ)存人類所有可以想到的問(wèn)題，儲(chǔ)存對(duì)這些問(wèn)題的所有合乎常理的回答，并且還需要理智地作出選擇。這幾乎是不可能的。到目前為止還沒(méi)有電腦能通過(guò)圖靈測(cè)試。但是如果限制在一定的領(lǐng)域和范圍之內(nèi)通過(guò)圖靈測(cè)試是完全有可能的。47計(jì)算機(jī)深藍(lán)戰(zhàn)勝國(guó)際象棋冠軍人工智能專家經(jīng)過(guò)多年的努力，開(kāi)發(fā)了不少智能軟件，在理論和實(shí)踐上取得了很大的進(jìn)步。1997年5月3-11日，IBM的計(jì)算機(jī)深藍(lán)（DeepBlue）以2勝1負(fù)3平的成績(jī)第一次戰(zhàn)勝國(guó)際象棋冠軍卡斯帕羅夫大師。也可以說(shuō)在一定意義下實(shí)現(xiàn)了圖靈的預(yù)言。自然,對(duì)于圖靈測(cè)試的理解以及它的作用等方面，學(xué)界也有各種不同的爭(zhēng)論。482208年機(jī)器能識(shí)別出我是人！498.圖靈獎(jiǎng)與對(duì)年輕人的期盼1966年，美國(guó)的國(guó)際計(jì)算機(jī)學(xué)會(huì)ACM（AssociationforComputingMachinery）為表彰圖靈對(duì)計(jì)算機(jī)科學(xué)的偉大貢獻(xiàn)，設(shè)立了圖靈獎(jiǎng)（A.M.TuringAward）。每年一屆，獎(jiǎng)金25萬(wàn)美元，獎(jiǎng)金由Intel和Google公司提供。

50計(jì)算機(jī)科學(xué)界的諾貝爾獎(jiǎng)獎(jiǎng)勵(lì)在計(jì)算機(jī)科學(xué)研究中做出創(chuàng)造性貢獻(xiàn)，推動(dòng)計(jì)算機(jī)科學(xué)技術(shù)發(fā)展的杰出科學(xué)家。選擇條件要求很高，程序極嚴(yán)，一直被公認(rèn)是世界計(jì)算機(jī)科學(xué)領(lǐng)域的最高榮譽(yù)獎(jiǎng)項(xiàng)，相當(dāng)于計(jì)算