圖靈機(理解)

一、圖靈機的組成

網上有一張經典的圖片來表達圖靈機的構成,圖如下:

這張圖片什麼意思?這麼一個簡單的機器/裝置怎麼會所有電子計算機的理論模型? 相信大傢看到這張圖後都有這樣的疑問,下面筆者帶來由淺入深去理解圖靈機的組成。圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程,它運算過程看作下列兩種簡單的動作:

  • 在紙上寫上或擦除某個符號;
  • 把註意力從紙的一個位置移動到另一個位置;

邏輯結構上圖靈機有四個部分組成

  1. 一個無限長的存儲帶,帶子有一個個連續的存儲格子組成,每個格子可以存儲一個數字或符號;
  2. 一個讀寫頭,讀寫頭可以在存儲帶上左右移動,並可以讀、修改存儲格上的數字或符號;
  3. 內部狀態存儲器,該存儲器可以記錄圖靈機的當前狀態,並且有一種特殊狀態為停機狀態;
  4. 控制程序指令,指令可以根據當前狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作(左移還是右移),並改變狀態存儲器的值,令機器進入一個新的狀態或保持狀態不變。

當然這些隻是理想的圖靈機,因為現實中不存在無限長的存儲帶。圖靈是經過嚴格的數學證明,認為u這樣的一臺裝置,可以模擬人類所能進行的任何計算過程。下面,我們來看看圖靈機的計算過程。

二、圖靈機的運行機制

圖靈機工作步驟

  1. 準備

- 存儲帶子上的格子初始化;
- 設置內部狀態,存儲器當前狀態;
- 讀寫頭設置初始在存儲帶上所做的格子位置;
- 準備好控制指令,即控制程序。

赞(0)