圖林機器理論

英國數學家A.M.圖林在1936年提出的一個理想的機器的理論。這種理想的機器，後來被命名為圖林機，它的結構非常簡單，元件的功能非常弱。對這種機器可描述如下：有一條一端或兩端無限伸長的紙帶，上面劃成一個一個的方格，方格內可印有字母或為空白。有一個元件叫做讀頭,它每次都注視一個方格,辨認其內容。讀頭可以不斷地處在不同的狀態中，也可以説接受不同的指令，然後根據讀頭注視方格的內容以及當時讀頭所處的狀態或所接受的指令，決定機器當時的動作。

動作分以下三種：讀頭左移(L)而注視左方一格；讀頭右移(R)而注視右方一格;讀頭印刷(P)一新字母或抹去原有字母，如果用 S0表示空白，則抹去原字母可以説是印刷S0；動作完了以後讀頭再轉入一新狀態，即接受一新指令。就圖林機而言,方格內所能印的字母是有限個的固定的,設為 S0，S1，…，Sm（S0表示空白），機器可能處的狀態或接受的指令也是固定的、有限的。設為q0，q1，…qn，並規定 q1為開始狀態，機器開動時便處在狀態q1中；又規定 q0為終止狀態，而當機器處在狀態q0時，便不再動作了。該機器的每個狀態及其功能可刻劃如下：

qiaLqj，qiaRqj，qiabqj。其意是,處在狀態qi的讀頭,如果注視格內的字母為a,則讀頭左移或右移,或印字母b，然後轉入狀態qj。但q0則沒有任何動作。由於引入終止狀態 q0, 並要求除q0以外的任何狀態qj對注視格內任何字母都應有所動作, 這樣即使沒有任何動作而轉入qj，也能寫成qiaaqj。

每個圖林機器都可用字母表A={S0，S1，…，Sm}與狀態動作表P={qiSaHbqj}（這裏 Hb為L、R或一字母）來刻劃，如果字母數為m+1，狀態數為n+1，則狀態動作表共(m+1)n行且q0不出現在最左端。雖然定有終止狀態q0，但如果從 q1開始，永遠轉不到終止狀態，則圖林機必永遠運轉而不停止。凡對任何開始字均能停止的機器叫做必停機器，未必停止甚至可能永遠運轉的叫做一般的圖林機。

在圖林機上,未印字母的格叫做空格,印有字母的格叫做實格。如果規定紙帶的兩旁必須全是空格，設最左的實格到最右的實格之間所印的字母依次序為a1,a2,…，an，其間若有空格，則用字母S0表示之，這就使該紙帶所表示的字為a1，a2，…an。如果讀頭恰好注視了其最左實格a1，則説讀頭標準注視了 a1a2…an。例如，有一圖林機器Ц，它從標準注視字 P開始（狀態為q1），根據機器的狀態動作表而繼續變動，直到出現終止狀態q0為止，如果這時紙帶上所表示的字變成了 Q，就表明機器Ц把P改造為Q,記為Ц(P)=Q；如果從標準注視P開始後，繼續運轉永遠達不到終止狀態，從而機器也永不結束，則表明Ц對P改造無結果，亦即Ц(P)無意義。

為了使用圖林機計算數論函數，須用圖林機器字母表上的字表示自然數。為此，最簡單的方法是使用兩個字母{S0，S1}，S0表示空白，S1相當於一豎,凡兩旁為空格而中間有n+1個相鄰實格的便表示數n，即用一個實格表示0,兩個實格表示1等等。要表示三元數組(a,b,c)可使用一個空格、a+1個實格,一個空格、b+1個實格,一個空格、c+1實格和一個空格。設機器Ц從標準注視x（或標準注視 x1，x2，x3）開始，根據狀態動作表而依次運轉，直到Ц把 x變成ƒ（x）,（把x1，x2，x3 變成g(x1，x2，x3)）為止，就説機器Ц計算了函數ƒ(x)(函數g(x1，x2，x3))。但如果 ƒ(x)(g(x1，x2，x3)) 無定義，則要求Ц永不停止或雖停止而給一個表示無結果的信號，例如，S0，S1以外的任何信號。

表面看來,圖林機器的功能是非常弱的。但是,只要提供足夠的空間（紙帶有足夠長）以及足夠的時間（步驟足夠多），那麼它的力量是非常強的，足以代替目前的任何計算機。實際上，任何遞歸半函數都可以用未必永停的圖林機計算，任何遞歸全函數即任何一般遞歸函數（見遞歸論）都可以用永停的圖林機計算。反之，凡能用一般圖林機器計算的數論函數都是遞歸半函數，凡能用永停圖林機器計算的數論函數都是遞歸全函數即一般遞歸函數，兩者實質上是一樣的。利用圖林機器計算遞歸函數具有很大的方便性。數理邏輯學界一致承認可計算函數與遞歸函數是相同的，從而一函數是可計算的當且僅當它是可用圖林機計算的。 ^[1]