文章目錄

• 一、非確定性圖靈機 -＞ 確定性圖靈機
• 二、確定性圖靈機 模仿 非確定性圖靈機 過程
• 三、算法的數學模型

一、非確定性圖靈機 -＞ 確定性圖靈機

---

給定如下非確定性圖靈機 , 設計 確定性圖靈機 模仿下面的 非確定性圖靈機 ;

上述非確定性圖靈機 的計算過程是一個 計算樹 ;

二、確定性圖靈機 模仿 非確定性圖靈機 過程

---

使用 確定性圖靈機 描述上述 非確定性圖靈機 ;

設計的 確定性圖靈機 有 $3$ 個帶子 , 每個帶子對應著 非確定性圖靈機 計算樹 的一個分支 ;

第 $1$ 個帶子 ( 輸入字符串 ) 上是 圖靈機的輸入字符串 , 該帶子上的內容永不改變 , 不能放其它內容 ;

第 $2$ 個帶子 ( 模仿帶子 ) 上是 模仿的計算樹的一個分支的內容 ;

第 $3$ 個帶子 ( 地址帶子 ) 上是數字編碼 , 該數字編碼會不停的更新 , 該編碼代表了計算樹中計算分支的編碼 ,

下圖中 第 $3$ 個帶子的 $123$ 含義是 ,
在深度為 $1$ 的分支中 , 選擇第 $1$ 個分支 ,
在深度為 $2$ 的分支中 , 選擇第 $2$ 個分支 ,
在深度為 $3$ 的分支中 , 選擇第 $3$ 個分支 , 如下圖所示的分支

第 $3$ 個帶子是計算分支編碼 , 真實的模仿計算分支計算過程在 第 $2$ 個帶子上完成 ,

帶子的數據變化 :

① 第 $1$ 個帶子放輸入字符串 , 永不改變 ;

② 第 $2$ 個帶子根據 第 $3$ 個帶子選擇的計算分支加載不同的計算分支對應的字符串 ;

③ 第 $3$ 個帶子上的數字會按照字典序的順序 , 不停的進行更新 , 更新的過程就是寬度有限搜索的順序 ;

通過 $3$ 個帶子中的確定性圖靈機 , 可以模仿非確定性圖靈機的計算 , 本質是找到非確定圖靈機中的接受狀態對應的 計算分支 ;

三、算法的數學模型

---

為算法提供嚴格的數學模型 , 除了圖靈機之外 , 還有其它的 $3$ 種數學模型 :

① 可計算函數 ,數學方向 ;

② Lambda 演算 , 程序語言方向 ;

③ 登記計算機 ( Register Machine ) , 計算理論方向 ;

總結

以上是生活随笔為你收集整理的【计算理论】图灵机 ( 非确定性图灵机 -＞ 确定性图灵机 | 模仿过程示例 | 算法的数学模型 )的全部內容，希望文章能夠幫你解決所遇到的問題。

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