所謂的圖靈機(jī)就是指一個(gè)抽象的機(jī)器，它有一條無限長的紙帶，紙帶分成了一個(gè)一個(gè)的小方格，每個(gè)方格有不同的顏色。有一個(gè)機(jī)器頭在紙帶上移來移去。機(jī)器頭有一組內(nèi)部狀態(tài)，還有一些固定的程序。在每個(gè)時(shí)刻，機(jī)器頭都要從當(dāng)前紙帶上讀入一個(gè)方格信息，然后結(jié)合自己的內(nèi)部狀態(tài)查找程序表，根據(jù)程序輸出信息到紙帶方格上，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)，然后進(jìn)行移動(dòng)。

發(fā)明者

1936年，阿蘭·圖靈提出了一種抽象的計(jì)算模型 —— 圖靈機(jī) (Turing Machine)。

圖靈的基本思想

圖靈的基本思想是用機(jī)器來模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過程，他把這樣的過程看作下列兩種簡單的動(dòng)作：

在紙上寫上或擦除某個(gè)符號;

把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置;

而在每個(gè)階段，人要決定下一步的動(dòng)作，依賴于 (a) 此人當(dāng)前所關(guān)注的紙上某個(gè)位置的符號和(b) 此人當(dāng)前思維的狀態(tài)。

為了模擬人的這種運(yùn)算過程，圖靈構(gòu)造出一臺假想的機(jī)器，該機(jī)器由以下幾個(gè)部分組成：

1.一條無限長的紙帶 TAPE。紙帶被劃分為一個(gè)接一個(gè)的小格子，每個(gè)格子上包含一個(gè)來自有限字母表的符號，字母表中有一個(gè)特殊的符號 表示空白。紙帶上的格子從左到右依此被編號為 0, 1, 2, ... ，紙帶的右端可以無限伸展。

2.一個(gè)讀寫頭 HEAD。該讀寫頭可以在紙帶上左右移動(dòng)，它能讀出當(dāng)前所指的格子上的符號，并能改變當(dāng)前格子上的符號。

3.一套控制規(guī)則 TABLE。它根據(jù)當(dāng)前機(jī)器所處的狀態(tài)以及當(dāng)前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動(dòng)作，并改變狀態(tài)寄存器的值，令機(jī)器進(jìn)入一個(gè)新的狀態(tài)。

4.一個(gè)狀態(tài)寄存器。它用來保存圖靈機(jī)當(dāng)前所處的狀態(tài)。圖靈機(jī)的所有可能狀態(tài)的數(shù)目是有限的，并且有一個(gè)特殊的狀態(tài)，稱為停機(jī)狀態(tài)。參見停機(jī)問題。

注意這個(gè)機(jī)器的每一部分都是有限的，但它有一個(gè)潛在的無限長的紙帶，因此這種機(jī)器只是一個(gè)理想的設(shè)備。圖靈認(rèn)為這樣的一臺機(jī)器就能模擬人類所能進(jìn)行的任何計(jì)算過程。

在某些模型中，紙帶移動(dòng)，而未用到的紙帶真正是“空白”的。要進(jìn)行的指令(q4)展示在掃描到方格之上(由 Kleene (1952) p.375 繪制)。

在某些模型中，讀寫頭沿著固定的紙帶移動(dòng)。要進(jìn)行的指令(q1)展示在讀寫頭內(nèi)。在這種模型中“空白”的紙帶是全部為 0 的。有陰影的方格，包括讀寫頭掃描到的空白，標(biāo)記了 1,1,B 的那些方格，和讀寫頭符號，構(gòu)成了系統(tǒng)狀態(tài)。(由 Minsky (1967) p.121 繪制)。

圖靈機(jī)的形式化定義

一臺圖靈機(jī)是一個(gè)七元組 (Q,Σ,Γ,δ,q0,qaccept,qreject)，其中 Q,Σ,Γ 都是有限集合，且滿足

1.Q 是狀態(tài)集合;

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

3.Γ 是帶字母表，其中 □∈Γ且Σ∈Γ ;

4. δ:Q×「→Q×?！羬L,R}是轉(zhuǎn)移函數(shù)，其中L,R 表示讀寫頭是向左移還是向右移;

5.q0∈Q是起始狀態(tài);

6. qaccept是接受狀態(tài)。

7.qreject是拒絕狀態(tài)，且 。 qreject≠qaccept

圖靈機(jī) M = (Q,Σ,Γ,δ,q0,qaccept,qreject) 將以如下方式運(yùn)作：

開始的時(shí)候?qū)⑤斎敕柎?從左到右依此填在紙帶的第 號格子上， 其他格子保持空白(即填以空白符)。 M 的讀寫頭指向第 0 號格子， M 處于狀態(tài) q0。 機(jī)器開始運(yùn)行后，按照轉(zhuǎn)移函數(shù) δ 所描述的規(guī)則進(jìn)行計(jì)算。 例如，若當(dāng)前機(jī)器的狀態(tài)為 q，讀寫頭所指的格子中的符號為 x， 設(shè) δ(q,x) = (q',x',L)， 則機(jī)器進(jìn)入新狀態(tài) q'， 將讀寫頭所指的格子中的符號改為 x'， 然后將讀寫頭向左移動(dòng)一個(gè)格子。 若在某一時(shí)刻，讀寫頭所指的是第 0 號格子， 但根據(jù)轉(zhuǎn)移函數(shù)它下一步將繼續(xù)向左移，這時(shí)它停在原地不動(dòng)。 換句話說，讀寫頭始終不移出紙帶的左邊界。 若在某個(gè)時(shí)刻 M 根據(jù)轉(zhuǎn)移函數(shù)進(jìn)入了狀態(tài) qaccept， 則它立刻停機(jī)并接受輸入的字符串; 若在某個(gè)時(shí)刻 M 根據(jù)轉(zhuǎn)移函數(shù)進(jìn)入了狀態(tài) qreject， 則它立刻停機(jī)并拒絕輸入的字符串。

注意，轉(zhuǎn)移函數(shù) δ 是一個(gè)部分函數(shù)， 換句話說對于某些 q,x， δ(q,x) 可能沒有定義， 如果在運(yùn)行中遇到下一個(gè)操作沒有定義的情況， 機(jī)器將立刻停機(jī)。

停機(jī)問題

停機(jī)問題(halting problem)是目前邏輯數(shù)學(xué)的焦點(diǎn)，和第三次數(shù)學(xué)危機(jī)的解決方案。其本質(zhì)問題是: 給定一個(gè)圖靈機(jī) T，和一個(gè)任意語言集合 S, 是否 T 會(huì)最終停機(jī)于每一個(gè)。其意義相同于可確定語言。顯然任意有限 S 是可判定性的，可數(shù)的(countable) S 也是可停機(jī)的，在使用 oracle 輸入的幫助下。

通俗的說，停機(jī)問題就是判斷任意一個(gè)程序是否會(huì)在有限的時(shí)間之內(nèi)結(jié)束運(yùn)行的問題。如果這個(gè)問題可以在有限的時(shí)間之內(nèi)解決，可以有一個(gè)程序判斷其本身是否會(huì)停機(jī)并做出相反的行為。這時(shí)候顯然不管停機(jī)問題的結(jié)果是什么都不會(huì)符合要求。所以這是一個(gè)不可解的問題。

停機(jī)問題本質(zhì)是一階邏輯的不自恰性和不完備性。類似的命題有理發(fā)師悖論、全能悖論等。

證明:

設(shè)停機(jī)問題有解，即：存在過程H(P, I)可以給出程序P在輸入I的情況下是否可停機(jī)。假設(shè)若P在輸入I時(shí)可停機(jī)，H輸出“停機(jī)”，反之輸出“死循環(huán)”，即可導(dǎo)出矛盾：

顯然，程序本身可以被視作數(shù)據(jù)，因此它可以被作為輸入，故H應(yīng)該可以判定當(dāng)將P作為P的輸入時(shí)，P是否會(huì)停機(jī)。所以我們設(shè)過程K(P)的流程如下：首先，它調(diào)用H(P, P)，如果H(P, P)輸出“死循環(huán)”，則K(P)停機(jī)，反之K(P)死循環(huán)。即K(P)做與H(P, P)的輸出相反的動(dòng)作。

現(xiàn)在假設(shè)求K(K)，則若H(K, K)輸出停機(jī)，K(K)死循環(huán)，但由定義知二者矛盾。反之，H(K, K)輸出死循環(huán)，則K(K)停機(jī)，兩者一樣矛盾。

因此，H不是總能給出正確答案，故而不存在解決停機(jī)問題的方法。

通用圖靈機(jī)

對于任意一個(gè)圖靈機(jī)，因?yàn)樗拿枋鍪怯邢薜?，因此我們總可以用某種方式將其編碼為字符串。 我們用 表示圖靈機(jī) M 的編碼。

我們可以構(gòu)造出一個(gè)特殊的圖靈機(jī)，它接受任意一個(gè)圖靈機(jī) M 的編碼 ，然后模擬 M 的運(yùn)作，這樣的圖靈機(jī)稱為通用圖靈機(jī)(Universal Turing Machine)。現(xiàn)代電子計(jì)算機(jī)其實(shí)就是這樣一種通用圖靈機(jī)的模擬，它能接受一段描述其他圖靈機(jī)的程序，并運(yùn)行程序?qū)崿F(xiàn)該程序所描述的算法。但要注意,它只是模擬,因?yàn)楝F(xiàn)實(shí)中的計(jì)算機(jī)的存儲(chǔ)都是有限的，所以無法跨越有限狀態(tài)機(jī)的界限。

圖靈機(jī)的變體

圖靈機(jī)有很多變種，但可以證明這些變種的計(jì)算能力都是等價(jià)的，即它們識別同樣的語言類。 證明兩個(gè)計(jì)算模型 A 和 B 的計(jì)算能力等價(jià)的基本思想是： 用 A 和 B 相互模擬， 若 A 可模擬 B 且 B 可模擬 A， 顯然他們的計(jì)算能力等價(jià)。注意這里我們暫時(shí)不考慮計(jì)算的效率，只考慮計(jì)算的理論上“可行性”。

首先我們可以發(fā)現(xiàn)，改變圖靈機(jī)的帶字母表并不會(huì)改變其計(jì)算能力。例如我們可以限制圖靈機(jī) 的帶字母表為 {0,1}，這并不會(huì)改變圖靈機(jī)的計(jì)算能力，因?yàn)槲覀冿@然可以用帶字母表為 {0,1} 的圖靈機(jī)模擬帶字母表為任意有限集合 Γ 的圖靈機(jī)。

另一個(gè)要注意的是，如果我們允許圖靈機(jī)的紙帶兩端都可以無限伸展，這并不能增加圖靈機(jī)的計(jì) 算能力，因?yàn)槲覀冿@然可以用只有紙帶一端能無限伸展的圖靈機(jī)來模擬這種紙帶兩端都可以無限 伸展的圖靈機(jī)。

如果我們允許圖靈機(jī)的讀寫頭在某一步保持原地不動(dòng)，那也不會(huì)增加其計(jì)算能力，因?yàn)槲覀兛梢杂?向左移動(dòng)一次再向右移動(dòng)一次來代替在原地不動(dòng)。

其它的常見圖靈機(jī)變種包括：

多帶圖靈機(jī)

非確定型圖靈機(jī)

枚舉器

圖靈可計(jì)算性

圖靈可識別語言

圖靈可判定語言

遞歸可枚舉語言

可計(jì)算函數(shù)

遞歸函數(shù)

停機(jī)問題

可判定性

不可判定性

其它等價(jià)的計(jì)算模型

除了圖靈機(jī)以外，人們還發(fā)明了很多其它的計(jì)算模型。包括：

寄存器機(jī)

遞歸函數(shù)

λ演算

生命游戲

馬爾可夫算法

然而這些模型無一例外地都和圖靈機(jī)的計(jì)算能力等價(jià)，因此邱奇，圖靈和哥德爾 提出了著名的邱奇-圖靈論題：一切直覺上能行可計(jì)算的函數(shù)都可用圖靈機(jī)計(jì)算，反之亦然。