文章目錄

• 一、不可判定性 ( Undecidability )
• 二、"停機問題" 不可判定
• 三、"圖靈機語言是否空集問題" 不可判定
• 四、"圖靈機是否等價問題" 不可判定
• 五、"是否存在自動機接受圖靈機語言問題" 不可判定
• 六、萊斯定理 ( Rice's Theorem )

一、不可判定性 ( Undecidability )

---

不可判定 ( Undecidability ) 是正常的 , 絕大多數的 計算問題 都是不可判定的 ;

可判定的計算問題 只占 計算問題 中的 一小部分 ;

證明思路 :

不可數無窮 : 語言 與 計算問題 的個數是無窮的 , 其個數與實數一樣多 , 是 不可數無窮 ;

可數無窮 : 圖靈機 個數也是無窮的 , 其個數與自然數一樣多 , 是 可數無窮的 ;

語言的個數 要 遠遠多于 圖靈機個數 ;

二、“停機問題” 不可判定

---

停機問題 是不可判定的 ;

停機問題 : 設計一個程序 , 幫助判定 “給定一個程序 , 該程序是否會停機” ;

① 如果知道該程序 不會停機 , 就強制停止該程序 ;

② 如果知道該程序 會停機 , 就耐心等待該程序執行完畢 ;

上述 “能判定程序是否會停機” 的程序 , 是不存在的 ;

三、“圖靈機語言是否空集問題” 不可判定

---

判定圖靈機所認識的語言是否是空集 的問題 , 也是不可判定的 ;

四、“圖靈機是否等價問題” 不可判定

---

圖靈機的等價問題 , 即 判定兩個圖靈機是否是相互等價的 , 也是不可判定的 ;

五、“是否存在自動機接受圖靈機語言問題” 不可判定

---

圖靈機 所認識的語言 , 是否能夠找到一個自動機認識 , 是不可判定的 ;

六、萊斯定理 ( Rice’s Theorem )

---

萊斯定理 ( Rice’s Theorem ) :

任何一個 關于圖靈機的計算問題 , 都是 不可判定的 ;

總結

以上是生活随笔為你收集整理的【计算理论】不可判定性 ( 停机问题 | 图灵机语言是否空集问题 | 图灵机是否等价问题 | 是否存在自动机接受图灵机语言问题 | 莱斯定理 Rice‘s Theorem )的全部內容，希望文章能夠幫你解決所遇到的問題。

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