2.2.2 圖靈機的原理、類型及圖靈等價性

截至本書成稿之日，電子計算機仍不能有效解決NP完全問題，主要原因是電子計算機的計算模型是圖靈機（記作M）。圖靈機是一個抽象機器，由一條無限長的數據帶、一個讀寫頭和一個控制器組成，如圖2.20所示。數據帶可以向兩端無限延伸并被分為一個個方格，每個方格存儲有限字母集（包含空白符）中的一個字符；控制器控制讀寫頭按照設定的狀態轉移函數（又稱程序）進行“移動”，讀寫頭總處于當前狀態。“移動”又稱圖靈運算，它包含如下4個動作。

圖2.20　圖靈機的結構

（1）讀取讀寫頭所指向方格中的字符。

（2）先將讀寫頭所指向方格中的字符擦除，再寫入新的字符。新字符與被擦除字符可以相同。

（3）讀寫頭向左或向右移動一格，或不動。

（4）改變控制器的狀態，但新的狀態可以與移動前的狀態相同。

其中，動作（2）～（4）是基于動作（1）、讀寫頭當前狀態及狀態轉移函數來完成的。若為單值，則稱M為確定型圖靈機；若為多值，則稱M為非確定型圖靈機。本書只考慮確定型圖靈機。

確切地，圖靈機可表示為五元組，即(,,,,)。

（1）是有限狀態集，包括初始狀態與接受狀態集H。

（2）是字母集，每個M具有一個規定的輸入字母集。

（3）是數據帶上可用的有限字母集，。

（4）是空格字符，，但。

（5）是狀態轉移函數。

定義了M在讀取到特定方格中的字符及所處狀態時，刪去該字符后應寫入的字符、移動的方向，以及轉換的狀態。確切地，狀態轉移函數定義為，其中和分別表示讀寫頭向右和向左移動，S則表示不移動。對于讀寫頭不動的情況，可用向左和向右移動各一次代替，因此狀態轉移函數也可定義為。

M在任何時刻都處于一種狀態，狀態代表M在特定時刻的內部信息。初始狀態是M開始運行時的狀態；如果狀態轉移函數停止執行，即當前狀態和讀寫頭讀取的符號在中沒有定義，則M停機。停機時，如果是接受狀態，則計算成功，否則計算失敗。

初始時，上的一個有限字符串（作為輸入）中的字符被分別寫在數據帶上相鄰的方格中，而數據帶上的其他方格都是空的。讀寫頭掃描該輸入最左端的字符，此時M處于初始狀態。隨后的每一步，處于當前狀態的M都先通過讀寫頭讀取數據帶小方格中的字符，再基于執行對應的動作，包括掃描方格上的字符并刪去，寫入新字符，接著讓讀寫頭向左或向右移動，并獲取新狀態。

下面通過一個簡單的例子說明圖靈機的運算原理。定義圖靈機M，輸入字母集，有限狀態集（），輸入的有限字符串為，狀態轉移函數的定義如下：

也就是說，、、、、、。

其中，（,）表示當前狀態為且讀取的字符為時，執行動作是將M的當前狀態變換成，在當前方格中寫入字符，讀寫頭向右移動（）、向左移動（）或保持不變（）。若用連續1的數量表示具體的數字，那么上述過程可以實現數字3與2的加法運算，如圖2.21所示。可見，上述圖靈機M可實現任意兩個數的加法運算。

圖2.21　加法運算的一個例子：3+2=5

圖靈機的概念被正式提出后，產生了許多變體，如多帶圖靈機和概率圖靈機等。下面詳細介紹多帶圖靈機。

按照讀入數據帶數量的不同，圖靈機可分為單帶圖靈機和多帶圖靈機。之前討論的圖靈機默認為單帶圖靈機。多帶圖靈機使用多條數據帶，每條數據帶都有自己的讀寫頭。注意，任何多帶圖靈機，無論有多少條數據帶，都可以由單帶圖靈機模擬。因此，可以認為多帶圖靈機和單帶圖靈機具有相同的計算效率。

圖靈機是一種簡單的計算模型，許多更加復雜的計算機器看似比圖靈機強大得多，但丘奇-圖靈論題道出了一個共識：任何可以通過合理的計算模型計算的函數都可以用圖靈機計算。也就是說，這些計算機器與圖靈機相比并沒有更強的計算能力。

圖靈等價性是指：在計算理論中，兩種計算模型能夠互相模擬和等效。具體而言，如果計算模型A可以模擬計算模型B的所有計算過程，并且計算模型B可以模擬計算模型A的所有計算過程，那么這兩種模型就是圖靈等價的。圖靈等價性的概念源自圖靈機的理論。圖靈機是一種抽象的數學模型，可以描述一種具有無限存儲能力的計算機。圖靈證明了只要一種計算模型能夠實現與圖靈機相同的計算能力，即能夠計算所有可計算函數，那么這種模型就是圖靈等價的。大多數計算模型都是圖靈等價的，如演算和通用遞歸函數。圖靈等價性意味著，雖然它們可能在形式和操作上有所不同，但能夠計算出相同的可計算函數集，因此在理論上是等效的。