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

第7章

四處皆通用

我們在這個世界所看到的大多數複雜事物是來自複雜的系統（哺乳動物、微運算器、經

濟、天氣），所以自然就會假設簡單的系統只能完成簡單的事情。但我們在本書已經看

到簡單的系統也可以擁有令人印象深刻的能力：第 6 章已經證明了即使是極小的程式語

言也具有足夠的能力來完成有用的工作，而第 5 章勾勒出通用的圖靈機設計，可以讀取

另一台機器編碼過的描述，然後模擬它的執行。

通用圖靈機的出現真的非常重要。即使任何個別的圖靈機都有一本寫死的規則手冊，但

透過讀取磁帶裡的指令，通用圖靈機示範了可能設計出能夠適應各種任務的裝置。這些

指令實際上是控制機器硬體運算的一段軟體，就像我們每天使用的可程式化通用電腦

1

。

有限和下推自動機有點

太過於

簡單，以致於無法支援這種完整的可程式性，但是圖靈

機就複雜的能讓它運作。

我們會在本章介紹幾個簡單的系統，並且發現它們全都是通用系統（它們全都能模擬圖

靈機，因此全都能執行從輸入提供的任何程式，而非系統裡寫死的規則），由此可知通

用真的比我們預期的更為常見。

Lambda 演算

我們已經知道 lambda 演算是一種可用的程式語言，但是我們尚未探索它是否像圖靈機

一樣強大。事實上，lambda 演算至少必須夠強大，因為它能模擬任何圖靈機，（當然

也）包括

通用

（

universal

）圖靈機。

1 『硬體』是指讀寫磁帶頭、磁帶、規則手冊。它們不是字面上的硬體，因為圖靈機通常是想法的實驗，

而不是實體的物件，但它們是『硬』的，因為相對於以字元寫進磁帶而存在並且不斷變化的『軟』資訊

而言，它們是系統固定的部分。 ...