非確定型圖靈機

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

\delta :Q\times \Gamma \to 2^{Q\times \Gamma \times \{L,R\}}

其中 $Q$ 是狀態集合， $\Gamma$ 是帶字母表， $L,R$ 分別表示讀寫頭向左和向右移動；符號 $2^{A}$ 表示集合 $A$ 的冪集，即

2^{A}=\{S~|~S\subseteq A\}

例如，設非確定型圖靈機 $M$ 的當前狀態為 $q$ ，當前讀寫頭所讀的符號為 $x$ ，若

\delta (q,x)=\{(q_{1},x_{1},d_{1}),(q_{2},x_{2},d_{2}),\ldots ,(q_{k},x_{k},d_{k})\}

則 $M$ 將任意地選擇一個 $(q_{i},x_{i},d_{i})$ ，按其進行操作，然後進入下一步計算。

非確定型圖靈機 $M$ 在輸入串 $\omega$ 上的計算過程可以表示為一棵樹，不同的分支對應著每一步計算的不同的可能性。只要有任意一個分支進入接受狀態，則稱 $M$ 接受 $\omega$ ；只要有任意一個分支進入拒絕狀態，則稱 $M$ 拒絕 $\omega$ ；某些分支可能永遠無法停機，但只要有一個分支可以進入接受或拒絕狀態，我們就說 $M$ 在輸入 $\omega$ 上可停機。注意，我們規定 $M$ 必須是無矛盾的，即它不能有某個分支接受 $\omega$ 而同時另一個分支拒絕 $\omega$ ，這樣有矛盾的非確定型圖靈機是不合法的。