計算引論結(jié)課論文

1、 計算引論結(jié)課論文圖靈機綜述作者:12061193 徐鈞鴻2014年 6月摘要圖靈機作為計算機領(lǐng)域中的重要組成部分, 值得深入的研究與發(fā)展。 本文從圖靈機的產(chǎn)生背 景、基本結(jié)構(gòu)、用途與發(fā)展幾個方面,簡單闡述了圖靈機的基本內(nèi)容與重要性。目錄摘要 . 1一、提出背景 . . 4二、模型論述 . . 41、基本思想 . . 42、圖靈機的定義 . . 5三、圖靈機的用途 . . 5 2 圖靈機的用途 . . 5四、相關(guān)發(fā)展 . . 61、在云環(huán)境下基于多軌道圖靈機的服務(wù)部署 . 62、基于量子邏輯的圖靈機 . . 7五、結(jié)論 . 7一、提出背景圖靈機的提相互有兩個背景事件, 首先就是第三次數(shù)學危機。

2、 這次危機是由于在康托的 一般集合理論的邊緣發(fā)現(xiàn)悖論造成的。 由于集合概念已經(jīng)滲透到眾多的數(shù)學分支, 并且實際 上集合論成了數(shù)學的基礎(chǔ), 因此集合論中悖論的發(fā)現(xiàn)自然地引起了對數(shù)學的整個基本結(jié)構(gòu)的 有效性的懷疑。 第二個是希爾伯特綱領(lǐng):為各門數(shù)學學科建立形式化的公理系統(tǒng), 它包含有 限條概念與公理, 整個學科建立在這個公理系統(tǒng)之上, 從而將數(shù)學理論的相容性問題轉(zhuǎn)化為 論證公理系統(tǒng)的相容性問題。 之后的哥德爾不完全性定理和希爾伯特判定問題, 提出了一個 問題,就是:是否存在一個算法,能判定一個算術(shù)命題是否為真。為了解決這個問題,英國的數(shù)學家圖靈 (Alan M. Turing, 1912-1954

3、在 1936年的論文中 給“算法” 這個概念提出了一個數(shù)學定義。這是一種模擬人的計算動作的計算模型,人們稱 為“圖靈機” 。 圖靈證明算術(shù)命題的真值是不能用圖靈機判定的。二、模型論述1、基本思想圖靈的基本思想是用機器來模擬人們用紙筆進行 數(shù)學 運算的過程, 他把這樣的過程看作 下列兩種簡單的動作:在紙上寫上或擦除某個符號;把注意力從紙的一個位置移動到另一個位置;而在每個階段,人要決定下一步的動作,依賴于(a 此人當前所關(guān)注的紙上某個位置 的符號和(b 此人當前思維的狀態(tài)。為了模擬人的這種運算過程,圖靈構(gòu)造出一臺假想的 機器,該機器由以下幾個部分組成:一條無限長的紙帶 TAPE 。 紙帶被劃分為

4、一個接一個的小格子, 每個格子上包含一個來 自有限字母表的符號,字母表中有一個特殊的符號 表示空白。紙帶上的格子從左到右依 次被編號為 0, 1, 2, .,紙帶的右端可以無限伸展。一個讀寫頭 HEAD 。該讀寫頭可以在紙帶上左右移動,它能讀出當前所指的格子上的 符號,并能改變當前格子上的符號。一套控制規(guī)則 TABLE 。它根據(jù)當前機器所處的狀態(tài)以及當前讀寫頭所指的格子上的符 號來確定讀寫頭下一步的動作,并改變狀態(tài)寄存器的值,令機器進入一個新的狀態(tài)。 一個 狀態(tài)寄存器 。 它用來保存圖靈機當前所處的狀態(tài)。 圖靈機的所有可能狀態(tài)的數(shù)目是 有限的,并且有一個特殊的狀態(tài),稱為 停機狀態(tài) 。參見 停機

5、問題 。注意這個機器的每一部分都是有限的, 但它有一個潛在的無限長的紙帶, 因此這種機器 只是一個理想的設(shè)備。圖靈認為這樣的一臺機器就能模擬人類所能進行的任何計算過程。2、圖靈機的定義 一臺圖靈機是一個七元組 限集合，且滿足 是狀態(tài)集合； 是輸入字母表，其中不包含特殊的空白符 為空白符； 是帶字母表，其中 且 ； 是轉(zhuǎn)移函數(shù)，其中 還是向右移； 是起始狀態(tài)； 是接受狀態(tài)。 圖靈機 開始的時候?qū)⑤斎敕柎?第 是拒絕狀態(tài)，且 將以如下方式運作： 從左到右依此填在紙帶的 ）。 的讀寫頭 。 表示讀寫頭是向左移 ； ， 其中 都是有 號格子上， 其他格子保持空白（即填以空白符 指向第 0 號格子，

6、處于狀態(tài) 。 機器開始運行后，按照轉(zhuǎn)移函數(shù) 所描述的規(guī)則進行 計算。 例如，若當前機器的狀態(tài)為 ，讀寫頭所指的格子中的符號為 ， 設(shè) ， 則機器進入新狀態(tài) ， 將讀寫頭所指的格子中的符號改為 ， 然后將讀寫頭向左移動一個格子。 若在某一時刻，讀寫頭所指的是第 0 號格子， 但根據(jù) 轉(zhuǎn)移函數(shù)它下一步將繼續(xù)向左移，這時它停在原地不動。 換句話說，讀寫頭始終不移出紙 帶的左邊界。 若在某個時刻 根據(jù)轉(zhuǎn)移函數(shù)進入了狀態(tài) ， 則它立刻停機并接受 輸入的字符串； 若在某個時刻 根據(jù)轉(zhuǎn)移函數(shù)進入了狀態(tài) ， 則它立刻停機并拒 絕輸入的字符串。 三、圖靈機的用途 2 圖靈機的用途 作為研究計算的一般性質(zhì)的抽象工

7、具, 圖靈機主要有 3 種用途: 5 2.1 作為語言接受器 被 M 接受的語言記作 L(M, 它是 中的這樣一些字符串的集合, 當把這些字符串 放在 M 的帶子上, M 處于 q0 狀態(tài)且 M 的帶頭處在最左單元時, 這些字符串可以使 M 進 入一個終結(jié)狀態(tài)而停機。 給定一個識別語言 L 的圖靈機 M, 一般假定, 當輸入被接受時, M 為停機, 即沒有下一動作。然而對于不被接受的字符串, M 可能永不停機。被圖靈機接受的 語言稱為遞歸可枚舉語言。遞歸集合是遞歸可枚舉集合的子類, 遞歸集合總能被對所有輸入 都能 停機的圖靈機所接受。 2.2 作為整數(shù)函數(shù)計算機 被圖靈機計算的函數(shù)稱為部分遞歸

8、函數(shù)。在某種意義上, 部分遞歸函數(shù)類似于遞歸可枚 舉語言, 因為計算它的圖靈機在給定的輸入上可能不停機。完全遞歸函數(shù)對應(yīng)于遞歸語言 , 因為它能被總能停機的圖靈機計算。 2.3 作為語言產(chǎn)生器 設(shè) M 是一個多帶圖靈機, 它用一條帶作為輸出帶, 在這條帶上, 符號一經(jīng)寫上就不能 再改寫, 輸出帶的帶頭也不能左移。 假定在輸出帶上, M 寫出某個字母表 上的一些字符串, 并用分隔符分開 , 則最終打印在輸出帶上的字符串的集合就稱為由 M 生成的語言, 記為 G(M, G(M! 。如果 L 是某個圖靈機生成的語言, 則 L 是遞歸可枚舉集合, 反之亦然。 我們現(xiàn)在對圖靈機的研究主要集中在兩個方面:

9、 第一, 研究圖靈機所定義的語言類, 該 語言類稱為遞歸可枚舉集合; 第二, 研究圖靈機所計算的函數(shù)類, 該函數(shù)類稱為部分遞歸函 數(shù)。 作為有效過程或算法的形式模型, 圖靈機的每個動作過程都應(yīng)該是有窮可描述的。 而且, i 每個過程應(yīng)該由離散的步驟組成, 每一步都能夠機械地實現(xiàn)。 四、相關(guān)發(fā)展 1、在云環(huán)境下基于多軌道圖靈機的服務(wù)部署 云計算可以把企業(yè)提供的服務(wù)通過網(wǎng)絡(luò)提供給用戶。因為現(xiàn)有的云架構(gòu)缺乏云服務(wù)組 合和部署的中間件層， 所以本文提出基于軌道圖靈機的云服務(wù)部署模型。 這個云服務(wù)部 署模型使按需云服務(wù)部署更加方便和快速， 并實現(xiàn)了一個基于云計算的中間件動態(tài)服務(wù)部署 （CMCD）原型。

10、云服務(wù)部署模型包括云服務(wù)搜索引擎模塊、 云服務(wù)組合模塊和圖靈機構(gòu)造模塊。 云服務(wù) 搜索引擎模塊是一個支持匹配算法多標準的云服務(wù)的搜索引擎。它能夠搜索滿足以下 3 方 面要求的云服務(wù)： （1）功能要求， （2）技術(shù)要求， （3）費用要求，為了進一步提高搜索結(jié)果 的準確性，我們設(shè)計了一個云本體。云本體包含了一組云的概念，和這些概念的個體以及這 6 些個體之間的關(guān)系。 云本體是用于確定相似云服務(wù)的依據(jù)， 基于云本體的相似云服務(wù)推理方 法包括三種（1）概念相似度推理（2）對象屬性相似的推理（3）數(shù)據(jù)類型的屬性相似推理。 在現(xiàn)實中， 云本體論有效的解決了我們?nèi)绾味攘吭品?wù)提供商提供的云服務(wù)之間的關(guān)系即相

11、 似度的難題。在云服務(wù)的組合上，我們使用有限狀態(tài)機（FSM）規(guī)定其調(diào)用序列，并且基于 一種改進的修剪算法來創(chuàng)建云服務(wù)組合樹。 在其云服務(wù)組合樹中可以找出所有的可執(zhí)行的路 徑，然后用一個簡單的加權(quán)技術(shù)用于選擇最佳的路徑即所要部署的云服務(wù)。 圖靈機構(gòu)造模塊主要是從云服務(wù)提供商宏觀層面進一步對云服務(wù)的部署進行控制。 CMCD 說明了動態(tài)云服務(wù)的部署可行性。CMCD 中間件使用圖靈機的數(shù)學模型，實現(xiàn)動態(tài) 云服務(wù)部署。實驗說明基于圖靈機的云服務(wù)部署算法在普通云服務(wù)功能方面有較好的性能， 并且部署成功率非常高。ii 2、基于量子邏輯的圖靈機 基于量子邏輯的自動機理論是量子計算模型的一個重要研究方向。 該項

12、研究基于量子邏 輯的圖靈機(簡稱量子圖靈機及其一些變形， 給出了包括非確定型量子圖靈機 l-VTM,確定型 量子圖靈機 l-VDTM 以及相應(yīng)類型的多帶量子圖靈機，并引入量子圖靈機基于深度優(yōu)先與 寬度優(yōu)先識別語言的兩種不同定義方式， 證明了這兩種定義方式在量子邏輯意義下是不等價 的，進一步證明了 l-VTM、l-VDTM 與相應(yīng)類型的多帶量子圖靈機之間的等價性。其次，給 出了量子遞歸可枚舉語言及量子遞歸語言的定義,，并給出了二者的層次刻畫,證明了 l-VTM 與 l-VDTM 不等價，但兩者作為量子遞歸語言的識別器是等價的。并且討論了基于量子邏 輯的通用圖靈機的存在性問題， 給出了一套合理編碼系統(tǒng)， 證明了基于量子邏輯的通用圖靈 機在其所取值的正交模格無限時不存在，而在其所取值的正交模格有限時是存在的。iii 五、結(jié)論 圖靈機作為現(xiàn)代計算機的鼻祖， 給現(xiàn)代計算機提供了原始模型與計算方法。 圖靈機在理 論上能夠模