文章目錄

• 一、計算模型與語言
• 二、區(qū)分 可計算語言 與 可判定語言
• 三、證明 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 可計算
• 四、通用 ( Universal ) 任務圖靈機 與 特殊任務圖靈機

一、計算模型與語言

---

計算模型是逐步進行擴張的 :

自動機 $\to$ 下推自動機 ( $1$ 個棧 ) $\to$下推自動機 ( $2$ 個棧 ) $?$ 圖靈機

所對應的語言也是逐步進行擴張的 :

正則語言 $\to$ 上下文無關(guān)語言 $\to$ 可計算語言

正則語言 對應的 計算模型 是 確定性有限自動機 ,

上下文無關(guān)語言 對應的 計算模型 是 下推自動機 ,

可計算語言 對應的 計算模型 是 圖靈機 ,

可判定語言 對應的 計算模型 是 判定機 ,

判定機 是一種 特殊的 圖靈機 , 是圖靈機的子集 ;

可判定語言 是 可計算語言 的子集 ;

圖靈機 的 可計算語言 , 是計算機科學的研究領域 ;

二、區(qū)分 可計算語言 與 可判定語言

---

找一個特例語言 , 區(qū)分 可計算語言 與 可判定語言 ;

圖靈機的可接受問題 :

將計算問題進行形式化 , $\mathrm{M}$ 是圖靈機 , $\mathrm{w}$ 是字符串 , 如果 $\mathrm{M}$ 圖靈機 接受 $\mathrm{w}$ 是字符串 , 將所有的可接受的 $\mathrm{w}$ 是字符串放在一個集合中 , 組成的語言 稱為 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 ;

${\mathrm{A}}_{\mathrm{T}\mathrm{M}}=\{<\mathrm{M},\mathrm{w}>|圖靈機\mathrm{M}接受\mathrm{w}字符串\}$

${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 稱為 圖靈機可接受的 ;

${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 是可計算的 , 但 不是可判定的 ;

該結(jié)論可以區(qū)分 可判定語言 與 可計算語言 ;

三、證明 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 可計算

---

證明 : ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 是可計算的 , 但 不是可判定的 ;

證明過程 : 構(gòu)造圖靈機 $\mathrm{U}$ ,

① 字符串 : 給定一個輸入字符串 , $<\mathrm{M},\mathrm{w}>$ , 即 在 圖靈機 $\mathrm{M}$ 上接受的字符串 $\mathrm{w}$ ;

② 模仿 : 字符串輸入到 圖靈機 $\mathrm{M}$ 之后 , 將自己想象成 $\mathrm{U}$ , 模仿 圖靈機 $\mathrm{M}$ 在 字符串 $\mathrm{w}$ 上進行計算 ;

③ 接受 / 拒絕 狀態(tài) : 如果 圖靈機 $\mathrm{M}$ 進入接受狀態(tài) , 則 圖靈機 $\mathrm{U}$ 也進入接受狀態(tài) , 如果圖靈機 $\mathrm{M}$ 進入拒絕狀態(tài) , 則 圖靈機 $\mathrm{U}$ 也進入拒絕狀態(tài) ;

④ Loop 循環(huán)狀態(tài) : 圖靈機 $\mathrm{M}$ 在 $\mathrm{w}$ 字符串上計算時 , 可能有第 $3$ 種可能性 , 即進入 Loop 循環(huán)狀態(tài) , 永不停機 ; 此時 圖靈機 $\mathrm{U}$ 也只能進入 Loop 狀態(tài) ;

現(xiàn)在 圖靈機 $\mathrm{U}$ 模仿的是 圖靈機 $\mathrm{M}$ 在 字符串 $\mathrm{w}$ 上的計算 , 圖靈機 $\mathrm{M}$ 進入什么狀態(tài) , 圖靈機 $\mathrm{U}$ 就進入什么狀態(tài) ;

$\mathrm{U}$ 很顯然是 圖靈機 , 因此 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 對應的計算問題是可計算的 ;

證明 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 不可判定 , 在下一篇博客中證明 ;

四、通用 ( Universal ) 任務圖靈機 與 特殊任務圖靈機

---

下面開始證明 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 對應的計算問題 是 不可判定的 ;

根據(jù) 丘奇-圖靈 命題 , 圖靈機 等于 算法 ;

圖靈機 $\mathrm{U}$ = " 在輸入字符串 $<\mathrm{M},\mathrm{w}>$ 上 , $\mathrm{M}$ 是圖靈機 , $\mathrm{w}$ 是字符串 , 則有 ① 模擬 $\mathrm{M}$ 在 $\mathrm{w}$ 上進行計算 , ② 如果 $\mathrm{M}$ 進入接受狀態(tài) , 則 $\mathrm{U}$ 接受 , $\mathrm{M}$ 拒絕 $\mathrm{U}$ 拒絕 , $\mathrm{M}$ Loop $\mathrm{U}$ 也 Loop "

上述 等號 左側(cè)是 圖靈機 $\mathrm{U}$ , 等號 右側(cè) 是 算法 ;

等號 就是 丘奇-圖靈 命題 ;

$\mathrm{U}$ 是通用 ( Universal ) 圖靈機 ,

① 特殊任務圖靈機 : 一般情況下 計算模型 是執(zhí)行一個 特定任務 , 給定一個任務 , 給定一個輸入 , 圖靈機進行計算 , 然后輸出結(jié)果 ;

② 通用任務圖靈機 :

圖靈機 $\mathrm{U}$ 不是特殊任務圖靈機 , 而是一個 一般任務圖靈機 , 該圖靈機可以執(zhí)行各種操作 ,

將各種圖靈機 , 進行編碼 , 輸入到通用圖靈機 $\mathrm{U}$ 中 , 通用圖靈機 $\mathrm{U}$ 就會模仿 特殊圖靈機 $\mathrm{M}$ 在字符串 $\mathrm{w}$ 上進行計算 ;

通用圖靈機 $\mathrm{U}$ 的主要任務就是 模仿所有其它 特殊圖靈機 $\mathrm{M}$ 進行計算 ;

計算機剛出現(xiàn)時 , 每個計算機只能執(zhí)行特殊的任務 ,

真正的通用任務計算機是 馮諾依曼 設計的 , 可以執(zhí)行所有的計算任務 ;

總結(jié)

以上是生活随笔為你收集整理的【计算理论】可判定性 ( 计算模型与语言 | 区分 可计算语言 与 可判定语言 | 证明 通用图灵机语言是 可计算语言 | 通用任务图灵机 与 特殊任务图灵机 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。