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

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

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

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

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

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

郝克剛

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

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

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

其中有空格符號b

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

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

Q10無窮長的由格子組成的帶子。一條兩個方向或一個方向是潛在無窮長的由格子組成的帶子。每個格子可存放一個符號。帶子邊附有一個讀寫頭，qj

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

sk,ql,d.

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

演示siqjS

：{s1,…,sn

}Q：{q1,…,qm

}…si,qj

sk,ql,d

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

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

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

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

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

在n>2時沒有非零整數(shù)解，費爾馬(Pierre

de

Fermat,

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

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

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

w。

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

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

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