程式人如果曾經想要瞭解、奠定運算方面的理論基礎，往往就會接觸到圖靈機（Turing Machine），我們多半的印象可能會認為，這是個空想的機器，或者說是數學探討。

然而，除了認為它是一堆狀態、箭頭、符號組成的模型之外，可曾想過，這其實是在親手打造一臺圖靈機呢？

紙上圖靈機

圖靈機是由艾倫·麥席森·圖靈（Alan Mathison Turing）在1930年代提出，至今仍是運算理論研究的中心課題，原因或可從《深入理解運算原理》第五章的引言獲得解答。

在當時，運算者（Computer）的工作「是以人手重複一系列費力的數學運算」，而圖靈在尋找一種方式，「瞭解並描述人力運算者的動作，以便讓相同的工作可以完全由機器執行」。

圖靈機模型將運算者執行的運算，分解至無法再分割的程度，，而這極為簡單的運算易於理解，也易於結合以建立起複雜的運算行為。相較於現代真實的電腦，圖靈機剝除了真實電腦的複雜性，藉由探討圖靈機的行為與用途，可以更根本地瞭解運算的本質，像是它能做到什麼？是什麼令運算能力得以增強？又有哪些無法達成的運算？

圖靈機的簡單運算被稱為規則，而規則格式是來自真實的人力運算者，因此，運算者目前的心智狀態、眼睛觀察到的符號，決定接下來運算的執行方式，亦即在紙帶寫下的執行結果（符號）及新的心智狀態，因而圖靈機的規則格式，都一致擁有五個元素：「目前狀態」、「讀入符號」、「寫入符號」、「移動方式（左或右）」、「下一狀態」。

每個圖靈機會是由數條規則構成，為了視覺化呈現圖靈機的規則，通常會透過組態圖（Configuration graph），也就是以圓圈標示狀態，以箭號表示狀態走向，箭號上標示讀入、寫入的符號以及磁頭的移動方式，另一個方式就是透過表格，以每一行或每一列來標示出規則，好處是易於撰寫與檢索。

無論面對的是組態圖或是規則表格，就是面對一臺圖靈機（而不只是一堆圓圈、箭頭、符號、欄位），基本上就是假設機器是實際存在的，至少還有你可以躲在一個鐵盒裏，按照規則來進行運算，到了最後，把磁帶塞到外頭給鐵盒外的人看。

別忘了，圖靈機最初的觀察對象，正是真實的人力運算者。

特定運算圖靈機

只要基於圖靈機的規則格式，在紙上畫出了組態圖或是建立了規則表格，實際上，就打造了一臺圖靈機。那麼，我們來打造翻轉位元的機器吧！不使用組態圖或表格，要條列規則也是可以的，就像以下規則的格式是「目前狀態」、「讀入符號」、「寫入符號」、「移動方式（左或右）」、「下一狀態」，其中_表示空白：

* 1、0、1、右、1

* 1、1、0、右、1

* 1、_、_、左、2

* 2、0、0、左、2

* 2、1、1、左、2

* 3、_、_、右、3（接受狀態）

如果磁帶一開始存有01010011，磁頭在最左方，依規則運作完之後，磁帶會有10101100，磁頭回到最左方，當然，目前運算的機器就是你，不過，這對人類太苦了，充滿許多重複性的動作，就不能打造出一臺真正的實體機器嗎？

可以的，畢竟你是開發者，寫個程式來識別符號、以陣列模擬磁帶等，並不是難事，嗯？這樣還算是打造出實體機器嗎？程式不是軟體嗎？不！就算使用程式實現了需求，執行時還是需要硬體吧！

雖說現代電腦十分強大，可以在上頭安裝作業系統、各式各樣的程式，用以完成各式各樣的需求，然而，當安裝了可以執行某程式語言的環境，也用該語言，寫了個可以翻轉位元程式然後執行，在執行的期間，這強大的電腦就是在裝萌，假裝自己翻轉位元的機器了！也就是說，硬體部份就是你的實體電腦，實際上，無論電腦再強大，在執行某程式時，它都將自己模擬成某機器，如果執行的只是個簡單的加法，在當下執行時，電腦就把自己模擬成加法器了。

你可以使用圖靈機的規則格式，打造出二進位數遞增一的機器，或者是加法機器、減法、乘法等機器，只不過，這些機器都是特定運算用途，只能識別特定符號、進行動作、轉移狀態，如果沒有可套用的規則，那麼，機器就卡住了。

通用圖靈機

雖說特定運算用途的圖靈機功能有限，然而，若有耐心，可以為現代常見的運算都打造出一臺圖靈機，然後把這些圖靈機結合起來，並且制訂一組專用規則，可以在某狀態讀入某符號時，轉移至特定功能圖靈機上。而這組專用規則，就是通用圖靈機（Universal Turing Machine），透過這組專用規則，可以隨時將通用圖靈機模擬為特定用途圖靈機。

在先前專欄〈令人腦殘的程式語言〉中談過的Brainfuck，是個具有移動磁帶、讀寫磁帶概念的程式語言，它用的各個符號，像是+-><[].,都有對應的實現，它就是個通用圖靈機。等一下！Brainfuck不是門程式語言嗎？怎麼會是圖靈機？是的！每個程式語言，都是等同於一臺通用圖靈機！

因為每個程式語言，都有一堆語法符號、語法規則，以及可以按規則執行動作的硬體。

舉例來說，看到現今任何一門程式語言的書時，其實都假設了，可以按照程式碼執行的機器，是確實存在的，不然的話，你怎麼會快快樂樂地捧著書、看著文件裏的程式碼呢？至少，如先前提及，還有你可以躲在鐵盒裏啊！

每個程式語言都是一臺通用圖靈機，而使用該語言寫出來的程式，都相當於打造了一臺特定用途圖靈機，因為它只能按照程式碼制訂的規則運算，識別特定的輸入、進行特定的輸出，不在規則內的話，機器如果卡住，就看各程式語言的環境如何規範了。

也因為每個程式都是一臺特定用途圖靈機，按照程式碼制訂的規則進行運算，這規則就是演算法了，所以，當我們在畫圖靈機的組態圖時，不覺得它像演算法的流程圖嗎？

現代電腦十分強大，可以在上頭安裝作業系統、各式各樣的程式，也就是說，現代電腦也是一臺通用圖靈機，上頭模擬了各式各樣的圖靈機，而有些還模擬能夠識別特定符號的通用圖靈機，像是JVM、Node.js，甚至是瀏覽器中的JavaScript執行環境等。

圖靈機中的議題

圖靈機就本質而言，就是將機器簡化到不能再簡單，使之易於理解與推論，從而知道運算的本質，能夠做到及不能做到的事情，因此，探討圖靈機中的一些議題，其實，就等同於在探討現代程式設計的一些議題。

例如，為圖靈機增加磁帶數量，不能增加其運算能力，然而可以令圖靈機在設計時便利許多，這就像是為語言加入一些便捷語法，雖無法增加語言的運算能力，然而可以令程式撰寫更為方便，為圖靈機增加不確定性（non-deterministic），可以類比為平行、猜測或評估的作法，雖不能增加運算能力，然而，卻有可能增加獲得解答的速度或可能性等。

想要更進一步認識現代程式設計的本質嗎？試著動手打造幾臺簡單的圖靈機，會是個不錯的開始，或許更能得到意想不到的收穫！