非確定型圖靈機（nondeterministic Turing machine）

想像你站在迷宮的岔路口。一般（確定型）的探險者必須選一條路。非確定型的探險者則在每個岔路都複製自己，同時派一個分身走每條岔路，只要有任何一個分身抵達出口就算成功。非確定型圖靈機（nondeterministic Turing machine）就是這樣運作：在某個狀態與帶上符號下，它可能有好幾個可行的動作，而只要存在至少一串選擇能引到接受並停機，它就「接受」該輸入。

形式上，相對於普通圖靈機，唯一的改變在轉移函數。δ(q, a) 不再恰好給出一個下一步，而是傳回一組可能的下一步：δ : (Q x Γ) -> P(Q x Γ x {L, R})，其中 Γ（Gamma）是紙帶字母表，P(...) 是冪集（所有子集所成的集合）。計算不再是一條直線，而是一棵格局（configuration）的分支樹：凡是允許多個動作的節點都會岔出多個子節點。若這棵樹有某個分支抵達接受狀態，機器就接受 w；唯有當每一個分支都停機而不接受時，它才拒絕。

確定型機器可以模擬它：有系統地搜尋整棵計算樹，以廣度優先（一層一層地搜，這樣某條無窮分支才困不住它）展開，並在任何分支接受的當下就接受。因此非確定型與確定型圖靈機識別的語言完全相同，邱奇-圖靈論題仍然成立。代價在於速度：搜尋一棵分支因子 b、深度 t 的樹大約要 b^t 步，是指數爆炸。對於對應的時間受限模型而言，這個指數代價是否真有必要，正是著名的 P 對 NP 問題，所以這個慢化值得記下來。這裡的非確定性是一種數學上的搜尋裝置，既非真正的平行電腦，也不是隨機。