




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
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)代計算機提供了原始模型與計算方法。 圖靈機在理 論上能夠模
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 標準醫(yī)學病例匯報
- 香港公司出資協(xié)議書
- 路面問題賠償協(xié)議書
- 遺產(chǎn)自愿放棄協(xié)議書
- 金店夜班合同協(xié)議書
- 農(nóng)機合伙人合同協(xié)議書
- 飯店入伙合同協(xié)議書
- 轉(zhuǎn)讓壽司餐廳協(xié)議書
- 飯?zhí)糜啿秃贤瑓f(xié)議書
- 集體產(chǎn)權(quán)私下協(xié)議書
- 2025-2030年中國威士忌酒行業(yè)運行動態(tài)及前景趨勢預(yù)測報告
- 小學生記憶小竅門課件
- 婚姻家庭與法律知到智慧樹章節(jié)測試課后答案2024年秋延邊大學
- 物業(yè)管理安全責任分配
- 《傷寒論》課件-少陽病提綱、小柴胡湯證
- 中國鐵路沈陽局集團有限公司招聘筆試沖刺題2025
- 2024年度醫(yī)療設(shè)備報廢回收與資源化利用合同3篇
- 2024商鋪租賃合同解除補償承諾書11篇
- 科室病歷質(zhì)量管理培訓記錄
- 新興行業(yè)審計風險分析-洞察分析
- 《口腔頜面醫(yī)學影像診斷學》考試復(fù)習題庫(含答案)
評論
0/150
提交評論