算法系列教程03 - 人人都能懂的圖靈機原理
上一講我們知道了圖靈機在歷史上出現的原因，它是一個計算模型，用來判定一個問題到底可不可解，那麼它是如何判定的呢？
在本篇文章開始之前，我們先來看一段視訊：
視訊來源： ofollow,noindex" target="_blank"> YouTube (經下載後上傳到騰訊視訊)
圖靈機的構成
為了方便講述圖靈機的構成，我從視訊中截取了一張圖：
視訊中的圖靈機是用現代工藝做的，可以看到圖靈機並不複雜，它做的事情很簡單。當機器處於“Read”狀態的時候，會從紙帶上讀內容，完了經過某種計算再向左或向右移動，然後在當前位置寫上符號 0 或 1（如果已經有符號會先擦除），下面有個狀態(State)會變化，另外還顯示了當前的位置(Position)和步數(Step)。
從上面圖中我們可以看到，圖靈機就是一個機器（稱為控制器）和一根紙帶組成的。
控制器 ，包含用來寫內容的“筆”、“擦子”。它可以向紙帶讀、寫、改資料，所讀內容我們可以理解為程式語句；它可以使紙帶左右移動；它還有一個可以變換的狀態。
紙帶 ，左右兩邊無限延長，紙帶上可以寫內容（也就是儲存），內容可以是數字和字母。我們可以把紙帶理解為儲存器。
我們再來看看圖靈機是怎麼工作的。
圖靈機執行原理
首先圖靈機工作前，需要先在紙帶上寫好一些符號，例如“1 1 0”：
加粗的方格表示當前控制器筆頭指向的位置。現在我們編寫一段簡單的程式，這段程式用表格表示是這樣的：
| 讀取 | 寫入 | 移動 |
|---|---|---|
| 空白 | 無 | 無 |
| 0 | 1 | 向右移 |
| 1 | 0 | 向右移 |
這個程式很容易理解，比如表格的第三行（即最後一行），意思就是當程式讀取到 1 時，在當前位置寫入 0，再向右移動一格。假設我們已經把這段程式輸入到機器中了，然後機器開始運作。
首先機器讀取紙帶當前的符號，如上面的紙帶圖，讀取到的是“0”，匹配程式表的第二行，按照程式的指示，應該在當前位置寫入“1”再向右移一格，過程如下兩個紙帶圖所示：
機器繼續讀取當前位置的符號，讀取到的是“1”，匹配程式表的第三行，然後按照程式的指示在當前位置寫入“0”，再向右移一格，這一步圖示如下：
依此繼續執行，最後一步圖示如下：
最後讀取到空白時，按照程式的指示，既不寫也不移動。事實上這個程式並不完整，還存在問題，例如怎樣才能讓機器停止，又如何讓機器不停地重複讀取、寫入和移動的過程呢？
我們還要在程式中加入狀態，控制器必須要有記錄狀態的功能。為什麼一定要加入狀態呢？因為如果沒有狀態的話，在紙帶有限的符號下，程式表只能是有限的行數。比如示例中的紙帶有三種符號：0、1 和空白，那麼程式表最多也就只能是三行，機器最多隻能執行三種可能的動作。加入狀態後，假如狀態有 0 或 1 兩種，那麼程式表的行數就可以增加到 2x3=6 行，這稱為 3 符號 2 狀態圖靈機。
例如下面是一個含有兩種狀態的程式表：
| 當前狀態 | 讀取 | 寫入 | 移動 | 修改狀態 |
|---|---|---|---|---|
| 0 | 空白 | 空白 | 向左移 | 1 |
| 0 | 0 | 1 | 向右移 | 1 |
| 0 | 1 | 0 | 向右移 | 0 |
| 1 | 空白 | 空白 | 向右移 | 停止 |
| 1 | 0 | 1 | 向左移 | 1 |
| 1 | 1 | 0 | 向左移 | 1 |
機器每一步需要結合當前的狀態再來執行相應的操作，所以在機器執行前，需要有個初始狀態。機器執行完一步後，按照指示修改狀態，以備下一步使用。
假如機器的初始狀態為 0，繼續使用上面最後一步的紙帶，當前指向的是空白，那麼匹配的是表格的第一行，按照程式指示，在當前位置寫入空白，並向左移一格，圖示如下：
依次類推，後續步驟的圖示如下：
一步步這樣匹配演示下來，上圖對應的最後一步是向左移一格後指向了空白，狀態變為了 1（匹配的是第五行）。此時，繼續執行，當前位置是空白，當前狀態是 1，那麼匹配的是表格的第四行，向右移一格，狀態變為停止，如下圖示：
這樣圖靈機就完成了一次計算。紙帶由“001”通過給定的程式計算變成了“110”，如果把它們看成二進位制的話，其實是做了一次 1+5=6 的運算。
隨著控制器狀態增多，那麼我們就可以編寫越複雜的程式，也就能和現代計算機一樣執行復雜的演算法。
好了，知道了圖靈機的執行原理，我們再回到開篇提到的問題，既然說圖靈機是一種計算模型，那麼它怎麼來判定一個問題有沒有解呢？
圖靈機停機
如果圖靈機成功完成了一次計算，我們就說圖靈機 成功停機 了。 停機 就意味著計算結束並得出結果，停機後紙帶上的符號就是計算結果。
當我們遇到一個問題，比如說輸入 A，問：能否由 A 計算出 B？圖靈機能幫我們做一個判定，如果我們能在 A 與 B 之間找到或設計出一個圖靈機程式，使輸入 A 停機得到的結果是 B，就說明這個問題可解，否則就說明這個問題不可解。
圖靈機就是這樣解決“可計算性的判定”問題的，這是圖靈機的一個重大意義。另外，我們可以看到圖靈機給出了一個可實現的通用計算模型，還引入了儲存器、程式、控制器等概念的原型，為現代計算機奠定了基礎，這也是圖靈機為什麼受到人們重視的原因。
參考：
https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html