非數學，非計算機專業的我，對編程什麼的一竅不通的我要怎麼理解圖靈機的概念？

01-01

圖靈機其實是個非常簡單的玩意兒，和「掰手指數數」是一個性質的。認真看書就明白了，別胡思亂想。

先問一個問題，你認為「計算」是什麼？

比如說，掰手指計數，左手伸4個手指，右手伸3個手指；然後把雙手所有伸出的手指數一遍，7個。

很好，這就是個「用『手指計算器』算3+4=7」的案例。

類似的，算盤每根柱子代表一個十進位位；然後一根柱子被木格分到上邊的一個珠子代表5、下邊一個珠子代表1。

就好像掰手指數數一樣，上邊撥下來一顆珠子，這是伸出了5根手指；下面撥上去兩個珠子，這是伸出了兩根手指——不進位加二對應的口訣是二上二，於是5+2=7。

如果在這個基礎上再加8呢？怎麼算7+8？

7加8要進位，對應的口訣是八去二進一，翻譯過來是「加八相當於先加十後減二」，即當前位撥下兩顆珠子，高位撥上一顆珠子，答案就擺在算盤上了（習題：如果是3+3這樣超過5但不足10的，你認為應該如何撥珠子？如果前面說的你真理解了，自己三下五除二就能搞出個口訣來）。

珠算口訣_百度百科

嗯，別研究珠算了。也別著急研究機械計算機。它們都不是關鍵。你越往裡鑽，反而會離真理越遠——能像圖靈一樣，先鑽進最複雜的機械結構（機械加解密機）然後再把它化簡成掰手指的，實在太少了。

偉大的圖靈已經幫我們抓住了關鍵，從最容易的來就足夠了。

讓我們盡量忘掉細節，告訴我，「計算」這個動作究竟是什麼？

從掰手指、玩算盤、撥機械計算器的數字輪的經驗，我們知道了：計算就是一些機械的操作步驟，按機械的規定機械的執行這些步驟，我們就可以得到某個輸入的計算結果。

太啰嗦了。廢話能更少點嗎？

嗯……計算動作……就是通過一些機械動作，把問題映射到答案的操作過程。

嘶~~這個定義字數倒是少了，但怎麼成天書了？

你這樣想：3+4是問題集合的一個問題；7是答案集合的一個答案；算3+4就是通過一些機械步驟（1、左右手分別伸出3和4根手指；2、數一數一共伸出了幾根手指），然後找到了7，對吧？

你看，完全不需要什麼「智能」，按死規矩來就行了。

仔細想一下，看看各種計算，從加減乘除到乘方開方積分求導……甚至加密解密……是不是都可以這麼看？

問題/原始數據/密文 ---&> 答案/密文/原始數據

很好，既然一切計算歸根結底都可以是機械過程，那麼有沒有什麼機械過程可以模擬一切運算呢？

你看，擺手指頭、算盤、機械計算機，它們的確可以幫我們做一些運算；但它們只能做特定種類的那些運算：有沒有可能弄出一個「可以幫我們做任何運算」的機器呢？

————————————————————————————

還是繼續玩簡單粗暴的：計算，其實不就是「一系列從問題到答案的映射步驟」嗎？

那麼，隨問題不同而各不相同的「映射步驟」本身，可以用不太多的幾條「萬能映射步驟」來映射嗎？

圖靈說了，可以。

我們可以做一個機械裝置，它可以：

1、從紙帶讀入內容或輸出信息到紙帶上（紙帶是無限長的）

2、移動到紙帶上的其它位置

3、有一套控制規則和一個內部狀態寄存器；可根據狀態寄存器內容以及當前紙帶格子里內容，決定下一步動作（在紙帶上移動、讀取/寫入內容或停機等）

這就是一台圖靈機。

其中，「控制規則」就是「映射步驟」（類似珠算口訣、機械計算器操作動作等），「內部狀態」就是黑板/演草紙上面的內容（或者算盤珠的擺放狀態、伸出的手指）；而「紙帶內容」就是要解決的問題以及輸出答案的地方——和人們掰手指或手工演算一模一樣。

然後呢，問題雖然是無限的；但解答某個問題需要的「控制規則」的數目是有限的，所以這些「控制規則」總可以編碼然後存到紙帶上。

我們可以給每個不同的控制規則一個編號，比如M。（標準術語體系里，控制規則M被稱為「圖靈機M」。個人認為這容易造成混淆，故這裡杜撰了個「控制規則M」）

圖靈證明了，可以設計一些特殊的控制規則，使得它控制下的圖靈機可以讀入任意的控制規則M，然後仿照控制規則M去處理紙帶內容。

換句話說，這些特殊的控制規則，就是一套「可以模擬其它任何映射步驟的映射步驟」。即所謂的「通用控制規則」（標準術語叫「通用圖靈機」）。

「通用控制規則「並不需要多複雜。事實上，最簡單的那些……簡直簡單的令人髮指。

說的更淺顯一些，就是：支持「通用控制規則」的圖靈機，不管它看起來有多簡單，但它的確就是一種萬能機器。

既然組成「通用控制規則」的規則並不需要多少，更不需要很複雜。那麼，搞出來一種「萬能解題機」就不困難。

很快，在圖靈理論的指導下，人類第一台計算機出現了。

——————————————————

現代計算機就是一種高度複雜化了的圖靈機——雖然高度複雜化了，但圖靈機該有的，它一概不缺：比如紙帶（用內存/磁碟模擬）、內部狀態寄存器（現代計算機有大量的標誌位和大量的寄存器甚至寄存器組）、在紙帶上移動（各種跳轉指令、各種複雜的定址操作）、控制規則（CPU指令集），等等。

至於程序員……其實就是藉助CPU指令集甚至某種高級語言（通用控制規則），為某個具體問題設計解題步驟的（控制規則M，或者……notepad.exe、qq.exe等等）——然後CPU按照程序員給出的步驟1、2、3、4做下去，問題答案就出來了（當然，要是某些步驟沒設計好、某些特殊情況沒考慮到……先生，你編的bug誕生了）。

比如說呢，前面提的那個「給算盤設計一條珠算口訣」問題，其實就是程序員日常工作（的一部分）了——都是「為某個問題設計機械解決步驟」嘛。

你可以回想一下乘除法的運算規則，然後仿照我前面提到的「步驟思想」，設計一套珠算口訣來。相信我，你可以的——設計出來後，記得到算盤上Debug哦。

如果你能搞定「自製算盤口訣」，就說明閣下骨骼精奇，定能把碼農大業發揚光大：這本祖傳的《編譯原理》，你掏100，就白送給你了-_-|||……

——當然，如果你連加法口訣都沒法補全……那麼閣下很可能並不適合吃程序員這碗飯：理所當然的，這篇文章……你應該也看不懂。

總之，圖靈機就是現代計算機的終極簡化版；除了最核心的計算原理，其它的一概沒有。

顯然，如果真正理解了圖靈機的計算原理、再從它開始來理解現代計算機工作原理，那是最簡潔最容易不過的了。

只是各種教材/書籍大概都有點"祖師爺崇拜"情結，這才把它講的晦澀難懂撲朔迷離……

《邏輯的引擎》

圖靈機實際上是抽象的模擬人在紙上算算數的一個過程：

你有一隻鉛筆和一塊橡皮。

有一個無限長的紙帶，紙帶被劃分成了無數段，每一段上面都有一個字元。

現在想像自己是個傻子記憶力有限，並且只能注意到紙帶上的某一段上面的字元。

你的腦子記住了一組數量有限的規則，除了這些規則你還知道自己的思維處於什麼狀態。

這一組規則告訴你：當你看到某個字元並且當你的思維狀態是什麼的時候，你應該幹啥。

規則要求你乾的事情通常是這樣：

1.忘記這個字元，看這個字元左邊的字元。

2.忘記這個字元，看這個字元右邊的字元。

3.把你看到的這個字元擦掉，換成另外某個字元。

4.洗洗睡吧。

5.或者其他。

一定要記得自己是個傻子，你只能注意到紙帶上的某一個字元的位置。而且那一組規則的數量是有限的，你不可能忘記，但也不可能學習新的規則。規則沒告訴你洗洗睡的時候堅決不能洗洗睡！

那麼，你就是一個圖靈機！

本文從圖靈機的基本概念到神經圖靈機，再到可微分神經計算機做了介紹，在這裡可以作為該問題的參考，希望對理解這個概念有所幫助。

參考視頻：Daniel Shank：神經圖靈機_騰訊視頻

圖靈機就是一種簡單的計算機模型。正如現代計算機一樣，其思想中也包含了一個外部存儲器和某種處理器。本質上，圖靈機包含上面寫有指令的磁帶和能夠沿著磁帶讀取的設備。根據從磁帶上讀取到的指令，計算機能夠決定在磁帶上不同的方向上移動以寫入或者擦除新符號等等。

神經圖靈機則是一種神經網路，但是它從圖靈機中獲得靈感來嘗試執行一些計算機可以解決得很好而機器學習模型並不能很好地解決的任務。本質上，它包括一個神經網路控制器（controller）、讀取磁帶設備的模擬器或處理器，如果你願意的話，還可以加上外部存儲或記憶（memory）。它在所有讀取到的輸入上都是持續的。就像長短期記憶（LSTM）網路或者其他相關的模型一樣，它是一個循環神經網路（recurrent neural network）。這意味著，像我們大多數人熟悉的一樣，它讀取類似變數的輸入，但是，神經圖靈機和圖靈機也有不同之處：除了有一個記憶/內存之外，神經圖靈機也可以接受一連串連續的輸入並提供輸出。

這裡的關鍵思想是神經圖靈機基本上就是可微分的圖靈機，要麼是 0 要麼是 1：計算機在「非此即彼」的邏輯或者整數中運作。然而大多數的神經網路和機器學習實際上不是這樣的，它們使用實數，使用更加平滑的曲線，使得它們更加容易訓練，這意味著，在看到它們的輸出時，你可以輕易地通過輸出追蹤回去調整參數以得到希望的輸出。當計算機 CPU 儘是諸如異或門（XOR）和與門（AND）等跳變函數時，這是非常難以實現的。神經圖靈機採用了基本的圖靈機中的所有功能找到了平滑的模擬函數。因此，比如在磁帶上，神經圖靈機可以決定稍微向左或者向右移動，而不是單純的向左或者向右，這可以讓你完成一些了不起的事情。

但是缺點是它只能夠學習簡單的演算法。例如接受輸入並複製它。這看起來是極其平常的，但是對當前的神經網路來說，這實際上是一件非常困難的事情，因為神經網路需要學習出一個演算法才能把這個工作做得足夠好。神經圖靈機能夠接受輸入和輸出，並且學習得到能夠從輸入映射到輸出的演算法。這確實相當令人興奮，因為這本質上是在嘗試著取代程序員。雖然我們還未實現，但是這的確很酷。這意味著一旦習得了演算法，它們可以接受輸入並且外推到基於該演算法的任何變數輸出。接下來你會立即明白這為什麼很酷。因為它們還非常擅長語言建模（language modeling）。如果你不知道什麼是語言建模，你可以思考一下自動完成（autocomplete）。語言建模就是猜測一個單詞在句子或者文檔語境中的意思。神經圖靈機也能夠在 Facebook 的 bAbI 數據集上表現得很有前景，bAbI 數據集是被設計用來鼓勵研究者們提升神經網路的通用認知推理能力的。

這是一個神經圖靈機執行複製/重複任務的例子。它已經學會了接受相對短的序列，並重複幾次。正如你可以在上圖看到的一樣，開始的時候它犯錯。

相反，你拿這個例子與長短時記憶網路（LSTM）相比，LSTM 實際上是一種非常強大的神經網路模型。它們會很快就傾向於崩潰。出現這種情況的原因是，LSTM 確實是在學習一些東西，但是它們並不是在學習演算法。LSTM 試圖一次解決整個問題，所以它們意識不到前兩次所做的事情就是它們之後應該做的。

在神經圖靈機可以做到的事中，一個有趣的例子是它們可以識別平衡的括弧。這個是特別有趣的，因為這涉及到的使用了棧（stack）的演算法，所以本質上你可以隨著左括弧的進入去跟蹤它們，然後嘗試去匹配與之對應的右括弧。這件事神經網路可以做，但是會以更加統計的方式完成，而神經圖靈機實際上可以像人類程序員一樣去完成這個任務。

神經圖靈機可以做這些炫酷的事情：它們可以學會演算法，它們可以理解一個小故事的意思，但是為什麼我們不能一直用這些東西呢？嗯，它們的結構是如此地有趣，但也伴隨著一些問題。

問題：

架構依賴；
大量的參數；
並不能從 GPU 加速中受益；
難以訓練

首先，一旦你指定了一般的架構，在實現它的時候仍然需要做出很多決策。例如，對於每一個給定的輸入或輸出單元，在給定的時間步長下你能夠讀取或者寫入多少向量？這些都很重要，它不僅僅是提高你的識別準確率的問題。如果你不能正確地做到這些，那它很有可能永遠都得不到一個合理的結果。參數的數量是極其大的，這會讓你的 RAM 壓力很大。這是機器學習中的一個重要部分，它們並不會受益於 GPU 加速，雖然正如我們所見，GPU 加速是機器學習中的重要一部分。原因是這是序列式的，很難並行化，因為它們當下所做的都是基於之前的輸入。很難將這些部分分解成容易的並行計算。它是很難訓練的，這一點和我剛才提到的所有問題都有所不同。

難以訓練：

數值不穩定性；
很難使用記憶（memory）；
需要很好的優化；
實際中很難使用

它們往往具有很強的數值不穩定性。部分原因是實際中給它們設計的任務。因為它們是在學習演算法，所以它們往往不會犯小錯誤，它們傾向於犯大錯誤。如果你在演算法中犯了一個錯誤，那麼所有的輸出結果都會是不正確的。這意味著，當你訓練它們的時候，它們總是很難找到需要的演算法。如果餵給大量的數據，給予足夠的時間，大多數神經網路都會得到一些結果。而神經圖靈機經常會卡住。大家知道，它們經常一遍又一遍地一味地產生那些經常重複的值。這是因為使用記憶是很困難的。他們不僅必須學會記住以後解決問題所需要的東西，還必須記住不要意外地忘記它，這一層要求額外地增加了複雜性。因此，為了解決這個問題，你最終會用一些循環神經網路通用的巧妙的優化方法。但是為了讓這些方法起作用，你需要想盡一切辦法。所有的這些問題都讓神經圖靈機很難用在日常應用中。

圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：在紙上寫上或擦除某個符號；把注意力從紙的一個位置移動到另一個位置；而在每個階段，人要決定下一步的動作，依賴於此人當前所關注的紙上某個位置的符號和此人當前思維的狀態。

為了模擬人的這種運算過程，圖靈構造出一台假想的機器，該機器由以下幾個部分組成：

1、一條無限長的紙帶，被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號表示空白。紙帶上的格子從左到右依此被編號為 0,1,2,... ，紙帶的右端可以無限伸展。

2、一個讀寫頭，可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，並能改變當前格子上的符號。

3、一套控制規則，它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，並改變狀態寄存器的值，令機器進入一個新的狀態。

4、一個狀態寄存器，它用來保存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的，並且有一個特殊的狀態，稱為停機狀態。

注意這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，因此這種機器只是一個理想的設備。圖靈認為這樣的一台機器就能模擬人類所能進行的任何計算過程。

開始的時候將輸入符號串從左到右依此填在紙帶上，其他格子保持空白（即填以空白符）。M 的讀寫頭指向第 0 號格子，M 處於狀態 q0。機器開始運行後，按照轉移函數 δ 所描述的規則進行計算，然後將讀寫頭向左移動一個格子。若在某一時刻，讀寫頭所指的是第 0 號格子，但根據轉移函數它下一步將繼續向左移，這時它停在原地不動。若在某個時刻 M 根據轉移函數進入了狀態 qaccept，則它立刻停機並接受輸入的字元串；若在某個時刻 M 根據轉移函數進入了狀態 qreject，則它立刻停機並拒絕輸入的字元串，對於某些 q,x， δ（q,x) 可能沒有定義，如果在運行中遇到下一個操作沒有定義的情況，機器將立刻停機。

馮·諾依曼率先提出，在計算機上實現類似生物細胞的效用，以研究自組織現象，即細胞自動機（cellular automata）模型，這是圖靈機的進一步發展，它能方便地模擬吸引子，自組織和混沌現象。

圖靈機其實原理不是那麼特別難理解，所謂的圖靈機就是指一個抽象的機器，它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態，還有一些固定的程序。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然後結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，並轉換自己的內部狀態，然後進行移動。

圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：1.在紙上寫上或擦除某個符號；

2.把注意力從紙的一個位置移動到另一個位置；

而在每個階段，人要決定下一步的動作，依賴於此人當前所關注的紙上某個位置的符號和此人當前思維的狀態。

那就先了解編程。

如果不知道元素周期表，研究鐵碳合金的性質又有什麼意義。

不需要理解，圖靈機就是一穿孔紙帶初級計算機。當年沒計算機，圖靈只好構造了這麼一個玩具

《圖靈的秘密》

圖靈機分為通用圖靈機和專用圖靈機，專用圖靈機相當於固定的程序代碼，通用圖靈機相當於解釋器，專用圖靈機當然需要通用圖靈機來解釋執行。一般說圖靈機就是在說通用圖靈機。

圖靈機真的沒啥高級的，它就是一個解釋器、一個構造簡單而又邏輯確定的解釋器，然後圖靈說這個解釋器能進行任何計算。

王垠說圖靈機名過其實，我認為還是很有道理的：圖靈的光環

圖靈機提供了一種簡化了的，抽象了的計算工具模型，使演算法成本的度量能夠拜託具體的演算法實現基礎，如人、硬體等因素，使演算法時間成本的計算轉化為基本操作的次數，各種演算法的成本有了更好的比較基礎。另外對初學者來說可能在觀念上起到一定的作用，使程序員能夠拜託硬體基礎的束縛，以這一計算機模型為基礎去集中於程序設計，而不用計較具體的硬體實現機制。

你可以看看這裡http://www.aturingmachine.com/的介紹

圖靈機，其實就是說，如果一個機器有 if 和 goto ，就可以實現任何功能。

我覺得其實圖靈機不是很難理解，不能理解的應該是圖靈機為啥這麼重要。

最開始大家都不知道計算機設計成什麼樣才能工作，圖靈機在理論上為計算機的發展指明了一條正確的方向，只要滿足圖靈機，計算機就一定能工作。

遞歸大法好，遠離圖靈機。

和一個無限算盤一樣僅此而已

私信輪子哥，讓他親自傳授你，不過可能不免費（笑）

把自己想像成一個聽話的白痴，按照書上說的步驟去模擬幾次，不要嫌累……

給你一個 &< 30 RMB 的計算器 + 紙筆，並且告訴你怎麼算一個東西。然後只要別人用任何方式推算出來的問題，你也一定可以推算出來