程式人如果曾經想要瞭解、奠定運算方面的理論基礎,往往就會接觸到圖靈機(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),可以類比為平行、猜測或評估的作法,雖不能增加運算能力,然而,卻有可能增加獲得解答的速度或可能性等。

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

作者簡介


Advertisement

更多 iThome相關內容