非確定性（nondeterminism）

想像你在走迷宮，來到一個岔路口。一個「確定型」的行人必須選定唯一一個方向往前走。相對地，「非確定型」的行人則被允許分身成好幾個副本，同時讓每一個副本走進不同的岔路；只要其中任何一個副本最後走到出口，我們就說這座迷宮被解開了。非確定性正是這個想法：被允許同時嘗試好幾種可能，而不是只走一條路。

更精確地說，在確定型機器中，每一種情境（你在哪裡、讀到什麼）都只通往唯一一個下一步。在非確定型機器中，同一個情境可能允許好幾個下一步，甚至一個也沒有。只要「存在」至少一條合法的移動序列通往成功，機器就算成功。並不要求每一條路都成功，也不要求每個情境都有路可走——有一條好路就夠了。一句好記的口號是：非確定型裝置在「某一個」選擇行得通時就接受。

關於有限自動機中的非確定性，最重要也最令人驚訝的事實是：它不會增加任何運算能力。非確定型有限自動機能做到的事，普通的確定型也都能做到（只是可能需要多得多的狀態）。所以在這裡，非確定性是給設計者的便利，而不是一種新的運算方式。要小心：非確定性「不是」隨機，也「不是」真實晶片免費就能做到的東西。它是一種數學上、描述上的工具。同樣的想法稍後會以更重大的形式回到 NP 類——那時「這份便利能不能總是被廉價地消除」就成了著名的未解難題。