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

第5章

終極機器

我們在第 3、第 4 章研究了簡單的運算模型能力。我們已經討論了如何識別日益複雜的

字串、如何匹配正規運算式，以及如何解析程式設計語言，這一切皆使用幾乎不複雜的

基本機器。

但我們也看到，這些機器（有限自動機和下推自動機）有很大的限制，而這會侵蝕它們

作為實際運算模型的實用性。我們的玩具系統還需要多少運算能力才能擺脫這些限制、

才能完成一般電腦可以執行的一切？要模仿 RAM、硬碟或正確的輸出機制等行為需要

多少的複雜程度？設計一個能夠真正

執行程式

而非總是執行單一寫死任務的機器需要

什麼？

在 1930 年代，艾倫 • 圖靈（Alan Turing）正在從本質解決這個問題。當時，『電腦』

這個字的英文原意是計算者（computer），其工作是以人手重複一系列費力的數學運算

來執行冗長的計算，而當時通常是由女性負責這類工作。圖靈在尋找一種方式來瞭解並

描述人力計算者的動作，以便讓相同的工作可以完全由機器執行。在本章，我們將會檢

視圖靈的革命性想法，也就是如何設計最簡單且可行的『自動機器』，這種機器將可獲

得人力運算的完整功能和複雜。

決定論圖靈機

我們在第 4 章曾經將堆疊加到有限自動機，以此當作有限自動機的外部記憶體能增加有

限自動機的運算能力。相較於機器狀態所提供的有限內部記憶體，堆疊的真正優點是它

能動態增加而適應任何數量的資訊，允許下推自動機處理需要儲存任意數量資料的問

題。