
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 開始
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎知識
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- Moore 機與 Mealy 機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的泵引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的封閉性
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的泵引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 從 CFG 構造 PDA
- 下推自動機和解析
- 圖靈機
- 圖靈機 (TM) 基礎
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限帶圖靈機
- 線性界限自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
圖靈機停機問題
輸入 - 一臺圖靈機和一個輸入字串 w。
問題 - 圖靈機是否能在有限步驟內完成字串 w 的計算?答案必須是“是”或“否”。
證明 - 首先,我們假設存在這樣的圖靈機來解決這個問題,然後我們將證明它自相矛盾。我們將稱這個圖靈機為停機機,它在有限時間內產生“是”或“否”。如果停機機在有限時間內完成,則輸出為“是”,否則為“否”。以下是停機機的框圖:

現在我們將設計一個反向停機機 (HM)’如下:
如果 H 返回 YES,則無限迴圈。
如果 H 返回 NO,則停止。
以下是“反向停機機”的框圖:

此外,一個輸入為自身的機器 (HM)2 構建如下:
- 如果 (HM)2 在輸入上停止,則無限迴圈。
- 否則,停止。
在這裡,我們得到了一個矛盾。因此,停機問題是不可判定的。
廣告