计算理论导引可归约性精选文档.ppt

《计算理论导引可归约性精选文档.ppt》由会员分享，可在线阅读，更多相关《计算理论导引可归约性精选文档.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算理论导引可归约性1本讲稿第一页，共三十页前言q本章讨论另外几个不可解的问题本章讨论另外几个不可解的问题。在讨论过程。在讨论过程 中，将介绍中，将介绍一个基本方法，可用来证明问题是计算上不可解的，这个一个基本方法，可用来证明问题是计算上不可解的，这个方法称为方法称为可归约性可归约性。q归约归约旨在将一个问题转化为加一个问题，且使得可以用第旨在将一个问题转化为加一个问题，且使得可以用第二个问题的解来解第一个问题，在日常生活中，虽然不这二个问题的解来解第一个问题，在日常生活中，虽然不这样称呼，但时常会遇见可归约性问题。样称呼，但时常会遇见可归约性问题。q例如，在一个新城市中认路，如果有一张地图，

2、事情就容例如，在一个新城市中认路，如果有一张地图，事情就容易了。这样，就将在城市认路问题归约为得到地图问题。易了。这样，就将在城市认路问题归约为得到地图问题。q从波士顿到巴黎旅行，可归约到两个城市的飞机票，进而从波士顿到巴黎旅行，可归约到两个城市的飞机票，进而归约到找工作问题。归约到找工作问题。q数学上的例子更多。数学上的例子更多。2本讲稿第二页，共三十页前言A AB BC CD Db b5 5b b2 2b b1 1b b3 3b b4 4b b7 7b b6 6B BC CA AD Db b6 6b b2 2b b5 5b b7 7b b4 4b b1 1b b3 33本讲稿第三页，共三十

3、页前言q可归约性总是涉及两个问题，称之为可归约性总是涉及两个问题，称之为 A 和和 B。如果。如果 A 可归约可归约到到 B，就可用，就可用 B 的解来解的解来解 A。q可归约性说的不是怎样去解可归约性说的不是怎样去解 A 或或 B，而是在知道，而是在知道 B 的解时怎的解时怎么去解么去解 A。q归约的归约的目的目的在于在于：将一个问题转化为另一个问题；且用第二：将一个问题转化为另一个问题；且用第二个问题的个问题的解解来解第一个问题。来解第一个问题。q归约的应用（归约的应用（A 可归约到可归约到 B）如果如果 B 是可判定的，则是可判定的，则 A 也是可判定的。也是可判定的。如果如果 A 是不

4、可判定的，则是不可判定的，则 B 也是不可判定的。也是不可判定的。4本讲稿第四页，共三十页主要内容主要内容5.1 语言理论中的不可判定问题语言理论中的不可判定问题5.2 一个简单的不可判定问题（自学）一个简单的不可判定问题（自学）5.3 映射可归约性映射可归约性5.3.1 可计算函数可计算函数5.3.2 映射可归约性的形式定义映射可归约性的形式定义 5本讲稿第五页，共三十页语言理论中的不可判定问题qATM=|M 是一个是一个 TM，且接受，且接受 w qATM 是不可判定的是不可判定的，即确定一个图灵机是否，即确定一个图灵机是否接受接受一个给定一个给定的输入问题是不可判定的。的输入问题是不可判

5、定的。q下面考虑一个与之相关的问题：下面考虑一个与之相关的问题：HALTTM，即确定一个图灵，即确定一个图灵机对给定输入是否机对给定输入是否停机停机（通过接受或拒绝）问题。（通过接受或拒绝）问题。q若将若将 ATM 归约到归约到 HALTTM，就可以，就可以利用利用 ATM 的不可判定性的不可判定性证明证明HALTTM的不可判定性的不可判定性。qHALTTM 的形式化描述的形式化描述 HALTTM=|M是一个是一个TM,且对输入且对输入 w 停机停机6本讲稿第六页，共三十页HALTTM 是不可判定的定理定理定理定理5.15.1HALTTM是不可判定的。是不可判定的。证明思路：反证法。（将证明思

6、路：反证法。（将 ATM 归约到归约到 HALTTM）假设假设 TM R 判定判定 HALTTM，利用，利用 R 可以构造一个判定可以构造一个判定 ATM 的的 TM S。使用使用 R，可以检查，可以检查 M 对对 w 是否停机，是否停机，如果如果 M 对对 w 不停机，不停机，S 就拒绝，因为就拒绝，因为 不在不在 ATM 中。中。如果如果 M 对对 w 确实停机，确实停机，S 就模拟它，而不会有死循环的危险。就模拟它，而不会有死循环的危险。这样，如果这样，如果 TM R 存在，就能判定存在，就能判定 ATM。7本讲稿第七页，共三十页语言理论中的不可判定问题定理定理定理定理5.15.1HAL

7、TTM是不可判定的。是不可判定的。假设假设 TM R 判定判定 HALTTM，由之可以，由之可以构造构造 TM S 来判定来判定ATM，其构造如下：，其构造如下：S=“在输入在输入 上，此处上，此处是是 TM M 和串和串 w 的编码：的编码：1)在输入在输入 上运行上运行 TM R。2)如果如果 R 拒绝，则拒绝，则拒绝拒绝。3)如果如果 R 接受，则在接受，则在 w 上模拟上模拟 M，直到它停机。，直到它停机。4)如果如果 M 已经接受，则已经接受，则接受接受；如果；如果 M 已经拒绝，则已经拒绝，则拒绝拒绝。”显然，如果显然，如果 R 判定判定 HALTTM，则，则 S 判定判定 ATM

8、。因为因为 ATM 是不可判定的，故是不可判定的，故 HALTTM 也必定是不可判定的。也必定是不可判定的。8本讲稿第八页，共三十页语言理论中的不可判定问题定理定理定理定理5.25.2 ETM 是不可判定的。是不可判定的。假设假设 ETM 是可判定的，以此证明是可判定的，以此证明 ATM 是可判定的。是可判定的。设设 R 是判定是判定 ETM 的一个的一个 TM，考虑用，考虑用 R 来构造判定来构造判定 ATM 的的 S。当当 S 收到输入收到输入时，如何运行？时，如何运行？构造构造 S 的一个想法是：输入的一个想法是：输入 上运行上运行 R 且看它是否接受。且看它是否接受。如果是，知道如果是

9、，知道 L(M)是空集，因此是空集，因此M不接受不接受w。如果如果 R 拒绝拒绝 w，则只知道，则只知道 L(M)不空，即不空，即 M 接受某个串，但是不知道是否接受这个接受某个串，但是不知道是否接受这个特定的特定的 w。因此，不能在因此，不能在 上运行上运行 R。目标：目标：修改修改，使得除了，使得除了 w 外，外，M 对所有串都拒绝对所有串都拒绝。ETM=M|M 是一个是一个TM，且，且L(M)=空问题空问题9本讲稿第九页，共三十页语言理论中的不可判定问题定理定理定理定理5.25.2 ETM 是不可判定的。是不可判定的。先用标准术语来写在证明思路中描述的那个修改型机器先用标准术语来写在证明

10、思路中描述的那个修改型机器M1.M1=“在输入在输入x上：上：1)如果如果 xw，则拒绝。，则拒绝。2)如果如果 x=w，则在，则在 x上运行上运行M，当，当M接受时，就接受。接受时，就接受。”这个机器以这个机器以 w 作为它的描述的一部分。检查作为它的描述的一部分。检查 x=w 是否成立的方法很显然，是否成立的方法很显然，即扫描输入并用一个字符一个字符地将它与即扫描输入并用一个字符一个字符地将它与 w 进行比较，就可确定它们是否相同。进行比较，就可确定它们是否相同。ETM=M|M 是一个是一个TM，且，且L(M)=空问题空问题10本讲稿第十页，共三十页语言理论中的不可判定问题再假设再假设 T

11、M R 判定判定 ETM。如下构造判定。如下构造判定 ATM 的的 TM S:S=“在输入在输入 上，此处上，此处 是是 TM M 和串和串 w 的编码：的编码：1)用用 M 和和 w 的描述来构造上述的描述来构造上述 TM M1。2)在输入在输入 上运行上运行 R。3)如果如果 R 接受，则拒绝；如果接受，则拒绝；如果 R 拒绝，则接受。拒绝，则接受。”如果如果 R 是是 ETM 的判定器，则的判定器，则 S 就是就是 ATM 的判定器。的判定器。而而 ATM 的判定器是不存在的，故的判定器是不存在的，故 ETM 必定是不可判定的。必定是不可判定的。定理定理定理定理5.25.2 ETM 是不

12、可判定的。是不可判定的。ETM=M|M 是一个是一个TM，且，且L(M)=空问题空问题11本讲稿第十一页，共三十页语言理论中的不可判定问题q另一个与图灵机有关的计算问题也很有意思，该问题是：另一个与图灵机有关的计算问题也很有意思，该问题是：给定一个图灵机和一个可由某个更简单的计算模型识别的给定一个图灵机和一个可由某个更简单的计算模型识别的 语言，测定此图灵机是否识别此语言语言，测定此图灵机是否识别此语言。q例如：令例如：令REGULARTM是测定一个是测定一个给定的图灵机是否有一个给定的图灵机是否有一个与之等价的有穷自动机与之等价的有穷自动机问题，则这个问题与问题，则这个问题与测定一个给定的测

13、定一个给定的图灵机是否识别一个正则语言图灵机是否识别一个正则语言的问题相同。的问题相同。REGULARTM=|M 是一个是一个 TM，且，且 L(M)是一个正则语言是一个正则语言qREGULARTM 是不可判定的。（定理是不可判定的。（定理5.3）q检查关于语言的任何一个性质是否可由图灵机识别都是不可检查关于语言的任何一个性质是否可由图灵机识别都是不可判定的。（莱斯定理）判定的。（莱斯定理）12本讲稿第十二页，共三十页语言理论中的不可判定问题定理定理定理定理5.45.4EQTM是不可判定的。是不可判定的。将将 ETM 归约到归约到 EQTM。设设TM R判定判定EQTM。如下构造判定。如下构造

14、判定ETM 的的TM S：S=“对于输入对于输入，其中，其中 M 是是 TM：1)在输入在输入上运行上运行 R，其中，其中 M1 是拒绝所有输入的图灵机是拒绝所有输入的图灵机。2)如果如果 R 接受，则接受；如果接受，则接受；如果 R 拒绝，则拒绝。拒绝，则拒绝。如果如果 R 判定判定 EQTM，则，则 S 判定判定ETM。但由定理但由定理5.2，ETM 是不可判定的，故是不可判定的，故 EQTM 也是不可判定的。也是不可判定的。EQTM=M1,M2|M1 和和 M2 都是都是 TM，且，且 L(M1)=L(M2)13本讲稿第十三页，共三十页利用历史计算归约定义定义定义定义5.55.5设设 M

15、 是一个图灵机，是一个图灵机，w 是一个串。是一个串。M 在在 w 上的一个上的一个接受接受计算历史计算历史是一个格局序列是一个格局序列 C1,C2,Cl，其中其中 C1 是是 M 在在 w 上的起始格局，上的起始格局，Cl 是是 M 的一个接受格局，且的一个接受格局，且每个每个 Ci 都是都是 Ci-1 的合法结果，即符合的合法结果，即符合 M 的规则。的规则。M 在在 w 上的一个上的一个拒绝计算历史拒绝计算历史可类似定义，只是可类似定义，只是 Cl 应应是一个拒绝格局。是一个拒绝格局。计算历史计算历史都是有限序列。都是有限序列。如果如果 M 在在 w 上不停机，则二者不存在。上不停机，则

16、二者不存在。确定型图灵机最多只一个计算历史。确定型图灵机最多只一个计算历史。非非确定型图灵机可能有多个计算历史。确定型图灵机可能有多个计算历史。14本讲稿第十四页，共三十页定义定义定义定义5.65.6 线线性性界界限限自自动动机机是是一一种种受受到到限限制制的的图图灵灵机机，它它不不允允许许其其读读写写头头离离开开包包含含输输入入的的带带区区域域。如如果果此此机机器器试试图图将将它它的的读读写写头头移移出出输输入入的的两两个个端端点点，则则读读写写头头就就保保持持在在原原地地不不动动。这这与与普普通通图灵机的读写头不会离开带子的左端点的方式一样。图灵机的读写头不会离开带子的左端点的方式一样。利

17、用历史计算归约的例子定义定义定义定义5.65.6ababa控制器控制器15本讲稿第十五页，共三十页定义定义定义定义5.65.6 设设 M 是是有有 q 个个状状态态和和 g个个带带符符号号的的 LBA。对对于于长长度度为为 n 的带子，的带子，M 恰有恰有 qngn 个不同的格局。个不同的格局。线性界限自动机引理引理引理引理5.75.7 M 的格局就像计算中间的一快照。格局由控制状态、读写头的格局就像计算中间的一快照。格局由控制状态、读写头位置和带内容组成。这里，位置和带内容组成。这里，M 有有 q 个状态。它的带长度是个状态。它的带长度是 n，所，所以读写头可能处于以读写头可能处于 n 个位

18、置之一，且个位置之一，且 gn 多个带符号串可能出现多个带符号串可能出现在带上。此三个量的乘积就是带长为在带上。此三个量的乘积就是带长为n的的M的格局总数。的格局总数。16本讲稿第十六页，共三十页定义定义定义定义5.65.6 ALBA是可判定的。是可判定的。线性界限自动机的可判定问题定理定理定理定理5.85.8L=“对于输入对于输入，其中，其中 M 是是 LBA，w 是串：是串：1)在在 w上模拟上模拟 M qngn步，或者直到它停机。步，或者直到它停机。2)如果如果 M 停机，则当它接受时停机，则当它接受时接受接受，拒绝时，拒绝时拒绝拒绝。如果它还没有停机，就如果它还没有停机，就拒绝拒绝。”

19、如果如果 M 在在 w 上运行上运行 qngn 步还没有停机，步还没有停机，根据引理根据引理5.7，它必定在重复某个格局，即陷入了循环。，它必定在重复某个格局，即陷入了循环。这就是算法为什么在此情形下拒绝的原因。这就是算法为什么在此情形下拒绝的原因。17本讲稿第十七页，共三十页ELBA是不可判定的。是不可判定的。ALLCFG=|G是是 一个一个 CFG 且且 L(G)=*是不可判定的。是不可判定的。线性界限自动机的可判定问题18本讲稿第十八页，共三十页主要内容主要内容5.1 语言理论中的不可判定问题语言理论中的不可判定问题5.2 一个简单的不可判定问题一个简单的不可判定问题(自学自学)5.3

20、映射可归约性映射可归约性5.3.1 可计算函数可计算函数5.3.2 映射可归约性的形式定义映射可归约性的形式定义19本讲稿第十九页，共三十页主要内容主要内容5.1 语言理论中的不可判定问题语言理论中的不可判定问题5.2 一个简单的不可判定问题一个简单的不可判定问题5.3 映射可归约性映射可归约性5.3.1 可计算函数可计算函数5.3.2 映射可归约性的形式定义映射可归约性的形式定义 20本讲稿第二十页，共三十页映射可归约性q将一个问题归约为另一个问题的概念可以用多种方式来形式定将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方式要根据具体应用情况。我们的选择是一义，选择使

21、用哪种方式要根据具体应用情况。我们的选择是一种简单方式的可归约性，叫做种简单方式的可归约性，叫做映射可归约性映射可归约性。q粗略地说，粗略地说，“用映射可归约性将问题用映射可归约性将问题 A 归约为问题归约为问题 B”是指，是指，存存在一个可计算函数在一个可计算函数，它，它将问题将问题 A 的实例转换成问题的实例转换成问题 B 的实例的实例。如。如果有了这样一个转换函数，就能用果有了这样一个转换函数，就能用B的解决方案来解的解决方案来解。原因是，。原因是，A 的任何一个实例可以这样来解：首先用这个归约将的任何一个实例可以这样来解：首先用这个归约将A转换为转换为 B 的一个实例，然后应用的一个实

22、例，然后应用 B 的解决方案。的解决方案。21本讲稿第二十一页，共三十页例例5.13 整数上所有通常的算术运算都是整数上所有通常的算术运算都是可计算函数可计算函数。例例如如，可可以以制制造造一一个个机机器器，它它以以 为为输输入入且且返返回回 m 与与n 的的和和 m+n。定义定义定义定义5.65.6 函函数数 f:*是是一一个个可可计计算算函函数数，如如果果有有某某个个图图灵灵机机 M，使得在每个输入，使得在每个输入w上停机，且此时只有上停机，且此时只有 f(w)出现在带上。出现在带上。可计算函数定义定义定义定义5.125.1222本讲稿第二十二页，共三十页可计算函数例例5.14 可计算函数

23、可以是机器的描述之间的变换可计算函数可以是机器的描述之间的变换。例如，如果例如，如果 w=是图灵机的编码，可以有一个可计算函是图灵机的编码，可以有一个可计算函 数数 f，以，以 w 为输入，且返回一个图灵机的描述为输入，且返回一个图灵机的描述 。M 是一个与是一个与 M 识别相同语言的机器，但识别相同语言的机器，但 M 从不试图将它的从不试图将它的读写头移出它的带的左端点。函数读写头移出它的带的左端点。函数 f 通过在通过在 M 的描述中加入一些的描述中加入一些状态来完成这个任务。如果状态来完成这个任务。如果 M不是图灵机的合法编码，不是图灵机的合法编码，f 就返回就返回 23本讲稿第二十三页

24、，共三十页定义定义定义定义5.65.6语言语言 A 是是映射可归约映射可归约到语言到语言 B 的，如果存在的，如果存在可计算函可计算函数数 f:*使得对每个使得对每个 w，wA f(w)B记作记作AmB。称函数。称函数 f 为为 A 到到 B 的的归约归约。映射可归约性的形式化定义定义定义定义定义5.155.15ABff24本讲稿第二十四页，共三十页定义定义定义定义5.65.6如果如果 AmB 且且 B 是可判定的，则是可判定的，则 A 也是可判定的。也是可判定的。映射可归约性定理定理定理定理5.165.16设设 M 是是 B 的判定器，的判定器，f 是从是从 A 到到 B 的归约。的归约。A

25、 的判定器的判定器 N 的描述如下：的描述如下：N=“对于输入对于输入w：1)计算计算 f(w)。2)在在 f(w)上运行上运行 M，输出，输出 M 的输出的输出。”显然，如果显然，如果 wA，则，则 f(w)B，因为，因为 f 是从是从 A 到到 B 的归约。的归约。因此，只要因此，只要 wA，则，则 M 接受接受 f(w)。故。故 N 的运行如所求。的运行如所求。定义定义定义定义5.65.6如果如果 AmB 且且 A 是不可判定的，则是不可判定的，则 B 也是不可判也是不可判定的。定的。推论推论推论推论5.175.1725本讲稿第二十五页，共三十页例5.8定理定理5.1使用从使用从 ATM

26、 出发的一个，证明了出发的一个，证明了 HALTTM是不可判定。是不可判定。这个归约说明了怎么这个归约说明了怎么用用 HALTTM 的的判定器判定器给出给出 ATM 的判定器的判定器。以下展示以下展示从从 ATM 到到 HALTTM 的的映射可归约性映射可归约性。必须提供一个可计算函数必须提供一个可计算函数 f，它使用形如，它使用形如 的输入，的输入，返回形如返回形如 的输出，使得的输出，使得 ATM 当且仅当当且仅当 HALTTM 下面的机器下面的机器 F 计算了归约计算了归约 f:F=“对于输入对于输入：1)构造下面图灵机构造下面图灵机 M 。M =“对于输入对于输入 x：a.在在 x 上

27、运行上运行 M。b.如果如果 M 接受，则接受。接受，则接受。c.如果如果 M 拒绝，则进入循环。拒绝，则进入循环。2)输出输出。”26本讲稿第二十六页，共三十页映射可归约性q在定理在定理 5.4 的证明中，隐含了一个从的证明中，隐含了一个从 ETM 到到 EQTM 的映射归的映射归约。此归约约。此归约 f 将输入将输入映射到输出映射到输出,其中其中 M1 是拒绝所有输入的机器。是拒绝所有输入的机器。27本讲稿第二十七页，共三十页映射可归约性如果如果AmB，且，且B是可图灵可识别的，则是可图灵可识别的，则A也是图灵可识也是图灵可识别的。别的。定理定理定理定理5.225.22推论推论推论推论5.

28、235.23如果如果AmB，且，且A不是图灵可识别的，则不是图灵可识别的，则B也不是图也不是图灵可识别的。灵可识别的。定理定理定理定理5.245.24EQTM 既不是图灵可识别的，也不是补图灵可识别既不是图灵可识别的，也不是补图灵可识别的。的。28本讲稿第二十八页，共三十页主要内容主要内容5.1 语言理论中的不可判定问题语言理论中的不可判定问题5.2 一个简单的不可判定问题一个简单的不可判定问题5.3 映射可归约性映射可归约性5.3.1 可计算函数可计算函数5.3.2 映射可归约性的形式定义映射可归约性的形式定义 作业：作业：5.1,5.5,5.6,5.28,5.34 29本讲稿第二十九页，共

29、三十页补充抽象模型抽象模型变种变种对应语言对应语言相当于程序或算法相当于程序或算法自动机不确定不确定 NFA正则语言 3型If,case,goto,无变量（内存）无变量（内存）无数组无数组下推机不确定下推机前后文无关语言，2型增加：增加：堆栈。仍无变量堆栈。仍无变量（内存）无数组（内存）无数组不确定线性界限下推机前后文有关语言1型型 语言语言一定停机的图灵机XXX的图灵机 多带,随机，有界递归语言族递归语言族增加数组，变量，内存增加数组，变量，内存保证了不会死循环保证了不会死循环图灵机0型，递归可枚举型，递归可枚举输入在语言外时，可能死输入在语言外时，可能死循环，循环，数学模型，简洁，数学模型，简洁，易分析易分析不要程序细节，易于分析不要程序细节，易于分析本质本质30本讲稿第三十页，共三十页