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

不可能的程式

|

269

無論哪種方式，我們都稱它為『邱奇 - 圖靈論題』，而不是『邱奇 - 圖靈

定理』，因為它是一種非正式的要求，而不是可以證明的數學斷言；它不

能以純粹的數學語言表示，所以無法構建數學證明。很多人都認為它是事

實，因為它符合我們對於運算本質和哪種演算法夠格的證據的直覺，但是

我們仍然稱它為『論題』，是為了提醒自己，它和可以證明的概念（例如

畢達哥拉斯定理），分屬不同的情況。

邱奇 - 圖靈論題意謂著圖靈機儘管簡單，但具有執行任何原則上可由人依照簡單說明而

進行的運算所需要的所有功能。許多人比這更進一步並聲稱，因為所有試著編碼演算法

都會導致運算能力和圖靈機器相當的通用系統，而這不可能完成任何更好的結果：任何

現實世界的電腦或程式語言只能完成圖靈機可以完成的功能，無法超過。無論最終是否

可能建置運算能力優於圖靈機的機器（可以使用外來的物理學定律來執行超出我們認為

的『演算法』的任務），並非確定能夠知道，但能確定的是我們目前不知道該如何完成。

程式可以參與圖靈機

正如我們在第 5 章所見，圖靈機簡易的特性讓設計特定任務的規則手冊變得很麻煩。

為了避免我們對運算能力的鑽研因為圖靈機程式設計討厭的細節而失色，我們將使用

Ruby 程式替代，就如同我們在歐幾里德演算法所做的一樣。

這種技巧因為通用而顯得正當：我們原則上可以將任何 Ruby 程式轉譯成等效的圖靈

機，反之亦然，因此 Ruby 程式的運算能力不會像圖靈機那麼強大，而我們可以發現的

所有 Ruby 能力的限制，應該也同樣適用圖靈機。

明智的反對意見是 ...