【正文】 epting 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” 所有歷史格局 是 非接受格局 問題表達(dá)為 : { X| ?x??LCFG , LCFG is CFL， 且 含有 M不接受 w的歷史的描述 } Univ. 可計算理論 2022/8/14 56/70 Theorem 從反面考慮 給定 TM M 和輸入串 w, 設(shè)法造 CFG G 使得 : x?G ?? x 不是 M 接受 w的歷史（的編碼） 這樣的 CFG 能夠造出來， Cp118119 造了一個 PDA,然后轉(zhuǎn)變成 CFG，利用了下列知識 設(shè) x 是下列歷史的編碼 C1,…,C k, 則 x?G 的充分條件是下列三者之一： 1) C1 不是開始格局 , 或 2) 中間有一處格局轉(zhuǎn)換 Cj ? Cj+1 不能推出接受 ,或 3) 最后的 Ck 不是接受格局 用 C語言寫 CFG G 大致如下 源程序 G= “if (M不接受 W) G?* x “ 如果看 ?*的細(xì)節(jié)，大約有三個 OR 分支，易 看出 G識別的語言 L(G)= ?* M在 W上的計算歷史； 下頁要用這個源程序， Univ. 可計算理論 2022/8/14 57/70 Theorem 從反面考慮 給定 TM M 和輸入串 w, 設(shè)法造 CFG G 使得 : x?G ?? x 不是 M 接受 w的歷史（的編碼） 這樣的 CFG 能夠造出來， Cp118119 造了一個 PDA,然后轉(zhuǎn)變成 CFG，利用了下列知識 設(shè) x 是下列歷史的編碼 C1,…,C k, 則 x?G 的充分條件是 下列三者之一 ： 1) C1 不是開始格局 , 或 2) 中間有一處格局轉(zhuǎn)換 Cj ? Cj+1 不能推出接受 ,或 3) 最后的 Ck 不是接受格局 用 C語言寫 CFG G 大致如下 源程序 G= “if (M不接受 W) G?* x “ 如果看 ?*的細(xì)節(jié)，大約有三個 OR 分支，易 看出 G識別的語言 L(G)= ?* M在 W上的計算歷史 ； 下頁要用這個源程序， Univ. 可計算理論 2022/8/14 58/70 Theorem 從反面考慮 給定 TM M 和輸入串 w, 設(shè)法造 CFG G 使得 : x?G ?? x 不是 M 接受 w的歷史（的編碼） 這樣的 CFG 能夠造出來， Cp118119 造了一個 PDA,然后轉(zhuǎn)變成 CFG，利用了下列知識 設(shè) x 是下列歷史的編碼 C1,…,C k, 則 x?G 的充分條件是下列 三者之一 ： 1) C1 不是開始格局 , 或 2) 中間有一處格局轉(zhuǎn)換 Cj ? Cj+1 不能推出接受 ,或 3) 最后的 Ck 不是接受格局 用 C語言寫 CFG G 大致如下 源程序 G= “if (M不接受 W) G?* x “ 如果看 ?*的細(xì)節(jié)，大約有 三個 OR 分支，易 看出 G識別的語言 L(G)= （ ?* L( M)） 在 W上的計算歷史； 下頁要用這個源程序， Univ. 可計算理論 2022/8/14 59/70 Theorem cp123 反證法 設(shè) ALLCFG = {?G? | G is CFG, L(G)=?* } 可判定 現(xiàn)在把接受問題歸約為對 ALLCFG的判定 Bool Deter_Accept(M,w) //主調(diào) { //造出如上頁描述的 CFG G //G識別的語言 L(G)= ?* M在 W上的計算歷史 。 G= “if (M不接受 W) G?* x “ //上頁已經(jīng)說明能造出來 return (Deter_ALL (G)。 //被調(diào) } 分析 y?ALLCFG ?? y != M在 W上的計算歷史 ?? M不接受 W y ? ALLCFG ?? y == M在 W上的計算歷史 ?? M接受 W 于是推出 接受問題可判定，矛盾。 由 G的構(gòu)造 Univ. 可計算理論 2022/8/14 60/70 Theorem cp123 反證法 設(shè) ALLCFG = {?G? | G is CFG, L(G)=?* } 可判定 現(xiàn)在把接受問題歸約為對 ALLCFG的判定 Bool Deter_Accept(M,w) //主調(diào) { //造出如上頁描述的 CFG G //G識別的語言 L(G)= ?* M在 W上的計算歷史 。 G= “if (M不接受 W) G?* x “ //上頁已經(jīng)說明能造出來 return (Deter_ALL (G)。 //被調(diào) } 分析 y?ALLCFG ?? y != M在 W上的計算歷史 ?? M不接受 W y ? ALLCFG ?? y == M在 W上的計算歷史 ?? M接受 W 于是推出 接受問題可判定，矛盾。 由 G的構(gòu)造 Univ. 可計算理論 2022/8/14 61/70 Undecidability CFG Properties 定理 習(xí)題 The language is EQCFG undecidable. //滿問題歸約為相等問題 Proof: Deter_All(M) //滿問題 . 已知是不可判定 { //調(diào)用一個特殊的相等問題 return(Deter_EQ_CFG(M, ?*)。 } 上頁 ： Theorem : ALLCFG is undecidable Remember the language EQCFG = {?G1,G2? | G1,G2 CFGs L(G1)=L(G2) }? Cp103 預(yù)告它 不可判定 ,但一直未證明。 作為習(xí)題 ， 它是 定理 C6,10的推論 ,。 所以被調(diào)用者也不可判定 Univ. 可計算理論 2022/8/14 62/70 Undecidability CFG Properties 定理 習(xí)題 The language is EQCFG undecidable. //滿問題歸約為相等問題 Proof: Deter_All(M) //滿問題 . 已知是不可判定 { //調(diào)用一個特殊的相等問題 return(Deter_EQ_CFG(M, ?*)。 } 上頁 ： Theorem : ALLCFG is undecidable Remember the language EQCFG = {?G1,G2? | G1,G2 CFGs L(G1)=L(G2) }? Cp103 預(yù)告它 不可判定 ,但一直未證明。 作為習(xí)題 ， 它是 定理 C6,10的推論 ,。 所以被調(diào)用者也不可判定 Univ. 可計算理論 2022/8/14 63/70 Undecidability ?學(xué)習(xí)了若干不可判定問題， ?不容易證明， 但 結(jié)果是容易理解的 。 ?不太容易記住， 可以自己總結(jié)一個表， ?可能在自己的論文中用到 （通過規(guī)約來引用定理） ?論文中，能 證明 XXX問題不可判定 ， 一般會 提高理論深度 Univ. 可計算理論 2022/8/14 64/70 線性界限自動機（ LBA) 計劃內(nèi)的自學(xué)課題 一般圖靈機，假定帶右邊無限長，內(nèi)存無限制 線性界限自動機 ， 假定帶右邊有限制，內(nèi)存有限制 實際的計算機都是內(nèi)存有限的，都是 LBA 由于相關(guān)內(nèi)容較簡單，理論上較為次要， 許多學(xué)校都安排為自學(xué)瀏覽內(nèi)容 Univ. 可計算理論 2022/8/14 65/70 Post對應(yīng)問題（ PCP) 計劃內(nèi)的自學(xué)課題 W1=下雨天 , W2=留客天 ,W3=留我不 ,W4=留 ….. X1=下雨天 ,X2=留客 ,X3=天留 , X4= 我不留 ….. 有 W1W2W3W4=X1X2X3X4 PCP問題： 能否設(shè)計一個算法，把漢語中所有這樣的 詞的序列 找出來？ 答案： 不能。成為 PCP是不可判定的。有的數(shù)先證明它，然后用它證明停機問題不可判定。 有歷史的意義。 自學(xué) Univ. 可計算理論 2022/8/14 66/70 Post對應(yīng)問題（ PCP) 計劃內(nèi)的自學(xué)課題 W1=下雨天 , W2=留客天 ,W3=留我不 ,W4=留 ….. X1=下雨天 ,X2=留客 ,X3=天留 , X4= 我不留 ….. 有 W1W2W3W4=X1X2X3X4 PCP問題： 能否設(shè)計一個算法，把漢語中所有這樣的 詞的序列 找出來？ 答案： 不能。成為 PCP是不可判定的。有的數(shù)先證明它，然后用它證明停機問題不可判定。 有歷史的意義。 自學(xué) Univ. 可計算理論 2022/8/14 67/70 Post對應(yīng)問題（ PCP) 計劃內(nèi)的自學(xué)課題 W1=下雨天 , W2=留客天 ,W3=留我不 ,W4=留 ….. X1=下雨天 ,X2=留客 ,X3=天留 , X4= 我不留 ….. 有 W1W2W3W4=X1X2X3X4 稱為歧義串 PCP問題： 能否設(shè)計一個算法，判定漢語中任一字符串是否歧義串。 答案： 不能。因為 PCP是不可判定的。有的書先證明它，然后用它證明停機問題不可判定。有歷史的意義。 自學(xué)（美國的一些學(xué)校也安排為自學(xué)） Univ. 可計算理論 2022/8/14 68/70 Post對應(yīng)問題（ PCP) 計劃內(nèi)的自學(xué)課題 用英語來解釋： 是否有不同語義的兩個句子，在 把單詞之間的空格刪去后，表達(dá)一樣（歧義）， W1W2W3W4=X1X2X3X4 PCP問題： 能否設(shè)計一個算法，判定英語中任一字符串是否歧義串 答案： 不能。成為 PCP是不可判定的。有的書先證明它，然后用它證明停機問題不可判定。有歷史的意義。 自學(xué)（美國的一些學(xué)校也安排為 自學(xué)） ?我們略去書上 PCP問題，而增加鋪磚問題作為不可判定問題的例子。一減一增，此例在以前參考教材中，較易，在后面內(nèi)容中也有用 （下次講） Univ. 可計算理論 2022/8/14 69/70 Summary ?Section : ? Reductions ? Examples of undecidable languages ? Computation histories ? More plex reductions Univ. 可計算理論 2022/8/14 70/70 Any Question ? Thank you !!