你可能永遠都搞不懂了圖靈機了！
程序員都知道圖靈機，但是卻不一定能搞懂它，不一定理解它爲什麼這麼厲害。
原因就是：圖靈機太簡單了，太數學了， 太抽象了。
1
我剛上大學的時候，有個社團叫 “圖靈學社”，當時我還納悶，圖靈是誰？
我就跑到圖書館去查書：哇，圖靈原來是我們的祖師爺啊，我們全靠他賞飯喫。
等等，這圖靈機是什麼玩意兒，一條紙帶，一個讀寫頭，一個控制器， 這也太簡單了吧。
現在的電腦有漂亮的界面，豐富的操作，有視頻，圖片，聲音。
編程中有虛擬機，各種框架，併發模型，設計模式，面向對象，泛型，函數式，閉包。
這麼複雜的東西，怎麼可能歸結到如此簡單的圖靈機中？這不是癡心妄想嗎？
3
這還真不是癡心妄想。因爲計算機使用的二進制數字可以表示一切！
先說圖像。
圖像有兩種存儲方式，一種是位圖，一種是矢量圖。
位圖相當於把整個圖像分解成一個個小的像素，每個像素都有顏色，這樣就可以用二進制數字表達了。
就像下面這張笑臉圖：
（可以看出圖像放大以後就出現鋸齒了。）
而矢量圖相當於記錄下了一個圖像的幾何信息。
比如一個圓，只要知道
-
圓心
-
半徑
-
繪製時的線型和顏色
就可以把他復原了， 很明顯，這些數據也可以用二進制表示。
視頻則是一幀幀的圖像組成，既然圖像可以用二進制表示，那視頻肯定也沒問題。
聲音也是類似的，本來是連續的，但是電腦會對他進行採樣（比如每秒採樣 44100 次），變成離散的，就可以用二進制表達，存放到電腦中了。
（音頻信號也出現鋸齒了，因爲數據是離散的，不是連續的了，不過只要採樣頻率高，人的耳朵分辨不出來）
所以，**視頻，圖像，文本，聲音都可以用二進制來表達，然後寫程序對他們進行處理就行了。 **
至於各種語言編寫的程序，無論是系統級的操作系統，還是應用層的 Web 網站， 最終都要歸結到賦值，順序，循環，分支這些最基本的結構。
如果你不相信，可以看看我之前寫過幾篇的文章：
《編程語言的巔峯》
所以只要圖靈機能表達這些最基本的結構，一切問題就都解決了。
3
本文的重點終於來了， 圖靈機如何去表達這些基本的結構呢？
進入燒腦環節，強烈建議找一塊兒安靜的時間來閱讀。
（其實做爲一個程序員，多用腦子是好事，不要一遇到難點兒的東西就逃了，那樣怎麼會進步和成長呢？）
我們先從一個極其簡單的編程語言來熱身， 這個語言只有三條指令
- 遞增
incr(X)
- 遞減
decr(X)
- 循環
while(X){
decr(X)
// 做一些事情
}
別小看這三條指令，從它們出發，可以組合出很多新的指令，可以把這些指令稱爲宏。
這些宏一旦建立，可以再次被組合使用
第一個宏： 把一個變量 X 的值清 0，記做 X <--0
while(X){
decr(X)
}
第二個宏： 給一個變量賦值，記做 X <-- n
X <-- 0 // 複用第一個宏
incr(X)
incr(X)
incr(X)
.....
incr(X) // 重複 n 次，不要嫌囉嗦，計算機最適合，最擅長幹這種重複的事情
第三個宏：把 X 的賦值給 Y ，記做 Y <--X
Y <--0 // 利用第二個宏
while(X){
decr(X)
incr(Y)
}
第四個宏：實現 if 語句 ，記做 if X then A
// 注意，X 的值只能是 0 或者 1
while(X){
decr(X)
A
}
實際上，只要你願意，還可以組合出各種各樣的新指令
Y <--- Y + X
Y <--- Y * X
......
只不過需要花費更多的指令罷了。
也就是說這個簡單的語言能實現上一節所說的賦值，順序，循環，分支等基本結構。
那如果圖靈機和這個簡單語言也是等價的，那圖靈機肯定能實現賦值，順序，循環，分支了，對吧？
4
接下來我們把目光轉向一個 “寒酸” 的圖靈機， 讓它來實現 decr(X), incr(X), while(X)
這個圖靈機的磁帶上只有空白（b）和字符 (1) 兩種選擇
兩個空白之間有多少個 1 就表示數字是多少，例如有 4 個 1 表示 4， 10 個 1 表示 10
下圖就表示數字 7
就是這麼簡單粗暴！
磁帶上的讀寫頭總是指向磁帶上的一個符號（當前符號），讀寫完成以後，它可以左移，右移或者呆那兒不動， 這依賴於控制器中的指令是什麼樣子的。
最重要的是那個控制器，相當於現代的 CPU 了，它是一個有限狀態的自動機，可以在有限的狀態中根據輸入轉入另外一個狀態。
我們現在試試用這個 “寒酸” 的圖靈機來實現 incr(X) ：對 X 加 1 。
爲了方便說明，假設 X 爲 7， 讀寫頭初始狀態位於最左端的空白處
是不是很簡單？
當然，這裏可以用有限狀態機來描述，爲了降低理解負擔， 我用大白話來說了。
想實現 decr (X) ，就更簡單了， 我們把剛纔的 X=8，減去 1
首先讓讀寫頭右移，遇到 1，把它變成 b ，停止就行。
循環要稍微複雜一點兒，仔細看好了。
假設 X = 3，循環是這樣的
while(X){
循環體
}
三種基本的運算實現了，現在我們可以說：
簡單圖靈機 <--> 簡單語言 <--> 複雜的語言
好了，證明完畢！不知道你暈了沒有。
其實這根本不是證明，就是希望大家能感受下圖靈這麼簡單的機器，也有着強悍的能力，就是實現起來比較費勁罷了。
後記：本文的簡單語言和圖靈機的例子來源於佛羅讚的《計算機科學導論》，這本書相當不錯，推薦！
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/aWtV9tYTMGSh2hLKXdacuA