圖靈機是一個由數(shù)學家圖靈在1936年構想出來的虛擬的機器鸳劳，這個機器的偉大之處在于:
它非常的簡單，但是它可以模擬任何的計算機程序。
它的結構
- 一條存儲帶
- 雙向無限延長
- 存儲帶上有一個個小方格
- 每個小方格里面存儲一個符號(數(shù)字骂铁、字母等等)
- 一個控制器
- 可以存儲圖靈機當前自身的狀態(tài)
- 包含一個讀寫頭，可以讀罩抗、寫存儲帶上方格里面的內容
- 可以根據(jù)督導的符號，改變自身的狀態(tài)
- 讀寫頭可以沿著存儲帶一格一格的左移或者右移
這里存儲帶其實就相當于現(xiàn)在計算機的內存灿椅，控制器其實就相當于CPU + 程序代碼
一直聽說最早的計算機程序都是通過紙帶打孔的方式表示的套蒂，原來是從圖靈機這里來的啊。
它的工作過程
- 準備
- 存儲帶上符號的初始化(準備輸入數(shù)據(jù))
- 控制器設置好自身當前的狀態(tài)(程序代碼的初始化)
- 讀寫頭置于存儲帶的起始位置(初始化)
- 反復執(zhí)行以下工作直到停機
- 讀出存儲帶上當前方格的符號
- 根據(jù)自身狀態(tài)和讀入的符號茫蛹，找到相應的程序語句
- 在存儲帶上寫入相應的值
- 修改圖靈機自身的狀態(tài)
- 根據(jù)程序的定義把存儲帶左移或者右移
一個圖靈機工作示例
那么圖靈機如何進行實際的計算呢操刀？我們來舉個例子:
假設我們
存儲帶上的數(shù)據(jù)只有兩種可能0,1, 圖靈機負責把0變成1，1變成0婴洼。
假設我們的存儲帶上的數(shù)據(jù)是這樣的:
我們圖靈機的控制邏輯是這樣的:
| 讀取到的符號 | 寫存儲帶的動作 | 移動操作 |
|---|---|---|
| 0 | 1 | 向右移動 |
| 1 | 0 | 向右移動 |
這其實就是我們的
代碼骨坑。
現(xiàn)在我們圖靈機開始運作，第一個讀到0, 根據(jù)控制邏輯表，我們把它改成1欢唾，并且存儲帶向右移動:
這次我們讀到的是1, 根據(jù)控制邏輯表且警，我們把它改成0，并且存儲帶向右移動:
繼續(xù)上面的邏輯礁遣，最終讀到一個空數(shù)據(jù)斑芜，圖靈機執(zhí)行結束。存儲帶最終的狀態(tài)是:
最終的狀態(tài)也就是程序運行的結果祟霍。
圖靈完備
A computational system that can compute every Turing-computable function is called Turing-complete (or Turing-powerful). Alternatively, such a system is one that can simulate a universal Turing machine.
也就是說如果一個指令集或者程序語言能夠模擬圖靈機的所有能力杏头，那么它就是圖靈完備的。
這里強調的是指定的計算系統(tǒng)的能力是圖靈機的超集
圖靈等價
A Turing-complete system is called Turing equivalent if every function it can compute is also Turing computable; i.e., it computes precisely the same class of functions as do Turing machines. Alternatively, a Turing-equivalent system is one that can simulate, and be simulated by, a universal Turing machine. (All known Turing-complete systems are Turing equivalent, which adds support to the Church–Turing thesis.)
一個計算系統(tǒng)被稱為圖靈等價的前提是它是圖靈完備的沸呐。但是這還不夠醇王，它的所有的能力，圖靈機也要具備崭添。
這里強調的是指定計算系統(tǒng)的能力跟圖靈機的計算能力是一樣的寓娩。
