圖靈和圖靈機(jī)模型

關(guān)于圖靈和圖靈機(jī)模型第一頁，共二十五頁，編輯于2023年，星期日22.1計(jì)算本質(zhì)的認(rèn)識歷史在20世紀(jì)30年代以前，人們并沒有真正認(rèn)識計(jì)算的本質(zhì)很早以前，我國的學(xué)者認(rèn)為，對于一個(gè)數(shù)學(xué)問題，只有當(dāng)確定了其可用算盤解算它的規(guī)則時(shí)，這個(gè)問題才算可解。這就是古代中國的“算法化”思想。蘊(yùn)涵了計(jì)算的根本問題，即“能行性”問題這對現(xiàn)代計(jì)算學(xué)科的研究具有重要的意義：圖靈機(jī)幾何定理的機(jī)器證明對計(jì)算本質(zhì)的真正認(rèn)識取決于形式化研究的進(jìn)程第二頁，共二十五頁，編輯于2023年，星期日3形式化研究進(jìn)程1275年，思維機(jī)器“旋轉(zhuǎn)玩具”是一種形式化的產(chǎn)物，標(biāo)志著形式化思想革命的開始形式化方法和理論的研究起源于對數(shù)學(xué)的基礎(chǔ)研究?？低袪柕募险摚蔀閿?shù)學(xué)的重要基礎(chǔ)希爾伯特綱領(lǐng)：將每一門數(shù)學(xué)的分支構(gòu)成形式系統(tǒng)或形式理論，并在以此為對象的元理論即元數(shù)學(xué)中，證明每一個(gè)形式系統(tǒng)的相容性，從而導(dǎo)出全部數(shù)學(xué)的相容性希爾伯特綱領(lǐng)的目標(biāo)，其實(shí)質(zhì)就是要尋找通用的形式邏輯系統(tǒng)，該系統(tǒng)應(yīng)當(dāng)是完備的，即在該系統(tǒng)中可以機(jī)械地判定任何給定命題的真?zhèn)纹淠康氖菫榱讼_素悖論：S={x∣x?S}1931年，哥德爾提出的關(guān)于形式系統(tǒng)的“不完備性定理”中指出，這種形式系統(tǒng)是不存在的，從而宣告希爾伯特綱領(lǐng)失敗“不完備性定理”說明，有些數(shù)學(xué)問題是不能用任何機(jī)械過程來解決的，我們應(yīng)把精力集中于解決具有能行性的問題第三頁，共二十五頁，編輯于2023年，星期日4圖靈對計(jì)算本質(zhì)的揭示在哥德爾研究成果的影響下，20世紀(jì)30年代后期，圖靈從計(jì)算一個(gè)數(shù)的一般過程入手對計(jì)算的本質(zhì)進(jìn)行了研究，從而實(shí)現(xiàn)了對計(jì)算本質(zhì)的真正認(rèn)識所謂計(jì)算，就是計(jì)算者（人或機(jī)器）對一條兩端可無限延長的紙帶上的一串0和1執(zhí)行指令，一步一步地改變紙帶上的0或1，經(jīng)過有限步驟，最后得到一個(gè)滿足預(yù)先規(guī)定的符號串的變換過程圖靈的研究成果是：可計(jì)算性=圖靈可計(jì)算性任一過程是能行的（理論上的能行，能夠具體表現(xiàn)在一個(gè)算法中），當(dāng)且僅當(dāng)它能夠被一臺圖靈機(jī)實(shí)現(xiàn)第四頁，共二十五頁，編輯于2023年，星期日52.2圖靈機(jī)計(jì)算模型第五頁，共二十五頁，編輯于2023年，星期日6圖靈機(jī)的特征圖靈機(jī)由一條兩端可無限延長的帶子、一個(gè)讀寫頭以及一組控制讀寫頭工作的命令組成寫在帶子上的符號為一個(gè)有窮字母表：{S0，S1，S2，Sp}一個(gè)給定機(jī)器的程序認(rèn)為是機(jī)器內(nèi)的五元組（qiSjSkRql或qiSjSkLql或qiSjSkNql）形式的指令集qi表示機(jī)器目前所處的狀態(tài)Sj表示機(jī)器從方格中讀入的符號Sk表示機(jī)器用來代替Sj寫入方格中的符號R、L、N分別表示向右移一格、向左移一格、不移動(dòng)ql表示下一步機(jī)器的狀態(tài)第六頁，共二十五頁，編輯于2023年，星期日7圖靈機(jī)的工作原理機(jī)器從給定帶子上的某起始點(diǎn)出發(fā)，根據(jù)其初始狀態(tài)及機(jī)內(nèi)五元組決定其動(dòng)作，經(jīng)過有限步驟機(jī)器停止時(shí)，帶子上的信息即為機(jī)器計(jì)算的結(jié)果?？赡墚a(chǎn)生的問題：無休止工作如：q1S2S2Rq3指令和q3S3S3Lq1指令同時(shí)出現(xiàn)在機(jī)器中時(shí)產(chǎn)生二義性如：q3S2S2Rq4和q3S2S4Lq6指令同時(shí)出現(xiàn)在機(jī)器中時(shí)第七頁，共二十五頁，編輯于2023年，星期日8實(shí)例設(shè)b表示空格，q1表示機(jī)器的初始狀態(tài)，q4表示機(jī)器的結(jié)束狀態(tài)，如果帶子上的輸入信息是10100010，讀入頭對準(zhǔn)最右邊第一個(gè)為0的方格，狀態(tài)為初始狀態(tài)q1。按照以下規(guī)則執(zhí)行之后，輸出正確的計(jì)算結(jié)果。

q101Lq2 q110Lq3 q1bbNq4 q200Lq2 q211Lq2 q2bbNq4 q301Lq2 q310Lq3 q3bbNq4第八頁，共二十五頁，編輯于2023年，星期日9圖靈機(jī)對例子的計(jì)算過程S(x)=x+1第九頁，共二十五頁，編輯于2023年，星期日10現(xiàn)代計(jì)算機(jī)的產(chǎn)生自從圖靈機(jī)思想提出不到10年，世界上第一臺電子計(jì)算機(jī)誕生了圖靈機(jī)反映的是一種計(jì)算模型，而現(xiàn)代計(jì)算機(jī)正是這種模型的具體實(shí)現(xiàn)反映了計(jì)算學(xué)科的抽象、理論和設(shè)計(jì)3個(gè)過程抽象和理論兩個(gè)過程關(guān)心的是解決具有能行性和有效性的模型問題設(shè)計(jì)過程關(guān)心的是模型的具體實(shí)現(xiàn)問題第十頁，共二十五頁，編輯于2023年，星期日11從計(jì)算角度認(rèn)知思維、視覺和生命過程符號主義者認(rèn)為：認(rèn)知是一種符號處理過程，因此思維就是計(jì)算（認(rèn)知就是計(jì)算）有關(guān)視覺認(rèn)知理論的學(xué)者也把視覺看作是一種計(jì)算此外，DNA（脫氧核糖核酸）計(jì)算技術(shù)的可行性，從一個(gè)側(cè)面說明了生命過程也是一種計(jì)算第十一頁，共二十五頁，編輯于2023年，星期日122.3圖靈簡介（1912—1954）第十二頁，共二十五頁，編輯于2023年，星期日13圖靈簡介圖靈1912年6月23日生于倫敦近郊，因父母一度在國外，童年時(shí)缺乏父愛和母愛，自幼起性格和行為很怪癖。13歲入中學(xué)，學(xué)習(xí)成績不是很好，只有數(shù)學(xué)例外，演算能力特別強(qiáng)。此外，擅長賽跑。1931年中學(xué)畢業(yè)后考入劍橋大學(xué)攻讀數(shù)學(xué)，其學(xué)位論文課題是關(guān)于概率論的中心極限定理的，由于對前人工作一無所知，他又重新發(fā)現(xiàn)了該定理。第十三頁，共二十五頁，編輯于2023年，星期日14圖靈簡介1935年，圖靈開始對數(shù)理邏輯發(fā)生興趣。數(shù)理邏輯用數(shù)學(xué)方法，也就是用符號和公式、公理的方法去研究人的思維過程、思維規(guī)律。其起源可追溯到17世紀(jì)德國的大數(shù)學(xué)家萊布尼茨(1646—1716)，其建立目的是一種精確的、普遍的符號語言，并尋求一種推理演算，以便用演算去解決人如何推理的問題。在萊布尼茨的思想中，數(shù)理邏輯、數(shù)學(xué)和計(jì)算機(jī)三者均出于一個(gè)統(tǒng)一目的，即人的思維過程的演算化、計(jì)算機(jī)化，以至在計(jì)算機(jī)上實(shí)現(xiàn)。但萊布尼茨的這些思想和概念還比較模糊。兩個(gè)多世紀(jì)來，許多數(shù)學(xué)家和邏輯學(xué)家沿著萊布尼茨的思路進(jìn)行了大量實(shí)質(zhì)性的工作，使數(shù)理邏輯逐步完善和發(fā)展起來，許多概念開始明朗起來；但是，“計(jì)算機(jī)”到底是怎樣一種機(jī)器，應(yīng)該由哪些部分組成，如何進(jìn)行計(jì)算和工作，在圖靈之前沒有任何人清楚地說明過。第十四頁，共二十五頁，編輯于2023年，星期日15圖靈簡介1936年，發(fā)表了“論可計(jì)算數(shù)及其在判定問題中的應(yīng)用”論文，提出了著名的理論計(jì)算機(jī)模型——圖靈機(jī)。利用這種計(jì)算機(jī)，可以把推理化做一些簡單的機(jī)械動(dòng)作。說來有趣，具有重大科學(xué)價(jià)值和歷史意義的計(jì)算模型，并非圖靈那篇論文的主題。圖靈那篇論文主要是回答德國大數(shù)學(xué)家戴維·希爾伯特(1862—1943)在1900年舉行的世界數(shù)學(xué)家大會上提出的著名的“23個(gè)數(shù)學(xué)難題”中的一個(gè)問題的，這個(gè)問題涉及邏輯的完備性，即是否所有的數(shù)學(xué)問題在原則上都是可解的。圖靈的論文回答了這個(gè)問題：有些數(shù)學(xué)問題是不可解的。而自動(dòng)計(jì)算機(jī)的理論模型則是圖靈在其論文的一個(gè)腳注中“順便”提出來的。這真可謂“歪打正著”——圖靈這篇傳世的論文主要是因?yàn)檫@個(gè)腳注，其正文的意義和重要性反而退居其次了。第十五頁，共二十五頁，編輯于2023年，星期日16圖靈簡介隨后，應(yīng)邀于美國普林斯頓大學(xué)與美國著名數(shù)學(xué)家和邏輯學(xué)家邱奇合作，并于1938年取得博士學(xué)位。在這里，還研究了布爾1854年創(chuàng)建的邏輯代數(shù)，自己動(dòng)手用繼電器搭建邏輯門，組成了乘法器。在美國，還遇到了普林斯頓大學(xué)教師天才科學(xué)家馮·諾伊曼。1938年回到英國劍橋大學(xué)，從事Z函數(shù)的計(jì)算方法研究。第十六頁，共二十五頁，編輯于2023年，星期日17圖靈簡介1939年為“二戰(zhàn)”服務(wù)，主要從事破譯德軍密碼工作。他用繼電器（后改用電子管）做成譯碼機(jī)，破譯了不少密報(bào)，發(fā)現(xiàn)了德軍的動(dòng)向，為盟軍戰(zhàn)勝德國法西斯立了不少功勞。二戰(zhàn)期間，他除了不修邊幅、講話木訥、孤僻等外，最不可思議的是他對英國獲勝?zèng)]有信心，把所有積蓄換成兩條銀條埋了起來，但后來記不起埋在哪兒了。第十七頁，共二十五頁，編輯于2023年，星期日18圖靈簡介二戰(zhàn)后，他去了英國國家家物理實(shí)驗(yàn)室(NationalPhysicalLaboratory，NPL)新建立的”數(shù)學(xué)部”，開始設(shè)計(jì)與建造電子計(jì)算機(jī)ACE(AutomaticComputingEngine)他把自己在計(jì)算模型方面的理論研究成果與戰(zhàn)時(shí)在脈沖技術(shù)和電子學(xué)方面的實(shí)踐經(jīng)驗(yàn)結(jié)合起來，提出了一個(gè)設(shè)計(jì)方案1946年5月以前由于找不到稱心的助手，一直“單槍匹馬”，直到威爾金森（1970年圖靈獎(jiǎng)獲得者）成了圖靈得力助手，此時(shí)ACE已到第5版，前4版由于圖靈不善于也不重視保管文檔資料而不知去向。ACE是一種存儲程序式計(jì)算機(jī)，但其存儲程序思想并非受馮·諾伊曼論文的影響，而是他自己的構(gòu)思。馮·諾伊曼本人也從來沒有說過存儲程序的概念是他的發(fā)明，卻不止一次地說過圖靈是現(xiàn)代計(jì)算機(jī)設(shè)計(jì)思想的創(chuàng)始人。但由于上級管理不善，圖靈于1948年離開了NPL，此時(shí)ACE已到第8版，而后由威爾金森接手負(fù)責(zé)ACE項(xiàng)目，并于1950年5月完成了ACE樣機(jī)（按ACE第5版實(shí)現(xiàn)），使英國計(jì)算機(jī)水平與美國平起平坐。第十八頁，共二十五頁，編輯于2023年，星期日19圖靈簡介1948年，圖靈到曼切斯特大學(xué)新成立的皇家學(xué)會計(jì)算實(shí)驗(yàn)室當(dāng)副主任。曼切斯特大學(xué)在計(jì)算機(jī)發(fā)展史上曾起過重大作用，1948年6月開發(fā)出了世界第一臺存儲程序式計(jì)算機(jī)MARKI（現(xiàn)在一般說法是英國劍橋大學(xué)威爾克斯設(shè)計(jì)和完成于1949午5月的EDSAC，實(shí)際上，最早開始設(shè)計(jì)與實(shí)施存儲程序式計(jì)算機(jī)的是EDVAC，于1952年完成）1950年10月發(fā)表了論文“計(jì)算機(jī)和智能”，進(jìn)一步闡明了他認(rèn)為計(jì)算機(jī)可以有智能的思想，并提出了測試機(jī)器是否有智能的方法，大家現(xiàn)在稱之為“圖靈測試”。第十九頁，共二十五頁，編輯于2023年，星期日20圖靈簡介在曼徹斯特大學(xué)期間，圖靈發(fā)表的論文中還包括對黎曼(1826—1866)Z函數(shù)的進(jìn)一步研究成果，這是他戰(zhàn)前曾經(jīng)感興趣而研究過的一個(gè)課題。這個(gè)時(shí)期，他對生物學(xué)和化學(xué)也產(chǎn)生了興趣，曾經(jīng)發(fā)表有關(guān)器官形成的化學(xué)基礎(chǔ)的論文，探討海星為什么呈五軸對稱，原腸胚在特定的點(diǎn)上形成溝槽等現(xiàn)象。這使他被公認(rèn)為是生物學(xué)中研究器官形態(tài)領(lǐng)域的先驅(qū)，也是遠(yuǎn)離平衡態(tài)化學(xué)的奠基人。由于圖靈的一系列杰出貢獻(xiàn)和重大創(chuàng)造，1951年他被選為英國皇家學(xué)會院士。第二十頁，共二十五頁，編輯于2023年，星期日21圖靈簡介1952年因同性戀被法院傳訊，指控行為“極端不當(dāng)”(grossindecency)，給予一年監(jiān)外察看，并給予藥物治療。兩年以后，1954年6月7日，距他42周歲生日不到兩個(gè)星期，因吃了在氰化物溶液中浸泡過的蘋果而在家中死去。后人為紀(jì)念這位”計(jì)算機(jī)科學(xué)之父”，在英國曼徹斯特的Sackville公園塑了真人大的青銅坐像；ACM于1966了設(shè)立了第一個(gè)獎(jiǎng)項(xiàng)——圖靈獎(jiǎng)，以推動(dòng)計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展和學(xué)術(shù)交流。第二十一頁，共二十五頁，編輯于2023年，星期日22圖靈塑像第二十二頁，共二十五頁，編輯于2023年，星期日23討論結(jié)合圖靈一生的事跡，討論：１、家庭教育的作用。２、計(jì)算機(jī)科學(xué)家應(yīng)具備的基本素質(zhì)。３、人才管理方式。４、同性戀。第二十三頁，共二十五頁，編輯于2023年，星期日24思考題計(jì)算題：在圖靈的帶子機(jī)中，設(shè)b表示空格，q1表示機(jī)器的初始