文章目錄

• 一、存在性證明
• 二、證明 通用任務圖靈機 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 對應的計算模型一定是 不可判定 ( 對角線法 )

一、存在性證明

---

存在性證明 : 肯定存在一些語言 , 不能被圖靈機接受 ;

使用 語言 可以表示 計算問題 , 計算問題的個數與 實數 一樣多 , 是 不可數的 ;

圖靈機 的個數 與 自然數 一樣多 , 是 可數的 ;

計算問題 要比 計算模型 多很多 , 計算問題 與 圖靈機 之間不是 一一對應的 ;

肯定存在一個計算問題 , 找不出與之對應的圖靈機 , 因此該計算問題肯定是 不可計算的 ,

二、證明 通用任務圖靈機 ${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言 對應的計算模型一定是 不可判定 ( 對角線法 )

---

${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言簡介 :

將計算問題進行形式化 , $\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}}$ 語言 是可計算的 , 但 不是可判定的 ;

該結論可以區分 可判定語言 與 可計算語言 ;

使用 對角線法 證明 ;

與博客 【計算理論】可判定性 ( 對角線方法 | 證明自然數集 N 與實數集 R 不存在一一對應關系 ) 中證明 自然數集 與 實數集 不能一一對應類似 ;

在 【計算理論】可判定性 ( 計算模型與語言 | 區分 可計算語言 與 可判定語言 | 證明 某語言是 可計算語言 | 通用任務圖靈機 與 特殊任務圖靈機 ) 博客中證明了 通用圖靈機語言 是計算語言 , 本博客中證明 通用圖靈機語言 不可判定 ;

使用反證法證明 :

圖靈機的結果有 $3$ 個狀態 , 接受狀態 , 拒絕狀態 , Loop 不停機狀態 ;

${\mathrm{A}}_{\mathrm{T}\mathrm{M}}$ 語言只包含 接受狀態 的情況 ;

所有的圖靈機 與 自然數集 一樣多 , 所有的圖靈機 是可以枚舉出來的 , ${\mathrm{M}}_1,{\mathrm{M}}_2,{\mathrm{M}}_3,?,{\mathrm{M}}_{\mathrm{n}}$ 圖靈機 ;

枚舉事務 , 一定有先決條件 , 如自然數集 , 無窮一定是可數的 , 不可數的無窮 , 如實數集 , 不能像上面圖靈機一樣枚舉 , 實數是無法進行枚舉的 ;

可以枚舉的無窮 , 一定是可數無窮 ; 圖靈機個數與自然數一樣多 , 是可數無窮 , 因此可以枚舉出來 ;

垂直表格中是枚舉出來的圖靈機 , 水平表格中是圖靈機語言的編碼 ;

表格中的內容 , 如第一行第一列 , ${\mathrm{M}}_1$ 與 $<m_1>$ 交叉的項 , 表示 圖靈機 ${\mathrm{M}}_1$ 在 $<m_1>$ 編碼上進行運算 , 其運算結果是 接受狀態 ;

對角線意外的項都是有結果的 , 與本次證明無關, 省略了 , 接受或拒絕 ;

$<m_1>$$<m_2>$$<m_3>$$?$$<m_n>$

${\mathrm{M}}_1$	接受
${\mathrm{M}}_2$		拒絕
${\mathrm{M}}_3$			接受
$?$
${\mathrm{M}}_{\mathrm{n}}$					拒絕

假設 : 存在一個 圖靈機 $\mathrm{H}$ , $A_{TM}$ 語言 是可判定的 ;

表格中的 圖靈機 $\mathrm{H}$ 的結果是已知的 , 接受 或 拒絕 ;

構造 圖靈機 $\mathrm{D}$ , 根據圖靈機語言編碼 $<{\mathrm{m}}_{\mathrm{n}}>$ 上的操作 :

圖靈機 $\mathrm{D}$ , 在 ${\mathrm{m}}_1$ 編碼上的計算結果 , 主要查看第 $1$ 行 , 第 $1$ 列的 , 即 圖靈機 ${\mathrm{M}}_1$ 在 $<m_1>$ 編碼上的結果 , 該計算結果是 接收 的 , 那么 圖靈機 $\mathrm{D}$ 在 $<m_1>$ 編碼 上的結果就設定相反的結果 , 拒絕 ;

圖靈機 $\mathrm{D}$ , 在 ${\mathrm{m}}_2$ 編碼上的計算結果 , 主要查看第 $2$ 行 , 第 $2$ 列的 , 即 圖靈機 ${\mathrm{M}}_2$ 在 $<m_2>$ 編碼上的結果 , 該計算結果是 拒絕 的 , 那么 圖靈機 $\mathrm{D}$ 在 $<m_2>$ 編碼上的結果就設定相反的結果 , 接收 ;

圖靈機 $\mathrm{D}$ , 在 ${\mathrm{m}}_3$ 編碼上的計算結果 , 主要查看第 $3$ 行 , 第 $3$ 列的 , 即 圖靈機 ${\mathrm{M}}_3$ 在 $<m_3>$ 編碼上的結果 , 如果該計算結果是 接受 的 , 那么 圖靈機 $\mathrm{D}$ 在 $<m_3>$ 編碼上的結果就設定相反的結果 , 拒絕 ;

$$?$$

圖靈機 $\mathrm{D}$ , 在 ${\mathrm{m}}_{\mathrm{n}}$ 編碼上的計算結果 , 主要查看第 $n$ 行 , 第 $n$ 列的 , 即 圖靈機 ${\mathrm{M}}_{\mathrm{n}}$ 在 $<m_n>$ 編碼上的結果 , 如果該計算結果是 拒絕 的 , 那么 圖靈機 $\mathrm{D}$ 在 $<m_n>$ 編碼上的結果就設定相反的結果 , 接收 ;

構造出的 $\mathrm{D}$ 一定是圖靈機 , 上述描述的算法對應的計算模型就是圖靈機 ;

一定存在一個 $\mathrm{k}$ , 圖靈機 $\mathrm{D}$ 就是 對應的 圖靈機 ${\mathrm{M}}_{\mathrm{k}}$ , 在上述表格對角線位置的結果 , 即在 $<{\mathrm{m}}_{\mathrm{k}}>$ 編碼上的計算結果 , 與 圖靈機 $\mathrm{D}$ 的結果是不同的 ;

這樣就產生了矛盾 , 圖靈機 $\mathrm{D}$ 的計算結果 是 圖靈機 ${\mathrm{M}}_{\mathrm{k}}$ 在 $<{\mathrm{m}}_{\mathrm{k}}>$ 編碼上計算結果相反的結果 ; 而這兩個圖靈機是同一個圖靈機 ;

因此假設 "存在一個 圖靈機 $\mathrm{H}$ , $A_{TM}$ 語言 是可判定的 " 不成立 ,

通用任務圖靈機 $\mathrm{H}$ , $A_{TM}$ 語言 是 不可判定的

總結

以上是生活随笔為你收集整理的【计算理论】可判定性 ( 对角线方法 | 使用对角线方法证明 通用任务图灵机 语言 不可判定 )的全部內容，希望文章能夠幫你解決所遇到的問題。

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