現代開發者若有機會接觸圖靈機，接下來，可能會進一步深入運算的原理，而在探索過程中，你會發現有種神奇機器，能憑藉瞎猜來轉移至下個正確狀態。而這種「Seafood」等級的機器，看似只存在於想像之中，除了在運算原理中探討運算能力等價性，還能有其他用途嗎？

非確定性有限自動機

在運算原理的探討中，往往從簡單的有限狀態自動機（Finite-state Automaton）開始構造，它沒有存取裝置，也就是沒有記憶能力，只看得到目前的狀態，但這機器能夠運算嗎？

例如，若是拿起一朵花，一片片抽掉，反覆地唸著「愛我」或「不愛我」來得到答案，這類問題還是能用有限狀態機解決的。能回答抽花瓣的機器，就相當於能識別某符號是否以2倍長度出現的機器。

基本上，當中的運作原理是：狀態1是初始，也是接受狀態，讀到a，就轉移至狀態2，再讀到a，又再轉回狀態1；類似地，要識別某符號是否以3倍長度出現的機器，會有三個狀態，讀到a，就轉移至狀態2，出現下個a，就轉移至狀態3，再來個a，即回到狀態1。

如果要設計識別某符號是否以2倍數，或者是3倍數出現的機器呢？例如，有個人先將輸入餵給其中一臺，若最後處於不可接受狀態，再餵給另一臺；若仍是不可接受狀態，那麼，輸入符號個數就不會是2倍數，或者是3倍數；然而，設計機器是為了將人的因素排除在外，有辦法將這兩個機器合併嗎？

也許機器一開機，不讀取任何輸入，就會馬上驅動馬達，看看卡上哪個規則齒輪。如果卡上判斷2倍數的齒輪，而輸入正好是2倍數符號，機器最後會處於接受狀態；若是3倍數符號，機器也能神奇卡中判斷3倍數的齒輪，問題就解決了。此時，這樣的機器稱為非確定性（Nondeterministic）有限自動機。

現實中，當然也沒有每次運氣都這麼好的神機，也就是說，設計不出這種等同於神蹟的演算法。實際上，非確定性有限自動機未必更強大，只是狀態較少，規則較少，一開始比較容易設計罷了。運算理論也會告訴你，透過合併狀態，這種非確定性有限自動機，都能轉換為對應的確定性（Deterministic）有限自動機。

非確定性下推自動機

比起有限狀態自動機更先進的機器，是一種擁有堆疊結構存取狀置的下推自動機（PushDown Automaton），因為機器能將運算結果暫時儲存在堆疊中，就有能力先去執行其他運算，因而下推自動機可以解決的問題，會比有限狀態自動機還多。

例如，下推自動機可以判斷輸入是否為對稱括號，像是「(())()」。像是，只要看到一個「(」就在堆疊中放一個積木，看到一個「)」就將積木從堆疊中移出；在消化全部的輸入之後，看看堆疊是否為空，就可以知道括號是不是對稱了。

然而，正讀、反讀都一樣的迴文呢？

如果可以將輸入寫在紙帶上，然後有人能對折紙帶並從中剪開，用一個代表中點的紙片重新接合，事情就簡單了。因為，機器可以將遇上中點紙片前的符號，逐一置入堆疊，而中點紙片之後遇上的符號，就看看是否等同於堆疊頂端的符號，若是就取出，若否就表示不是迴文了。

然而，機器是要去除人的因素，若沒有人為介入，只能要求機器能夠猜中，也一定可以猜中什麼時候讀完一半的輸入，自動轉換至取出堆疊中符號的狀態了，這樣具有非確定性的神奇機器，稱為非確定性下推自動機。

當然，現實機器若要用猜的，一定會有運氣不好的時候，也就是，明明是迴文而機器卻猜錯中點而不接受的情況，而這樣的機器可以稱為運算機器嗎？就機器本身來說，增加這種瞎猜的不確定性，至少還有「可能」矇對，如果沒有這種不確定性，就什麼也沒有了。因此，若可以接受可能性的答案，這仍然是個運算機器！

由於堆疊的狀態難以預測，可判斷迴文的非確定機器，沒辦法透過合併狀態來得出對應的確定性機器，就算想要列出全部的執行路徑，也不可行。

因為資料一從堆疊中取出，就會永遠消失，不可能在之後回溯至某個狀態。也就是說，確實有著確定性下推自動機無法回答，然而瞎猜必中的神機卻可以解答的問題。

非確定性圖靈機

關於確定性與非確定性的探討，乍看之下，是個不切實際的話題，然而，因為每個程式語言就相當於通用圖靈機。

就這點來說，現代程式設計處處可見確定性與非確定性的實例。例如，搜尋陣列中某個元素，以最簡單的線性搜尋來說，從頭至尾逐一比對，就是確定性演算的一種；至於非確定性演算，就是猜測索引值，而該索引位置就是想尋找的元素。

實際上，不可能存在每猜必中的非確定性演算，單純使用隨機數的話，運氣不好、沒猜中的機會居多，而且，線性搜尋排除運氣好壞的影響，雖然速度緩慢，但確實可以達成任務。也就是說，對圖靈機來說，非確定性演算並不會增加額外運算能力。

雖然每次都能猜中的「神機」不存在，然而，如果能忍受瞎猜，或者說是可以接受可能性的結果，以非確定性機器的概念來打造只求得可能性的機器，還是有其設計的簡單與速度快的優點。例如，陣列中相符的元素其實很多，幾乎每次都能猜中想要的元素索引位置，那麼，就不用特別費心，來設計高效率的確定性搜尋演算法了。

高效率的確定性演算法，某種程度上，也是結合了非確定性演算的概念。

例如，資料若已經事先排序，之後採用二分搜尋法時，每次決定採用中間索引，可以看成是一種猜測，若不符合，再決定使用往左或往右的中間索引；如果認為排序過後，想要的資料極有可能在前三分之一區段，那麼，每次猜測三分之一索引處，也未嘗不可。反正，最差的情況總比線性搜尋好，要是一次就猜中，那就等同於神機。

某種外部參與形式

有些演算法，本身就是非確定性的，對於非確定性演算法來說，每次執行時，就算是相同的輸入，都可能產生不同的結果。隨機數產生器就是一個例子，有時就是需要隨機性，像是隨機迷宮、隨機字符（Token）或者機率模擬等，有時若能接受可能性的答案，加上一些啟發式（heuristic）評估，非確定性也是一種可行的設計方案。

完全沒有人為因素下，判定迴文的非確定性下推自動機並不存在，然而，如果將人視為機器的一部份，人為的參與就能構成這臺非確定性機器。

若從上述這點來看，非確定性機器也非單純理論上的「神機」，因為非確定性實際上代表著某種外部參與形式。就圖靈機來說，某種外部參與形式（也就是非確定性），雖然無助於增加運算能力，然而，若能降低機器設計與打造時的難度，或者是加快機器執行的效率，這樣的外部參與就有價值。

現實中有許多程式，一開始在實現時會需要人的參與，就是這樣的概念，在能解決問題之後，進一步思考如何能減少外部參與（也就是減少非確定性），也正是現代程式設計努力的課題之一，如果在深思之後，某個外部參與確實是必要，就算那樣的外部參與是瞎猜（隨機），只要有益於解決問題，也會是個可行的方向！