圖靈機——扳著手指數數
英國數學家圖靈於1936 年發表《論可計算數及其在判定問題中的應用》一文, 文中提出了一種十分簡單而運算能力極強的理想計算裝置———圖靈機的概念, 推進了計算機理論的發展。
艾倫·麥席森·圖靈（Alan Mathison Turing，1912年6月23日－1954年6月7日）
不要被「圖靈機」這個聽上去很高端的名字給嚇到了，其實這是一個很好理解的概念。
首先，我們要知道「圖靈機」是一個抽象的機器，或者說是一切計算機器的理想模型。
既然適用於一切的計算機，就說明這個模型足夠簡單。背後的原理，我們每個人也都可以輕鬆掌握。
首先，讓我們來自製一個計算機器：
第一步，伸出你的手——左手或右手，無所謂。
第二步，輸入計算指令「1+1」，於是你先扳下1根手指，再扳下來1根手指。
第三步，讀取計算結果，觀察手，發現扳下了2根手指。輸出結果「1+1=2」
經過剛才的幾步，其實我們已經理解了所有計算機器運行的基本原理。
1936年，艾倫·圖靈(1912-1954)提出了一種抽象的計算模型 —— 圖靈機 (Turing Machine）。
現在，讓我們和圖靈一起從頭開始設計這台機器。首先，我們需要的我們機器能夠進行計算，這意味著我們能夠將信息輸入進去，也就是把算數式的左端以某種方式告知機器。
這並不需要多麼複雜的設計——因為時刻不要忘了，我們正在設計的並非是一台現在就能在流水線上生產的機器，而是理想的存在的機器。
就像你把數學題用小紙條傳給坐你鄰座的學霸那樣，我們把一切需要計算機處理的信息寫在一個紙條上。為了方便計算機閱讀，我們不妨用一張細長的紙條，使其寬度為一個字元，這樣就可以確保機器一個字一個字地閱讀。
鑒於，我們要設計一台萬能的機器，我們假定這個小紙條（TAPE）可以無限長。
有了紙，學霸還需要什麼才能幫我們做題呢?
答案是學霸需要看題。
So，這台機器需要有一個可以讀取信息的讀取端。
而為了達到幫我們解決問題的目的，學霸還需要一支筆，也就是一個可以輸出信息的輸出端。
一般來說，我們把讀取端和輸出端合併起來——成為一個可以讀取紙條上信息，並且可以動手改寫紙條上信息的讀寫頭（HEAD）。
你可以把讀寫頭視作一個執筆的人，他可以瀏覽和書寫，塗改紙張上的字元，或者添加新的字元。
好的，我們現在已經有了這樣一個人，可以開始解決問題了嗎？
等等，等等。這個人還沒有腦子呢。
雖然他已經在硬體上具備了解決問題的能力，但是卻仍然缺乏解決問題的軟體。那麼，接下來就是請學霸解決問題過程中最關鍵的一步——
教學霸怎麼做數學題！
我辛辛苦苦做了這麼多步就是為了讓學霸幫我做題，你居然告訴我要讓我來教他做？？要他有何用？
其實這也很好理解。計算機不可能無師自通，他處理問題的能力都來自於人類對它的傳授。但是它真正的優勢在於，其永不知疲倦，可以通過巨量的積累來解決問題。這樣，只要它掌握了最基本的原理規律，就可以處理那些非常複雜的問題。
對於我們要設計的這台機器來說，它也需要這樣一套規則（TABLE）。
比如加減乘除規則，或則其他的任何算式、任何用來處理紙上字元的規則，只要輸入規則者可以保證這台機器可以通過這些規則解決所有的問題。
接著就是整個過程中最為精妙的一步，即把這套規則運用到機器中去，把硬體和軟體結合起來。這並不是什麼魔法，而是偉大的艾倫圖靈的智慧。
控制器（CON）。當圖靈機讀到一個它規則中可接受的字元，就會進入某個特定的狀態（如同當你看到加數「1」後扳下一根手指），這一狀態被狀態寄存器所記錄，並且觸發這一狀態所對應的規則。（例如看到加號，則觸發扳手指的規則）這一規則主導下，機器會執行已經做出的新的行動，而這一行動又會帶給計算機一個新的狀態；如此往複，就實現了計算機利用規則，操縱硬體，最終實現計算，並把計算結果輸出的目的。
讓我們來整理一下。
從硬體上來看，圖靈機就是由控制器（CON）、存儲帶(TABLE)和讀寫頭（HEAD）組成。
(1)控制器: 它是一台時序機, 即有限自動機, 具有有限個內在狀態, 包括初始狀態和終止狀態。控制器內存有操作程序, 即指令序列, 用來驅動存儲帶
左右移動和控制讀寫頭的操作;
(2)存儲帶(輸入帶) : 它是一條可向兩端無限延伸的帶子, 帶上分成一個個方格, 每一方格可以存儲規定字元表中的一個字元, 也可保持空白;
(3)讀寫頭(帶頭) : 它能與存儲帶進行相對運動, 並對存儲帶進行掃描, 每次讀出或寫入一個字元。讀寫頭與控制器能進行雙向通信, 即接受控制器的指令, 並將掃描結果送到控制器。
圖靈機假想圖
因為圖靈機的理念和設計，艾倫圖靈與馮·諾依曼一同被成為「計算機之父」，而圖靈機的理論在計算機科學、邏輯學、語言學等各個領域都掀起了巨大的變革。
曾經有人質疑，憑藉這些有限且簡單的規則，和沒有任何情感的機器，可能做出什麼樣的成果？相對於它高昂的成本和繁瑣的設計，這一切或許都會顯得得不償失。但是，很顯然，今天你在這裡運用著圖靈機的智能手機，加入到圖靈機支持的互聯網路，看到我用圖靈機的筆記本電腦打出來的這些文字，就是打在這些曾經質疑者臉上最響亮的耳光。
References
[1]趙正平，圖靈機及其構造研究【A】.1009- 3044(2006)26- 0192- 03
[2]Michi Henning,Steve Vinoski, 徐金梧, 徐科, 呂志民, 等譯.Advanced CORBA
[3]Programming with C++(基於C++CORBA 高級編程)[M].北京:清華大學出版社,2000.
[4]趙致琢.計算科學導論［M].北京:科學出版社.2004．
-END-
TAG:ChangsView |