非確定性不是隨機（nondeterminism is not randomness）

我們很容易把非確定型機器想像成：在每個岔路口擲一枚硬幣，然後祈禱好運。這個圖像是錯的，而且這個差別很重要。非確定性沒有硬幣、沒有機率，也沒有運氣。機器並不存在「選錯了」而拒絕一個本該接受之字串的可能。它的定義純粹關乎「存在」：只要至少存在一條接受路徑，字串就被接受，就這麼簡單。

把這兩個概念精確對照。隨機化機器在它的選擇上帶有機率，可能以例如 0.9 的機率接受同一個輸入——你跑它，有時會得到錯的答案。非確定型機器則完全沒有機率；「接受」是關於「所有可能執行所成之樹」的一個邏輯命題（是否存在一片接受葉子？），而不是任何單一實體執行的結果。因此非確定性是一種定義上、描述上的工具——一種指定語言的方式——而不是對任何真實機器逐刻運作方式的描述。

由此得到兩個實際的後果。第一，真實硬體不會免費得到非確定性；要真正判定是否接受，確定型電腦必須搜尋或模擬整棵選擇之樹（對 NFA 而言，就是追蹤可能狀態的集合）。第二，當這個想法以 NP 類的身分回歸時，賭注就提高了：NP 是用「非確定型多項式時間」定義的，而那種存在式的猜測能否總是被確定型機器在多項式時間內模擬，正是未解的「P 對 NP」問題。把「非確定型」與「隨機」乾淨地分開，對理解有限自動機與複雜度理論都至關重要。