圖靈機

來自 搜狐網 的圖片

圖靈機是中國科技名詞。

世界三大漢語詞典分別是中國大陸的《 漢語大詞典》(共13冊，5.6萬詞條，37萬單詞)、中國台灣的《 中文大辭典 》(共10冊，5萬詞條，40萬單詞)以及日本的《 大漢和辭典 》(共13冊，4.9萬詞條，40萬單詞)。漢字是記錄漢語的文字，它已有六千年左右的歷史，是世界上最古老的文字之一。

目錄

名詞解釋

圖靈機，又稱圖靈計算機，是一個抽象的機器。它由英國數學家艾倫・麥席森・圖靈(1912―-1954年)於1936年提出的一種抽象的計算模型，即將人們使用紙筆進行數學運算的過程進行抽象，由一個虛擬的機器替代人類進行數學運算。 圖靈機有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個讀寫頭在紙帶上移來移去。讀寫頭有一組內部狀態，還有一些固定的程序。在每個時刻，讀寫頭都要從當前紙帶上讀入一個方格信息，然後結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，並轉換自己的內部狀態，然後進行移動。

工作原理

一台圖靈機是一個七元組，{Q，Σ，Γ，δ，q0，qaccept，qreject}，其中 Q，Σ，Γ 都是有限集合，且滿足：

1、Q 是狀態集合；

2、Σ 是輸入字母表，其中不包含特殊的空白符；

3、Γ 是帶字母表，其中 Q∈Γ且Σ∈Γ ；

4、 δ：Q×Γ→Q×Γ×{L，R}是轉移函數，其中L，R 表示讀寫頭是向左移還是向右移；

5、q0∈Q是起始狀態；

6、 qaccept是接受狀態。

7、qreject是拒絕狀態，且qreject≠qaccept。

圖靈機 M = (Q，Σ，Γ，δ，q0，qaccept，qreject) 將以如下方式運作：

開始的時候將輸入符號串從左到右依次填在紙帶的格子上， 其他格子保持空白（即填以空白符）。M 的讀寫頭指向第 0 號格子， M 處於狀態 q0。機器開始運行後，按照轉移函數 δ 所描述的規則進行計算。例如，若當前機器的狀態為 q，讀寫頭所指的格子中的符號為 x，設 δ（q，x）= （q'，x'，L），則機器進入新狀態 q'，將讀寫頭所指的格子中的符號改為 x'，然後將讀寫頭向左移動一個格子。若在某一時刻，讀寫頭所指的是第 0 號格子，但根據轉移函數它下一步將繼續向左移，這時它停在原地不動。換句話說，讀寫頭始終不移出紙帶的左邊界。若在某個時刻 M 根據轉移函數進入了狀態 qaccept， 則它立刻停機並接受輸入的字符串； 若在某個時刻 M 根據轉移函數進入了狀態 qreject， 則它立刻停機並拒絕輸入的字符串。

注意，轉移函數 δ 是一個部分函數， 換句話說對於某些 q，x， δ（q，x）可能沒有定義， 如果在運行中遇到下一個操作沒有定義的情況， 機器將立刻停機。

通用圖靈機

對於任意一個圖靈機，因為它的描述是有限的，因此我們總可以用某種方式將其編碼為字符串。我們用 表示圖靈機 M 的編碼。

我們可以構造出一個特殊的圖靈機，它接受任意一個圖靈機 M 的編碼 ，然後模擬 M 的運作，這樣的圖靈機稱為通用圖靈機(Universal Turing Machine)。現代電子計算機其實就是這樣一種通用圖靈機的模擬，它能接受一段描述其他圖靈機的程序，並運行程序實現該程序所描述的算法。但要注意，它只是模擬，因為現實中的計算機的存儲都是有限的，所以無法跨越有限狀態機的界限。經典圖靈機及其許多變形識別語言的能力都是相同的，正因為如此，圖靈機可以作為計算的一般模型。另外，通用圖靈機 (可編程圖靈機) 是存在的，通用圖靈機可以模擬任意一個圖靈機，這也是將圖靈機作為現代計算機的形式模型的根本原因。

停機問題

停機問題(halting problem)是邏輯數學的焦點，是第三次數學危機的解決方案。其本質問題是：給定一個圖靈機和一個任意語言集合S，是否會最終停機於每一個s∈S。其意義類似於可確定語言。顯然任意有限S是可判定性的，可數的(countable)S也是可停機的。

通俗地說，停機問題就是判斷任意一個程序是否會在有限的時間之內結束運行的問題。如果這個問題可以在有限的時間之內解決，則可以有一個程序判斷其本身是否會停機並做出相反的行為。這時候顯然不管停機問題的結果是什麼都不會符合要求，所以這是一個不可解的問題。

停機問題的本質是一階邏輯的不自恰性和不完備性。類似的命題有理髮師悖論、全能悖論等。

圖靈機的變體

圖靈機有很多變體，但可以證明這些變體的計算能力都是等價的，即它們識別同樣的語言類。證明兩個計算模型A和B的計算能力等價的基本思想是：用A和B相互模擬，若A可模擬B且B可模擬A，則它們的計算能力等價。注意這裡我們暫時不考慮計算的效率，只考慮計算的理論「可行性」。

改變圖靈機的帶字母表並不會改變其計算能力。例如我們可以限制圖靈機的帶字母表為（0，1），這並不會改變圖靈機的計算能力，因為我們可以用帶字母表為（0，1）的圖靈機模擬帶字母表為任意有限集合廠的圖靈機。

另一個要注意的是，如果我們允許圖靈機的紙帶兩端都可以無限伸展，這並不能增加圖靈機的計算能力，因為我們可以用只有紙帶一端能無限伸展的圖靈機來模擬這種紙帶兩端都可以無限伸展的圖靈機。

如果我們允許圖靈機的讀寫頭在某一步保持原地不動，那也不會增加其計算能力，因為我們可以用向左移動一次再向右移動一次來代替原地不動。

其他的常見圖靈機變種包括多帶圖靈機、非確定型圖靈機、交替式圖靈機、枚舉器。

意義

圖靈提出圖靈機的模型並不是為了同時給出計算機的設計，它的意義有如下幾點:

(1)它證明了通用計算理論，肯定了計算機實現的可能性，同時它給出了計算機應有的主要架構；

(2)圖靈機模型引入了讀寫、算法與程序語言的概念，極大的突破了過去的計算機器的設計理念；

(3)圖靈機模型理論是計算學科最核心的理論，因為計算機的極限計算能力就是通用圖靈機的計算能力，很多問題可以轉化到圖靈機這個簡單的模型來考慮。

通用圖靈機向人們展示這樣一個過程:程序和其輸入可以先保存到存儲帶上，圖靈機就按程序一步一步運行直到給出結果，結果也保存在存儲帶上。更重要的是，隱約可以看到現代計算機主要構成，尤其是馮・諾依曼理論的主要構成。