為什麼有了 遞歸, select-case, 約定數據結構(數組) 就可以證明圖靈完備？ 另為什麼遞歸如此重要？

看了一些編譯的知識，寫過關於編譯的項目，看了王yin, vczh的博客。 對其中的 "程序語言設計" 很感興趣。 在設計編譯器指令的時候，用到了 mov類，計算類，跳轉類指令，就可以完成很多很多的功能了。提出這個問題就是想把這部分用到的指令與遞歸，圖靈完備等理論聯繫起來

---

能用來模擬一個圖靈機就能證明圖靈完備。常見的兩種編程模型，一種支持可變存儲（變數，內存），一種支持遞歸，都是圖靈完備的。圖靈機基本來說是需要一個有狀態的自動機，加上一條可以隨意讀寫的無限長紙帶，對於支持可變存儲的計算模型來說，可變的存儲可以用來模擬這條紙帶以及狀態機的狀態；對於純函數來說，沒有變數，所以只能通過遞歸來記錄狀態，每一層遞歸可以接受三個參數，分別表示自動機狀態、紙帶讀寫頭左側內容、紙帶讀寫頭右側內容，然後通過尾遞歸來循環下去，就可以模擬圖靈機了。

---

其實你會發現，遞歸、select-case（如果你說的是我理解的那個意思）、約定的數據結構（數組）等等這些東西都不需要，只要一個Lambda calculus就夠了。

至於為什麼遞歸如此重要，肯定是因為遞歸很重要嘛。

---

圖靈機是一個自動機（狀態有限）+無限長的紙帶。約定數據結構很明顯對應紙帶。select-case應該對應自動機狀態的轉移，這裡需要用if進行選擇。至於遞歸，自動機是沒記憶性的，記憶是在紙帶上，因此就有了遞歸。意思是在自動機上走了一步後，可以看成是最初的問題，只是起點不一樣了，還是在用相同的代碼選擇下個狀態。總體來說遞歸就是一種子問題的感覺。

圖靈完備的東西其實特別多的，有些也算是意想不到，例如 Rule 110，Conway"s Game of Life。

---

一個問題是不是可以計算就是以是否可以規約成一個遞歸問題或是一個基礎問題來衡量的，當然遞歸的底層也是一個基礎問題。關於可計算問題有一些相關的數學證明可供參考。

-----2014-12-02更新-----

我來填坑了。

• 美國數學家阿隆佐·邱奇創建了稱為λ演算的方法來定義函數
• 英國數學家阿蘭·圖靈創建了可對輸入進行運算的理論機器模型，現在被稱為通用圖靈機
• 邱奇以及數學家斯蒂芬·科爾·克萊尼和邏輯學家J.B. Rosser一起定義了一類函數， 這種函數的值可使用遞歸方法計算

以上是維基百科在邱奇-圖靈論題這一詞條下給出來的三種函數，我們普遍認為能用這三種函數表達出來的函數都是可以計算的，當然，到目前為止這都還只是一個猜想。

這裡面涉及了兩個非常重要的概念「可計算」和「可演算」，可計算是指能用機械的方法得到結果的性質，而可演算這一概念就比較黑科技了，只要是可行的步驟都可以算是可演算的。比如說我們可能靈光一現想到用某些物理方法解決一些數學問題，人類當然是可以這麼腦洞大開的，但是對於機器來說這些沒有明顯聯繫的東西它沒有能力聯繫起來，也就是說對於機械來說它並不能採取這樣的手段來解決問題。

但是圖靈-邱奇論題提出「可有效演算的問題都是可計算問題」，這表示了一個非常不符合直觀認知的事情，也就是說確定性圖靈機和非確定性圖靈機的計算能力是等價的，到現在我也沒法從直覺上接受它=_=。

關於如何界定可有效計算的問題，邱奇在《A Note on the Entscheidungsproblem》一文中，用lambda和遞歸函數對可有效計算這一概念進行了描述，題主可以看看，數學性比較強，讀起來其實有點難度的。

關於圖靈機的計算能力問題呢，我們可以認為它是一個自動機，可以計算所有我們目前定義的所有可計算問題，與之等價的計算模型還有lambda演算等等。只要是計算能力與圖靈機等價（也就是可以計算所有的可計算問題）的計算模型，我們都稱之為圖靈完備。lambda演算模型的圖靈完備性是被圖靈自己證明的，話說邱奇算他師叔？

實際中也存在不可計算的問題，最著名的是圖靈機模型上的停機問題，在此之前邱奇還發現了lambda等價問題也是不可計算的，此外還有海狸很忙問題等等。

可計算性問題是一個非常抽象複雜的問題，就算是邱奇-圖靈論題也只是一個被普遍接收的假想（就像哥德巴赫猜想一樣），如果題主對此感興趣，不妨看看邱奇在這方面的研究，從數學角度感受一下。我對此也不是完全理解，比如那兩個難以接受的等價圖靈機=_=，還是要直接從前輩那裡汲取營養。

先想到這裡，說不定什麼時候想起來再填坑。

---

推薦閱讀：