目錄

• 圖靈機(turing machine)
• 例子
• 格局(configuration)
• Turing's Thesis

---

圖靈機(turing machine)

學過計算機的人總歸會多或少得聽說過圖靈機這種東西，但是圖靈機究竟是什么呢？圖靈機其實也是自動機的一種，并且圖靈機會在狀態轉換過程中操作一個無限的tape

tape的樣子如下圖所示，tape里面包含字符，其中后面那個兩豎一橫的符號是blank的意思，它是一個特殊的字符，用來填滿無限的tape

tape head指向當前tape上的字符

tape上的操作

• 可以對tape head指向的字符進行讀/掃描操作
• 可以對tape head指向的字符進行寫/更新操作
• 將tape head左移一格
• 將tape head右移一格

操作規則：
1、
每一步操作都要執行一下操作

• 讀取當前的字符
• 更新當前格子中的字符
• 左移一格或者右移一格

如果當前tape指向最左邊的格子，那么執行左移操作將不會發生移動

如果你不想更改當前格的字符，那么執行更新操作的時候只要讓它更新為和當前字符一樣即可

2、
操作行為類似于有限狀態機

有初始狀態

終止狀態有兩種：

• accept state
• reject state

計算結束后狀態會變成下列三種中的一種：

• 終止并且接受(accept)
• 終止并且拒絕(reject)
• 循環(loop，就是說沒有終止)

下面是圖靈機的正式定義，Turing Machine可以表示為一個七元組$(S,\Sigma ,\Gamma ,\delta ,s_0,b,F)$

• S是一組狀態的集合
• $\Sigma$是輸入字母表
• $\Gamma$是tape的字母表
• $\delta$是轉換函數
• $s_0$是初始狀態
• $b$是空符號
• $F$是終止狀態的集合(包括accept或reject)

轉換函數 $\delta$定義為:
$$S\times \Sigma \to \Gamma \times (R/L)\times S$$

這里的(R/L)就是執行左移或者右移操作，R就是向右(right)移動，L就是向左(left)移動

以下面這張圖為例，在圖上$0\to 1,R$代表的含義是，在狀態A時接收字符0，那么將會轉變為狀態B，并且在當前磁頭位置寫下1這個字符，然后磁頭向右移動一格

例子

接下來我們通過構建一個圖靈機，并且實際運算一下，看看圖靈機究竟是如何進行計算的

我們要構建圖靈機，用于計算n+1函數，下圖的初始狀態是q1，結束狀態是qa

假設輸入的數字為1011（二進制），初始時tape head指向第一個值

第一步讀取一個1，自動機會通過$1\to 1，R$這個轉換，轉換后仍然變成$q_1$，在第一格寫入1，并將tape head右移一格

接下來的步驟和上面一樣分別讀取0,1,1仍然轉變為$q_1$，并且寫上和原來相同的數字

這時候的tape head指向了空字符，按照狀態機的轉換$q_1$只能轉變為$q_2$，要注意的是，tape head會往左移動一格

我們看看$q_2$這邊的轉換，碰到1就寫入0，并且向左移動tape head，因為按照二進制加法的邏輯，最后一位如果是1，那么+1后變成0，并且會進一位，如果最后一位是0，那么就直接變成1就行了，故此有了圖上$q_2$的轉換

再執行一次上面的操作

這次讀取到了0，所以狀態$q_2$將會轉變為$q_3$，并且將0覆寫為1，然后向右移動一格

來到了$q_3$狀態，在這個狀態下，只要單純向右移動即可，因為寫入的數字是相同的

終于到了最后一步啦，看到讀取空字符，然后$q_3$狀態就會轉變為$q_a$的接受狀態，因為到達了終止狀態，滿足了圖靈機的終止條件，所以圖靈機運行完畢

我們來看看，我們輸入的數字是1011，然后輸出的數字是1100，所以我們實現的這個圖靈機完成了n+1這個函數的操作步驟

格局(configuration)

configuration翻譯成了格局，但這個東西其實就是一個圖靈機在當前狀態下的快照，由當前狀態下tape中的字符，tape head指向的位置，以及當前自動機的狀態這三個元素組成，可以簡單的用如下圖所示圖靈機的格局

用字符串表示格局的話，是類似于下面這樣的：

$?$ 1100$q_1$ 11001

$?$符號代表開始位置，里面的$q_1$代表當前的狀態，里面的字符代表的tape中的字符，tape head指向的是狀態右邊的第一個字符，所以在這個例子里面，tape head指向的是1

Turing’s Thesis

Turing’s Thesis
1、任何能被數字計算機執行的事情，Turing Machine同樣也能夠完成（從這里可以看出Turing Machine能力相當強大）
2、如果你能寫出一個算法來解決某個問題，那么同樣可以寫出一個圖靈機程序來解決相同的問題

總結

以上是生活随笔為你收集整理的软件理论基础学习笔记——图灵机的全部內容，希望文章能夠幫你解決所遇到的問題。

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