深入理解運算原理｜從簡單的機器到無所不能的程式

Afterword

後記

是的，以上就是我們整個運算理論之旅的終點。我們設計了具備各種功能的語言和機

器，從罕見的系統找出運算方式，並且栽進電腦程式設計的理論界限裡內。

沿途除了探索特定的機器和技術，我們也已經看到了若干更為全面的想法：

• 任何人都可以設計並實作程式語言。語法和語意的基本概念相當簡單，而諸如

Treetop 之類的工具可以提防百般無趣的細節。

• 每個電腦程式都是數學物件。就語法而言，程式只是大型的數值；它在語意上表示

數學函數，或者是可以藉由正式的化簡規則來操縱的階層結構。這意謂著來自數學

的許多技術和結果，例如 Kleene 的遞迴理論或 Gödel 的不完全理論，同樣可以適

用程式。

• 我們最初只是將運算描述成『電腦做什麼』，但事實證明運算是某種自然力量。很

誘人的是將運算想像成精巧複雜的人類發明，只能由許多複雜零件組成的專屬系統

執行，但它也出現在似乎不夠複雜而無法支援它的系統。因此，運算並不是發生在

微處理器內部的無趣人造過程，而是在許多不同地方和許多不同的方式發生的普遍

現象。

• 運算並非不容妥協的全有或全無。不同的機器擁有不同能量的運算能力，這給了我

們相當實用的連續體：DFA 和 NFA 的能力有限，DPDA 和 NPDA 的能力較強大，

而圖靈機是我們所知道最強大的。

• 編碼和抽象的層級對於運算能力的運用非常重要。從非常低階的半導體物理學開

始，提升到更高階的多點觸控圖形使用者介面，電腦就是維護抽象高塔的機器。為

了讓運算有用，我們需要能以機器可以操縱的更簡單形式，對來自現實世界的複雜 ...