非確定型圖靈機

定義

如果不加特殊說明，通常所說的圖靈機都是確定型圖靈機。非確定型圖靈機和確定型圖靈機的不同之處在於，在計算的每一時刻，根據當前狀態和讀寫頭所讀的符號，機器存在多種狀態轉移方案，機器將任意地選擇其中一種方案繼續運作，直到最後停機為止。具體而言，其狀態轉移函式為

其中 Q是狀態集合，

是帶字母表，

分別表示讀寫頭向左和向右移動；符號

表示集合

的冪集，即

例如，設非確定型圖靈機

的當前狀態為

，當前讀寫頭所讀的符號為

，若

則 M將任意地選擇一個

，按其進行操作，然後進入下一步計算。

非確定型圖靈機 M在輸入串

上的計算過程可以表示為一棵樹，不同的分支對應著每一步計算的不同的可能性。只要有任意一個分支進入接受狀態，則稱 M接受

；只要有任意一個分支進入拒絕狀態，則稱 M拒絕

；某些分支可能永遠無法停機，但只要有一個分支可以進入接受或拒絕狀態，我們就說 M在輸入

上可停機。注意，我們規定 M必須是無矛盾的，即它不能有某個分支接受

而同時另一個分支拒絕

，這樣有矛盾的非確定型圖靈機是不合法的。

定理：對於任意一個非確定型圖靈機M，存在一個確定型圖靈機M'，使得它們的語言相等，即

。

證明：因為非確定型圖靈機的計算過程就是一棵樹，因此我們只需遍歷該樹就可以模擬其計算過程。一個簡單的想法是利用深度優先搜尋來遍歷 M的計算樹，但這樣行不通，因為 M的某些計算分支可能永遠不停機！所以我們可以採用一種在算法設計中稱為疊代加深搜尋的技巧來遍歷 M的計算樹。具體證明如下：

對於非確定型圖靈機 M，構造一個確定型圖靈機M'如下：

1.令

；

2.深度優先地模擬 M的每個分支的計算，但每個分支最多只計算 k步，如果某個計算分支在 k步內可以停機，則M'也停機，並將該計算分支的計算結果輸出。

3.令 k增加 1，跳轉到上一步繼續執行。

顯然，若 M有某個分支可以停機，則此 M'也一定會找到該分支並停機。因此

。

定理2：如果語言L被非確定型圖靈機 M在多項式時間內接受，則一定存在多項式P使得語言L被時間複雜度為

的確定型圖靈機程式所接受。

定理2說明了為什麼在證明P=NP之前，所有的NPC問題都只有指數時間複雜度算法。