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

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

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