理論的應用（applications of the theory）

在漫長地攀爬過抽象機器與不可能性證明之後，問一句「這一切到底是為了什麼」是公道的。答案是：計算理論並非象牙塔——它悄悄地貫穿了極大量的日常軟體。每當你用某個模式搜尋文字、你的程式碼被編譯、一個網路協定被檢查錯誤，或有人證明某問題是 NP 困難因而停止追逐一個完美的快速演算法時，這套理論都在做真正的工作。

具體而言，這些連結無處不在。有限自動機與正規表示式驅動著每個編輯器裡的搜尋與取代、每個編譯器的詞法分析器，以及像 grep 這類工具與網路入侵偵測中的高速字串比對。上下文無關文法與下推自動機是剖析的基礎：每個程式語言的編譯器、每個剖析器產生器（yacc、ANTLR 及其同類）都建立在文法理論上，同樣的機制也剖析設定檔、標記語言與協定。圖靈機與可計算性給了我們硬性的極限——不可判定性告訴我們，為何一個完美、完全通用的錯誤偵測器或程式等價檢查器不可能存在，而這本身就是有用的知識。複雜度理論與 NP 完全性給了工程師一套精確的詞彙來表達「這在一般情況下難解」，從而正當化轉向近似、啟發式或特例。Buchi 自動機、時序邏輯與模型檢驗則驗證真實的硬體以及攸關安全與安全性的協定。

也許最具實務價值的回報，聽起來也最謙遜：一個 NP 困難證明就是一張「可以停手」的許可證。當你證明某問題是 NP 完全的，你不只是沒能找到快速演算法——你握有強力證據（雖未達確定，因為 P 對 NP 未解），表明不存在高效的精確演算法，所以理性的舉動是去近似、限制輸入、利用某個小參數，或接受隨機性。在軟體之外，同樣的工具也出現在計算語言學（自然語言的文法）、密碼學（支撐安全通訊的單向函數與零知識證明），以及資料庫的設計（把查詢語言當作邏輯）。這套理論的觸及之廣，正是它無聲的辯護。