什麼是圖靈機

以下圖來源網絡，如果侵權請聯繫我們刪除。

本文目錄：

什麼是圖靈

一個例子說明圖靈的運行原理

圖靈機有什麼意義

以下是正文：

1.什麼是圖靈機

1936年，英國數學家阿蘭-圖靈在《論數字計算在決斷難題中的應用》提出了「圖靈機「的概念。

根據他的論文造出來的圖靈機可能像下面的那樣：

來個高大上的，具體的感受一下

OK, 抽絲剝繭後是這樣的：

從上面的的圖看出圖靈機的基本結構：

兩個基本結構：存儲帶（紙條）和一個控制器

存儲帶在理論上是雙向無限延長的，他的上面由一個個的小方格成，方格裡面可以存一個數字或者字母。例如我們可以假設方格上面寫上1 ，如果沒有寫就認為就是0。

控制器：就是那個在紙帶上面的盒子。他不但存儲當前自身狀態，還包含一個讀寫頭，用來讀，寫和更改存儲帶上的方格的內容。然後這貨可以根據讀到的字母或者數字來變化自身的狀態，例如上圖的狀態是4，那麼下一次可能就會變成5了。所以存儲帶一格一格的左右移動時，可以更改紙帶上的內容和改變的自身的狀態。

細心的朋友已經發現在那個盒子上面有一張紙，其實上面就是最最最原始代碼了。那麼它到底是什麼東西，請往下看！

2.一個例子說明圖靈的運行原理

看一下下面的圖，把圖靈機再進行一些抽象。

上面是紙條，左邊就是那個讀寫頭，下面是我們的代碼

除了圖右邊的描述補充一下，R L H分別代表右，左，和不動

現在我們來運行一下：

它先讀取當前的自己狀態q1和當前紙帶數字1,然後看一下我們的規則，q1 和 1對應第一條，這時控制器應該在紙帶寫下1,所以紙條內容沒變。然後向右移動一個位置，同時改變自己的狀態為q1，依然沒變。成下面這樣：

接下來重複上面的過程.想像一下機械運動，例如火車運動。然後來到那個沒有數字的紙帶格子。

這個時候有些不一樣了，根據當前狀態和讀取的紙帶的內容，它要改變紙帶內容為1,向右移動一個位置的同時把自己的狀態變為q2.然後它向右移一位，接下來的過程可以自己在腦中分析一下。

最後我們看一下下面兩張圖：

第一張圖是執行了最後一個有數字的格子之後的情況：

現在他要向左移動一個位，變成了第二張圖的情況，往下看

然後，在執行對應的語句後，把1擦除後停留在當前位置，最後一直停留在那裡。

發現了嗎？這就是停機了。。。。。

其實上面的程序到底幹了什麼：如果我們把1111當成4,111當成3,那麼結果就是4+3=7(1111111)。

下面總結一下運行過程：

循環開始：

（1）讀寫頭讀出存儲帶上當前方格中 的字母/數字；

（2）根據 自身當前狀態 和 所讀到的 字符，找到相應的程序語句；

（3）根據 相應程序語句，做三個動作： ① 在當前存儲帶方格上寫入一個相 應的字母/數字； ② 變更自身狀態至新狀態； ③ 讀寫頭向左或向右移一步；

循環結束:

3.圖靈機的意義

圖靈機給出了一種指定輸入，然後就可以得到恆定的輸出的計算模型。

基本上就是一個虛擬的"計算機"，而在當時提出來的"萬能圖靈機"就是現代計算機最原始的模型，它可以在紙帶上存儲數據和程序。三年之後，在1939出現了採用二進位的第一臺電子計算機。

最後，圖靈好帥啊～～～～

熱愛生活，享受娛樂，專注技術，歡迎關注QGer