【正文】 因?yàn)? PCP是不可判定的。 } 上頁 ： Theorem : ALLCFG is undecidable Remember the language EQCFG = {?G1,G2? | G1,G2 CFGs L(G1)=L(G2) }? Cp103 預(yù)告它 不可判定 ,但一直未證明。 //完成了該問題向接受問題的歸約 } 分析 ， 如果 M 拒絕 w 或在 w死循環(huán) ,則 L(PMw)=? ，從而 ?PMw? ?L， 如果 M 接受 W, L(PMw) = L(Q) ，所以 ?PMw??L, 于是 判定 “PMw?L?” ? 判定 “?M,w??ATM?” 矛盾。 else return false。 else return false。} 對(duì)比 cp 115,可知，我們的 SCU表達(dá)法 特別簡潔 EQTM is not even TM or coTM recognizable… 空問題已經(jīng)被證明是不可判定，它可規(guī)約為相等問題 ，所以相等問題不可判定 ?空語機(jī) ?源程序 Univ. 可計(jì)算理論 2022/8/14 42/70 Limited Success thus far 由上可知，規(guī)約（調(diào)用）方法證明問題較簡單 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. 可計(jì)算理論 2022/8/14 43/70 Computation Histories 計(jì)算歷史 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: 接受歷史－格局序列 ，格局 =（寄存器，指令指針，內(nèi)存 ,… ） 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 history C1,…,C k for M on w”. 思想：接受串的格局序列，類似從微分求原函數(shù)，從局部到全局 Univ. 可計(jì)算理論 2022/8/14 44/70 Computation Histories 計(jì)算歷史 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: 接受歷史－格局序列 ，格局 =（寄存器，指令指針，內(nèi)存 ,… ） 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 history C1,…,C k for M on w”. 思想：接受串的格局序列，類似從微分求原函數(shù)，從局部到全局 Univ. 可計(jì)算理論 2022/8/14 45/70 Computation Histories 計(jì)算歷史 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: 接受歷史－格局序列 ，格局 =（寄存器，指令指針，內(nèi)存 ,… ） 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 history C1,…,C k for M on w”. 思想 ：接受串的格局序列，類似從微分求原函數(shù)，從局部到全局 Univ. 可計(jì)算理論 2022/8/14 46/70 Reducing Histories 歷史 計(jì)算的中間過程 cp121 “ ?M,w??ATM” 等價(jià)于 “All histories C1,…,C k are nonaccepting ones for M on w”. Let us list all potential histories by some set X, and check whether x?X is an accepting history for M on w by a Boolean function FMw: FMw(x)=true ?? x是 TM M 接受 w 的歷史 “ ?M,w??ATM” ?? ?x?X: ?FMw(x) “ ?M,w??ATM” ?? ?x?X: FMw(x) Univ. 可計(jì)算理論 2022/8/14 47/70 Reducing Histories 歷史 計(jì)算的中間過程 “ ?M,w??ATM” 等價(jià)于 “All histories C1,…,C k are nonaccepting ones for M on w”. Let us list all potential histories by some set X, and check whether x?X is an accepting history for M on w by a Boolean function FMw: FMw(x)=true ?? x是 TM M 接受 w 的 歷史 “ ?M,w??ATM” ?? ?x?X: ?FMw(x) “ ?M,w??ATM” ?? ?x?X: FMw(x) Univ. 可計(jì)算理論 2022/8/14 48/70 Reducing Histories 歷史 計(jì)算的中間過程 “ ?M,w??ATM” 等價(jià)于 “All histories C1,…,C k are nonaccepting ones for M on w”. Let us list all potential histories by some set X, and check whether x?X is an accepting history for M on w by a Boolean function FMw: FMw(x)=true ?? x是 TM M 接受 w 的歷史 “ ?M,w??ATM” ?? ?x?X: ?FMw(x) “ ?M,w??ATM” ?? ?x?X: FMw(x) 造一個(gè)布爾函數(shù) Univ. 可計(jì)算理論 2022/8/14 49/70 用接受歷史（ 計(jì)算的中間過程） 解決的若干問題 Hilbert’s 10th Problem 復(fù)習(xí) cp97 Univ. 可計(jì)算理論 2022/8/14 50/70 用接受歷史 解決的若干問題 Hilbert’s 10th Problem again cp97 Decision problem: Let P(x1,…,x n) be a polynomial in n variables ?(x1,…,x n) ? Zn: P(x1,…,x n) = 0? 不定方程是否有解， 例如費(fèi)馬問題 是否可判定（寫程序來判斷）？ 表達(dá)計(jì)算歷史為元組 ( x= (x1,…,x n) ?Zn)的序列。 所以被調(diào)用者也不可判定 Univ. 可計(jì)算理論 2022/8/14 63/70 Undecidability ?學(xué)習(xí)了若干不可判定問題， ?不容易證明， 但 結(jié)果是容易理解的 。有的書先證明它，然后用它證明停機(jī)問題不可判定。成為 PCP是不可判定的。 //被調(diào) } 分析 y?ALLCFG ?? y != M在 W上的計(jì)算歷史 ?? M不接受 W y ? ALLCFG ?? y == M在 W上的計(jì)算歷史 ?? M接受 W 于是推出 接受問題可判定，矛盾。一個(gè)個(gè)證明太麻煩，它們有共同規(guī)律： SOMETM = { ?M? | L(M) with Some property } 先補(bǔ)充一個(gè) Rice?s定理，把他們統(tǒng)一解決 Univ. 可計(jì)算理論 2022/8/14 27/70 Rice’s Theorem (習(xí)題 ) 準(zhǔn)備討論 定理５ .3 ,cp120 RegularTM = { ?M? | L(M) is a regular language} 直觀解釋 ： 一切 能識(shí)別正則語言的圖靈機(jī)的集合。 Univ. 可計(jì)算理論 2022/8/14 1/70 Lecture Notes for Computation Book :《 計(jì)算理論導(dǎo)引 》 Introduction to the Theory of Computation Chap5 Reductions (可歸約性） Professor : 唐常杰 Students : . 20222022, SCU Style : Lecture / Seminar Univ. 可計(jì)算理論 2022/8/14 2/70 Univ. 可計(jì)算理論 2022/8/14 3/70 Univ. 可計(jì)算理論 2022/8/14 4/70 Outline for today ?Section : ? Reductions ? Examples of undecidable languages ? Computation histories ? More plex reductions Univ. 可計(jì)算理論 2022/8/14 5/70 復(fù)習(xí) Last lesson coTM recognizable 語言族 TMrecognizable 語言族 TM decidable ETM = { ?M? | M is a TM with L(M)=? } EQTM = { ?G,H? | G,H TMs with L(G)=L(H) } ATM = { ?M,w? | M