區塊鏈的圖靈完備

摘要

圖靈於 1912 年在倫敦出生，1936 年 5 月，圖靈提交影響深遠的論文，讓通用圖靈機能模擬人的思考方式，最後，成為人工智慧之父。以太坊的「智能型合約」語言是運用圖靈完備，而圖靈完備的程式語言可以實現所有以前一個程式語言在單機上實現的功能，也即能盡最大限度滿足現實應用場景的開發。

keyword：通用圖靈機、描述數、嘅演算法、停機問題、智能型合約

圖靈完備，圖靈完全性通常指具有無限存儲能力的通用物理機器或程式語言。圖靈完備意味著你的語言可以做到能夠用圖靈機能做到的所有事情，可以解決所有的可計算問題。

圖靈機的發明者：圖靈

圖靈(Turing)於 1912 年在倫敦出生，到了中學就長得高大壯碩，還是長跑健將。Christopher Morcom。他因為感染肺結核，身體嬴弱削瘦，但課業名列前茅，與圖靈一樣對數學、科學有極高的興趣，兩人常一起討論而成為莫逆之交。

無奈Morcom在畢業前一年不敵病魔而過世，用情至深的圖靈深受打擊，卻也因此更加專注於學業。圖靈如此努力的背後還有個重要動力。Morcom原本已經獲得劍橋大學的獎學金，圖靈想替他實現未能完成的人生，以進入劍橋大學為目標，最後圖靈也如願於 1931 年入學就讀。

圖靈無意打造一台真正的機器，因為他要處理的是抽象的原則性問題，重點在於思辨過程，而不是加減乘除。因此圖靈只須設想這台自動機器如何運作，無需考慮它如何製造。事實上這台後來以他為名的「圖靈機」極為簡化，硬體組成只有一個可以左右移動的讀寫頭，以及一條無限長的紙帶。與其說它是計算機，反倒比較像是台打字機。

圖靈機(Turing machine)

圖靈機(Turing machine)就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態，還有一些固定的程序。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然後結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，並轉換自己的內部狀態，然後進行移動。

這些影響讀寫頭與機器狀態的規則可以整理成一張「行為表」，例如，狀態：1，掃描結果—空白，向右移動，塗改方格不改，狀態不變；掃描結果—1，向右移動，塗改方格不改，狀態改為2。狀態：2，掃描結果—空白，向右移動，塗改方格寫上「1」，狀態改為3；掃描結果—不變，向右移動，塗改方格不改，狀態不變。

狀態：3，掃描結果—空白，向左移動，塗改方格不改，狀態改為4；掃描結果—1，向右移動，塗改方格不改，狀態不變。狀態：4，掃描結果—空白，不動，塗改方格不改，狀態不變；掃描結果—1，不動，塗改方格抹去「1」，狀態不變。

圖靈機只能從紙帶上讀取資料，所以行為表得用一行符號來表達，才能印在紙帶上讓圖靈機掃描。例如上面那張行為表可能就會變成一行指令：10RNN；11RN2；20R13；21RNN；30LN4；31RNN；40NNN；41N0N。

接著我們把指令中的英文字母與符號用數字代替，例如 A ~ Z 改為 11 ~ 33，分號”；” = 99，數字也跟著改用兩位數 00 ~ 09表示。如此一來，指令就會化為一串數字，圖靈稱之為「描述數」，意指這行純數字的數列就能描述圖靈機的行為。

正常的描述數可以讓圖靈機經過有限步驟後停下來，產生可計算數。但某些描述數卻可能讓圖靈機中途動彈不得，或是不斷來回繞圈圈，無法產生有意義的答案。例如「讀到 1 就往右；讀到 0 則往左」這個指令，就會讓圖靈機遇到 “1”、”0”相鄰時左右來回，永不停止（這其實就相當於「說謊者悖論」）。

如果一台圖靈機只有一個描述數，我們當然可以輕易地發現某台圖靈機停不下來，從而知道這個描述數有問題。不過實際上不需要建造那麼多台圖靈機。想像有台特別的「通用圖靈機」（圖靈稱之為 ”Universal machine“），可以把其它圖靈機的描述數都掃描進來，那麼它便能模擬任何一台圖靈機的運作。而且描述數除了代表運作規則，也可以當成數字做為編號，按大小順序排列，方便圖靈機搜尋。

圖靈完備的程式語言

圖靈機模型描述的是一個計算程序，它可以像物理的電腦一樣運作，完成一個電腦所能做的所有事情。而所謂圖靈完備的程式語言，即是能夠實現所有計算機可以實現的功能的程式語言。

一台圖靈機個讀取器都會位於條帶其中一格，而部機會做以下三個基本作業當中是但一個：第一，讀取讀取器下嗰格係乜符號；第二，編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；第三，將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔離嘅一個格。

例如：圖靈機計算加減法。想像以下嘅演算法，條帶上面有兩個數值， x 和 y ，兩個都用二進制表達，而兩個數之間同條帶嘅起始有個 $ 做標示，是指部圖靈機會讀嘅輸入會類似噉嘅樣：$0010$0011（「0010」是二進制係 2，而「0011」是二進制係 3）。部機行完一次段演算法之後，條帶嘅狀態就會變成 $0000$0101（「0101」喺二進制入面係 5）

再想像一部圖靈機跟以下嘅演算法行：

// 由 x 嗰度減 1，再加 1 落 y 嗰度，直至 x = 0 為止。

repeat until x == 0, then HALT {

// 用 T2（睇下面）

subtract 1 from x

// 用 T1（睇下面）

add 1 to y

go back to the first $

}

說明如下：

T2（將個數減 1）如下：

補充－將 1 變做 0，0 變做 1；

將個數加 1（睇 T1）；

再做一次補充。

T1（將個數加 1）如下：

如果喺個數嘅左邊盡頭（$）起始，行去個數嘅右邊盡頭；

由右邊開始行，將所有 1 變做 0，直至

將第一個 0 變成 1

一般來講，我們平常使用的計算機程式語言，比如C、GO、爪哇都是圖靈完備的，因為它們都可以最大限度發揮計算機的能力。這些都是單機的情況，而在分布式下的情況如何呢？很顯然，在單機的情況下，實現所需要的功能是主要目的，而在分布式情況下如何解決上圖中的不一致的問題才是最關鍵的考量。

停機問題

圖靈完備語言最顯著的一個特點是支持循環，所謂循環，就是程序能不斷執行下去。那麼在區塊鏈支撐的分布式環境下，礦工如何判斷一個程序何時結束呢？而圖靈計算理論，也有人證明過，要證明一個程序能不能終止是不可能的（圖靈停機問題），所以這種「智能型合約」語言需要保證所寫出的程序不能存在死循環。

這也是為什麼以太坊語言會加入 GAS 氣體（瓦斯）的原因，通過加入氣體，程序每個運算過程都會消耗一定成本，從而不會無限制地執行下去。圖靈完備的智能合約相信在不久的將來可以實現更多、更複雜的去中心化的功能。不過，合約制定者不需要擔心防衞類似攻擊，因為如果執行中途停止則所有更改將被恢復。

計算機能模擬人的思考方式

1936 年 5 月，圖靈提交這篇影響深遠的論文：《論可計算數及其在判定性問題上的應用》 (On Computable Numbers, with an Application to the Entscheidungsproblem)，不但在數學上占有重要地位，更展示許多計算機的創新設計。

他率先提出通用計算機的概念，將不同程式預先載入後再開始運行。而程式轉化為描述數，使得程式和資料共用同一個載體，也是首創。同時描述數做為程式的獨特編號，就相當於電腦程式在記憶體中的貯存位址；許多人相信這個概念啟發了馮紐曼用於 ENIAC 的設計。

圖靈還揭示了常人所未見的計算機角色。計算機的作用向來純粹就只為數學計算，但圖靈在這篇論文中卻是從人類如何思考的角度，討論如何讓機器模仿計算者的心智狀態。多年之後，圖靈提出「圖靈測試」，因而被稱為「人工智慧之父」。

以太坊的智能型合約

我們知道，比特幣誕生之後，大家逐漸發現了其底層的區塊鏈技術的巨大價值，同時認為區塊鏈技術才是分布式環境下解決這種一致性問題，可信的技術體系。這種分布式環境下實現一致性的語言現在都被統稱為「智能型合約」。比特幣腳本語言就是這樣一種語言，它實現了非常安全的數位貨幣計算模型，保證了在不需要第三方機構的情況下，兩方之間可以進行價值的轉移。

但是，現實世界的需求是極其龐雜的，為了滿足未來將區塊鏈技術應用於更多場景的可能需要，比特幣腳本語言是遠遠不夠的。這也是為什麼以以太坊為代表的區塊鏈技術，都宣稱自己所採用的「智能型合約」語言是圖靈完備的主要原因。

所以以太坊朝著這個目標在前進，也正是由於這個平台的強大，目前基於以太坊開發的區塊鏈應用越來越多。為什麼呢？通過上面的介紹就知道，以太坊的「智能型合約」語言是圖靈完備的，而圖靈完備的程式語言可以實現所有以前一個程式語言在單機上實現的功能，也即能盡最大限度滿足現實應用場景的開發。