現代開發者若有機會接觸圖靈機,接下來,可能會進一步深入運算的原理,而在探索過程中,你會發現有種神奇機器,能憑藉瞎猜來轉移至下個正確狀態。而這種「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)評估,非確定性也是一種可行的設計方案。

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

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

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

 

作者簡介


Advertisement

更多 iThome相關內容