計算機科學(xué)的本史元春(編輯修改稿)
2025-06-08 22:19 本頁面
【文章內(nèi)容簡介】 可計算的 ? Turing回答了可計算性問題：哪些問題類是可以用計算機解決的，計算機的通用計算能力問題，并給出了理論計算模型 ——圖靈機和它的輸入數(shù)據(jù)、計算程序和輸出結(jié)果的表示方式 ? 圖靈機由一條雙向都可以無限延長的、被分成一個個小方格的磁帶；一個有限狀態(tài)控制器；一個讀寫磁頭 3部分組成 Turing Machine 圖靈機一步一步地進行工作，其工作情況取決于三個條件： ? 有限狀態(tài)控制器內(nèi)部狀態(tài) ? 讀寫磁頭掃描在磁帶的哪個方格上 ? 該方格上有什么信息 每一步工作的過程： ? 讀 “ 讀寫磁頭 ” 當(dāng)前所掃描的磁帶方格的存儲內(nèi)容 si ? 根據(jù) si的值以及 “ 有限狀態(tài)控制器 ” 當(dāng)前內(nèi)部狀態(tài) qi， ? 決定在當(dāng)前方格寫入新的內(nèi)容 s’i ? 并決定 “ 讀寫磁頭 ” 由當(dāng)前位置 或左移 (一格 )、或右移 (一格 )、或不移動、或停機 ? 并決定 “ 有限控狀態(tài)制器 ” 新的控制狀態(tài) q i+1 ? 進入下一步工作，按同樣的方式工作；如此周而復(fù)始，直到遇到命令機器停機。 Turing Machine Fundamentals 1 0 1 1 0 q1 q2 q3 q4 q5 q6 q7 0 0 1 1 0 q1 q2 q3 q4 q5 q6 q7 當(dāng)控制器前處于狀態(tài) q2， 磁頭所指的磁帶方格內(nèi)容為 1，現(xiàn)在要采取得動作是：將該磁帶方格的內(nèi)容改寫為 0，磁頭向右移動一格，控制器內(nèi)狀態(tài)變?yōu)?q5 Example Turing Machine 圖靈機的這種由狀態(tài)、符號確定的工作過程叫做圖靈機程序，可以由一個五元組序列來定義： q, b, a, m, q’ ? q： 當(dāng)前狀態(tài) ? b： 當(dāng)前方格中的符號 ? a： 當(dāng)前方格中修改后的符號 ? m： 磁頭移動的方向，左移 L（ Left）、 右移 R（ Right）， 不動 N（ Nomotion） ? q’： 下一狀態(tài) Turing Machine 前面例子中，圖靈機的一步動作可表示為： q2, 1, 0, R, q5 A Turing machine for incrementing a value 圖靈機計算實例 —— f(x) = 2x 在二進制圖靈機上計算函數(shù) f(x) = 2x，即 x， f(x)都用二進制表示，磁帶方格中只能用 0和 1兩個符號， B表示空白。 約定： 開始時，磁帶上只有一連續(xù)的方格串上放入 x的相應(yīng)的二進制值符號，其余方格都為空白。 機器從狀態(tài) q1開始，磁頭指向 x最左一位所在地方格。 停機時，磁帶上非空方格串所組成的二進制值即代表 f(x)。 在前面的約定下，計算 f(x) = 2x的圖靈機程序如下，其中： Halt表示停機， Error表示在計算中不會出現(xiàn) 當(dāng)前狀態(tài) B被掃描時的寫、移動、狀態(tài)轉(zhuǎn)移 0被掃描時的寫、移動、狀態(tài)轉(zhuǎn)移 1被掃描時的寫、移動、狀態(tài)轉(zhuǎn)移 q1 1， L， q7 0， R， q1 1， R， q2 q2 B， R， q3 0， R， q2 1， R， q2 q3 0， L， q4 0， R， q3 Error q4 B， L， q5 0， L， q4 Error q5 Error 1， L， q5 0， L， q6 q6 B， R， q1 0， L， q6 1， L， q6 q7 Halt B， L， q7 Error 圖靈機計算實例 —— f(x) = 2x ? 為什么以 x的二進制數(shù)為符號作為磁帶初始值 ? ? 為什么停機后磁帶上的二進制值就是最終結(jié)果 ? ? 為什么有 7種狀態(tài) ? ? 為什么在每種狀態(tài)中要進行這些動作 ? 圖靈機程序設(shè)計 圖靈機計算實例 —— f(x) = 2x 1 0 q1 q2 q3 q4 q5 q6 q7 1 0 q1 q2 q3 q4 q5 q6 q7 1 0 q1 q2 q3 q4 q5 q6 q7 開始 第 1步 第 2步 圖靈機計算實例 —— f(x) = 2x 1 0 q1 q2 q3 q4 q5 q6 q7 1 0 0 q1 q2 q3 q4 q5 q6 q7 1 0 0 q1 q2 q3 q4 q5 q6 q7 第 5步 第 4步 第 3步 圖靈機計算實例 —— f(x) = 2x 0 1 0 q1 q2 q3 q4 q5 q6 q7 q1 q2 q3 q4 q5 q6 q7 q1 q2 q3 q4 q5 q6 q7 1 1 0 0 1 0 第 8步 第 7步 第 6步 圖靈機計算實例 —— f(x) = 2x 0 1 0 q1 q2 q3 q4 q5 q6 q7 0 1 0 q1 q2 q3 q4 q5 q6 q7 0 1 0 q1 q2 q3 q4 q5 q6 q7 第 11步 第 10步 第 9步 圖靈機計算實例 —— f(x) = 2x 0 1 0 q1 q2 q3 q4 q5 q6 q7 0 1 0 0
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1