【正文】 自學（美國的一些學校也安排為 自學） ?我們略去書上 PCP問題，而增加鋪磚問題作為不可判定問題的例子。有的書先證明它，然后用它證明停機問題不可判定。 自學（美國的一些學校也安排為自學） Univ. 可計算理論 2022/8/14 68/70 Post對應問題（ PCP) 計劃內的自學課題 用英語來解釋： 是否有不同語義的兩個句子，在 把單詞之間的空格刪去后，表達一樣（歧義）， W1W2W3W4=X1X2X3X4 PCP問題： 能否設計一個算法，判定英語中任一字符串是否歧義串 答案： 不能。有的書先證明它，然后用它證明停機問題不可判定。 答案： 不能。 有歷史的意義。成為 PCP是不可判定的。 有歷史的意義。成為 PCP是不可判定的。 所以被調用者也不可判定 Univ. 可計算理論 2022/8/14 63/70 Undecidability ?學習了若干不可判定問題， ?不容易證明， 但 結果是容易理解的 。 } 上頁 ： Theorem : ALLCFG is undecidable Remember the language EQCFG = {?G1,G2? | G1,G2 CFGs L(G1)=L(G2) }? Cp103 預告它 不可判定 ,但一直未證明。 作為習題 ， 它是 定理 C6,10的推論 ,。 由 G的構造 Univ. 可計算理論 2022/8/14 61/70 Undecidability CFG Properties 定理 習題 The language is EQCFG undecidable. //滿問題歸約為相等問題 Proof: Deter_All(M) //滿問題 . 已知是不可判定 { //調用一個特殊的相等問題 return(Deter_EQ_CFG(M, ?*)。 G= “if (M不接受 W) G?* x “ //上頁已經說明能造出來 return (Deter_ALL (G)。 //被調 } 分析 y?ALLCFG ?? y != M在 W上的計算歷史 ?? M不接受 W y ? ALLCFG ?? y == M在 W上的計算歷史 ?? M接受 W 于是推出 接受問題可判定，矛盾。 把 不定方程的整數解 轉化為 接受問題 Univ. 可計算理論 2022/8/14 52/70 用接受歷史研究 CFL 中的判定問題 定理５ .10, cp121 ALLCFG = {?G? | G is CFG, L(G)=?* } 識別全集的 CFG的集合 Theorem : ALLCFG is undecidable 不能寫出通用程序判定其成員籍 We can prove the undecidability of this language with the use of putation histories. Goal: Linking ATM with EQCFG 把它和 接受問題，相等問題 聯(lián)系起來 This will require some careful steps. 分幾步 Univ. 可計算理論 2022/8/14 53/70 Theorem Initial Attempt 一種容易想到 但不成功的想法 ?M,w??ATM 出發(fā) ?M,w??ATM equals “There is an accepting history x of M on w.” Let?s try to express this as: ?x??LCFG, where LCFG is some CF language. Problem: “?x??LCFG?” is decidable… 此路不通??！ Univ. 可計算理論 2022/8/14 54/70 Theorem Initial Attempt 一種容易想到 但不成功的想法 ?M,w??ATM 出發(fā) ?M,w??ATM equals “There is an accepting history x of M on w.” Let?s try to express this as: ?x??LCFG, where LCFG is some CF language. Problem: “?x??LCFG?” is decidable… 此路不通??！ Univ. 可計算理論 2022/8/14 55/70 Theorem Second Attempt 正面走不通， 從反面考慮 ?M,w??ATM ?M,w??ATM 圖靈機 M不接受 w 等價于 沒有 M接受 w的歷史 “There is no accepting history x of M on w.” 等價于 “All histories x are nonaccepting for M on w” 所有歷史格局 是 非接受格局 問題表達為 : { X| ?x??LCFG , LCFG is CFL， 且 含有 M不接受 w的歷史的描述 } Univ. 可計算理論 2022/8/14 56/70 Theorem 從反面考慮 給定 TM M 和輸入串 w, 設法造 CFG G 使得 : x?G ?? x 不是 M 接受 w的歷史（的編碼） 這樣的 CFG 能夠造出來， Cp118119 造了一個 PDA,然后轉變成 CFG，利用了下列知識 設 x 是下列歷史的編碼 C1,…,C k, 則 x?G 的充分條件是下列三者之一： 1) C1 不是開始格局 , 或 2) 中間有一處格局轉換 Cj ? Cj+1 不能推出接受 ,或 3) 最后的 Ck 不是接受格局 用 C語言寫 CFG G 大致如下 源程序 G= “if (M不接受 W) G?* x “ 如果看 ?*的細節(jié)，大約有三個 OR 分支，易 看出 G識別的語言 L(G)= ?* M在 W上的計算歷史； 下頁要用這個源程序， Univ. 可計算理論 2022/8/14 57/70 Theorem 從反面考慮 給定 TM M 和輸入串 w, 設法造 CFG G 使得 : x?G ?? x 不是 M 接受 w的歷史（的編碼） 這樣的 CFG 能夠造出來， Cp118119 造了一個 PDA,然后轉變成 CFG，利用了下列知識 設 x 是下列歷史的編碼 C1,…,C k, 則 x?G 的充分條件是 下列三者之一 ： 1) C1 不是開始格局 , 或 2) 中間有一處格局轉換 Cj ? Cj+1 不能推出接受 ,或 3) 最后的 Ck 不是接受格局 用 C語言寫 CFG G 大致如下 源程序 G= “if (M不接受 W) G?* x “ 如果看 ?*的細節(jié)，大約有三個 OR 分支，易 看出 G識別的語言 L(G)= ?* M在 W上的計算歷史 ； 下頁要用這個源程序， Univ. 可計算理論 2022/8/14 58/70 Theorem 從反面考慮 給定 TM M 和輸入串 w, 設法造 CFG G 使得 : x?G ?? x 不是 M 接受 w的歷史（的編碼） 這樣的 CFG 能夠造出來， Cp118119 造了一個 PDA,然后轉變成 CFG，利用了下列知識 設 x 是下列歷史的編碼 C1,…,C k, 則 x?G 的充分條件是下列 三者之一 ： 1) C1 不是開始格局 , 或 2) 中間有一處格局轉換 Cj ? Cj+1 不能推出接受 ,或 3) 最后的 Ck 不是接受格局 用 C語言寫 CFG G 大致如下 源程序 G= “if (M不接受 W) G?* x “ 如果看 ?*的細節(jié)，大約有 三個 OR 分支，易 看出 G識別的語言 L(G)= （ ?* L( M)） 在 W上的計算歷史； 下頁要用這個源程序， Univ. 可計算理論 2022/8/14 59/70 Theorem cp123 反證法 設 ALLCFG = {?G? | G is CFG, L(G)=?* } 可判定 現在把接受問題歸約為對 ALLCFG的判定 Bool Deter_Accept(M,w) //主調 { //造出如上頁描述的 CFG G //G識別的語言 L(G)= ?* M在 W上的計算歷史 。 不定方程 接受問題 Univ. 可計算理論 2022/8/14 51/70 用接受歷史 解決的若干問題 Hilbert’s 10th Problem again cp115 Decision problem: Let P(x1,…,x n) be a polynomial in n variables ?(x1,…,x n) ? Zn: P(x1,…,x n) = 0? 不定方程是否有解， 例如費馬問題 是否可判定（寫程序來判斷）？ 表達計算歷史為元組 ( x= (x1,…,x n) ?Zn)的序列。} 對比 cp 115,可知，我們的 SCU表達法 特別簡潔 EQTM is not even TM or coTM recognizable… 空問題已經被證明是不可判定，它可規(guī)約為相等問題 ，所以相等問題不可判定 ?空語機 ?源程序 Univ. 可計算理論 2022/8/14 42/70 Limited Success thus far 由上可知，規(guī)約（調用）方法證明問題較簡單 Our reductions have been very straightforward: “A TM for this language can be transformed into a similar TM that decides another language” As a result, the provable undecidable languages are very alike ATM, EQTM, HALTTM, et cetera. For languages concerning questions not about TMs we have to use a more refined reduction. Univ. 可計算理論 2022/8/14 43/70 Computation Histories 計算歷史 ep176 cp120 An accepting putation history for a TM M on a string w consists of a sequence of configurations C1,C2,…,C k such that the following properties hold: 接受歷史－格局序列 ，格局 =（寄存器，指令指針，內存 ,… ） 1. C1 is the start configuration of M on w 始格 2. Each Cj+1 follows properly from Cj 3. Ck is an accepting configuration 接受格局 Observation: Stating “?M,w??ATM” is equivalent with stating “There is no accepting putation