圖靈機的組成

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

這張圖片什么意思？這么一個簡單的機器/裝置怎么會所有電子計算機的理論模型？

圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，它運算過程看作下列兩種簡單的動作：

• 在紙上寫上或擦除某個符號；
• 把注意力從紙的一個位置移動到另一個位置；
  圖靈機把復雜的過程抽象成了上述兩個動作：讀寫和移動

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

一個無限長的存儲帶，帶子有一個個連續的存儲格子組成，每個格子可以存儲一個數字或符號

一個讀寫頭，讀寫頭可以在存儲帶上左右移動，并可以讀、修改存儲格上的數字或符號

內部狀態存儲器，該存儲器可以記錄圖靈機的當前狀態，并且有一種特殊狀態為停機狀態

控制程序指令，指令可以根據當前狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作（左移還是右移），并改變狀態存儲器的值，令機器進入一個新的狀態或保持狀態不變。

大家可以理解一下為什么圖靈機要由上面四部分組成。

當然這些只是理想的圖靈機，因為現實中不存在無限長的存儲帶。

總結

以上是生活随笔為你收集整理的什么是图灵机及图灵完备（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。