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

第3章

最簡單的電腦

我們在短短的幾年之內就被電腦包圍了。它們曾經安全的隱身在軍事研究中心和大學實

驗室，但現在它們無所不在：在我們的桌上、口袋、汽車引擎蓋底下，甚至植入我們的

身體。身為程式設計者，雖然每天都在使用複雜的計算裝置，但我們瞭解它們的運作方

式有多深呢？

伴隨現代電腦的威力而來的是諸多的複雜性，使得電腦眾多子系統的每個細節變得難以

瞭解，而這些子系統彼此如何相互建立整個系統的細節，更是難以瞭解。這種複雜性使

得直接推論現實電腦的能力和行為變得不切實際，因此，擁有簡化過並能完全瞭解細節

且與現實機器共享有用功能的電腦模型，將會相當有用。

我們會在本章剝去電腦的概念，讓電腦回到最原始的本質，看看它可以用來做什麼，並

且探索這類簡單電腦的極限。

決定論有限自動機

現實生活裡的電腦通常擁有大量的揮發性記憶體（RAM）和非揮發性儲存空間（硬碟

或 SSD）、許多 I/O 裝置，以及能夠同時執行多個指令的數個處理器核心。

有限狀態機

（

finite state machine

），也稱為

有限自動機

（

finite automaton

），是經過相當程度簡化的電腦

模型，它拋出了這所有的功能，以換取易於理解、易於推論、易於以硬體或軟體實作。

狀態、規則、輸入

有限自動機沒有永久固定的儲存空間，也沒有實質的 RAM。它是具有少數可能

狀態

（state）的小機器，並且能夠追蹤目前的狀態（可將它想作擁有足夠 RAM 的電腦，且

能儲存單一的值）。