The Decidables and Undecidables

稍微整理一下 Sipser 第四章 "Decidability" 和第五章 "Reducibility" 本文內的問題 XD。

Decidable problems

• A_DFA ─ 給定的 DFA 是否接受給定字串（p.168）：用 TM 模擬之。
• A_NFA ─ 給定的 NFA 是否接受給定字串（p.169）：先把 NFA 轉換為 DFA，然後交給判別 A_DFA 的 TM 判別。
• A_REX ─ 給定字串是否匹配給定的 regex（p.170）：把 regex 轉換為 NFA，然後交給判別 A_NFA 的 TM 判別。
• E_DFA ─ 給定 DFA 所辨識的語言是否為空（p.170）：對 DFA 的 states 做 BFS。
• EQ_DFA ─ 給定的兩部 DFAs 所辨識的語言是否相同（p.171）：建一部 DFA 辨識「兩部給定 DFAs 所辨識語言」的 symmetric difference，然後用判別 E_DFA 的 TM 判別之。
• A_CFG ─ 給定 CFG 是否能產生給定字串（p.172）：將 CFG 轉換為 Chomsky normal form，令給定字串為 w，看「經 2|w| - 1 次代換而得的字串」裡面是否有 w。
• E_CFG ─ 給定 CFG 所產生的語言是否為空（p.173）：判定任意變數是否可能導出字串 ─ 將 terminal symbols 標上記號，接著只要有某條規則的右側所有 symbols 都有記號，就把該條規則左側的變數標上記號，情勢不再變動後看 S 是否有記號。
• Context-free languages（p.174）：既為 context-free language，就可找到某個 CFG 產生之，如此便落在 A_CFG 的勢力範圍內。
• A_LBA ─ 給定 LBA 是否接受給定字串（p.198）：直接模擬之，因為 LBA 的 configurations 有窮，故超過總共組數即可判定為 looping。

Undecidable problems

• A_TM ─ 給定 TM 是否接受給定字串（p.176）：用 Cantor 偉大的對角線論證法。Remark：A_TM 為 Turing-recognizable。
• A_TM ─ 給定 TM 是否不接受給定字串（not Turing-recognizable；p.184）：若 A_TM 為 Turing-recognizable，則 A_TM 同時為 Turing-recognizable 和 co-Turing-recognizable，而得到 A_TM 為 decidable。
• HALT_TM ─ 給定 TM 接收給定字串為輸入時是否停機（p.192）：by reduction from A_TM ─ 先用判別 HALT_TM 的 TM 測試是否會 loop，不會 loop 再直接模擬之。
• E_TM ─ 給定 TM 所辨識的語言是否為空（p.193）：by reduction from A_TM ─ 修改給定 TM，使之拒絕給定字串以外的所有字串，然後交給判別 E_TM 的 TM 判別。
• REGULAR_TM ─ 給定 TM 所辨識的語言是否為 regular（p.195）：by reduction from A_TM ─ 造一部 TM 接受 0^n1^n 形式之字串，除此之外，若給定 TM 接受給定字串，則接受「其他形式不為 0^n1^n 的字串」，最後將此 TM 交給判別 REGULAR_TM 的 TM。
• EQ_TM ─ 兩部給定 TM 所辨識的語言相同（p.196）：by reduction from E_TM ─ 造一部「所辨識語言為空」的 TM，然後和給定 TM 一起交給判別 EQ_TM 的 TM。
• E_LBA ─ 給定 LBA 所辨識的語言是否為空（p.199）：by reduction from A_TM ─ 造一部 LBA 接受「給定 TM 接受給定字串」的計算歷程（computation history）字串，然後交給判別 E_LBA 的 TM。
• ALL_CFG ─ 給定 CFG 是否產生 \Sigma*（p.201）：by reduction from A_TM ─ 設計一個 CFG 產生所有字串，除了「給定 TM 接受給定字串」的計算歷程以外，然後將此 CFG 交予判別 ALL_CFG 的 TM 判別。
• EQ_CFG ─ 兩個給定 CFGs 產生的語言是否相同（p.174）：by reduction from ALL_CFG ─ 造一個 CFG 產生 \Sigma*，然後判別給定 CFG 所產生的語言是否和適才的 CFG 相同。
• PCP ─ the post correspondence problem（p.203）：造一堆 dominos，加以拼湊可產生「給定 TM 接受給定字串」的計算歷程（「給定 TM 接受給定字串」iff「可由這堆 dominos 拼湊出 accepting 的計算歷程」）。細節參見 p.204 ~ p.209 XD。

--
然後就到 complexity theory 了。後半學期實在有點偏離課名「自動機與形式語言」 XD。

---

想一想，似乎也不算太偏 XD。