可归约

1朴秀峰[e-mail]计算理论2前言本章讨论另外几个不可解的问题。在讨论过程中，将介绍一个基本方法，可用来证明问题是计算上不可解的，这个方法称为可归约性。归约旨在将一个问题转化为加一个问题，且使得可以用第二个问题的解来解第一个问题，在日常生活中，虽然不这样称呼，但时常会遇见可归约性问题。例如，在一个新城市中认路，如果有一张地图，事情就容易了。这样，就将在城市认路问题归约为得到地图问题。从波士顿到巴黎旅行，可归约到两个城市的飞机票，进而归约到找工作问题。数学上的例子更多。3前言ABCDb5b2b1b3b4b7b6BCADb6b2b5b7b4b1b34前言可归约性总是涉及两个问题，称之为A和B。如果A可归约到B，就可用B的解来解A。可归约性说的不是怎样去解A或B，而是在知道B的解时怎么去解A。归约的目的在于：将一个问题转化为另一个问题；且用第二个问题的解来解第一个问题。归约的应用（A可归约到B）如果B是可判定的，则A也是可判定的。如果A是不可判定的，则B也是不可判定的。5主要内容5.1语言理论中的不可判定问题5.2一个简单的不可判定问题（自学）5.3映射可归约性5.3.1可计算函数5.3.2映射可归约性的形式定义6语言理论中的不可判定问题ATM={M,w|M是一个TM，且接受w}ATM是不可判定的，即确定一个图灵机是否接受一个给定的输入问题是不可判定的。下面考虑一个与之相关的问题：HALTTM，即确定一个图灵机对给定输入是否停机（通过接受或拒绝）问题。若将ATM归约到HALTTM，就可以利用ATM的不可判定性证明HALTTM的不可判定性。HALTTM的形式化描述HALTTM={M,w|M是一个TM,且对输入w停机}7HALTTM是不可判定的定理5.1HALTTM是不可判定的。证明思路：反证法。（将ATM归约到HALTTM）假设TMR判定HALTTM，利用R可以构造一个判定ATM的TMS。使用R，可以检查M对w是否停机，如果M对w不停机，S就拒绝，因为M,w不在ATM中。如果M对w确实停机，S就模拟它，而不会有死循环的危险。这样，如果TMR存在，就能判定ATM。8语言理论中的不可判定问题定理5.1HALTTM是不可判定的。假设TMR判定HALTTM，由之可以构造TMS来判定ATM，其构造如下：S=“在输入M,w上，此处M,w是TMM和串w的编码：1)在输入M,w上运行TMR。2)如果R拒绝，则拒绝。3)如果R接受，则在w上模拟M，直到它停机。4)如果M已经接受，则接受；如果M已经拒绝，则拒绝。”显然，如果R判定HALTTM，则S判定ATM。因为ATM是不可判定的，故HALTTM也必定是不可判定的。9语言理论中的不可判定问题定理5.2ETM是不可判定的。假设ETM是可判定的，以此证明ATM是可判定的。设R是判定ETM的一个TM，考虑用R来构造判定ATM的S。当S收到输入M,w时，如何运行？构造S的一个想法是：输入M上运行R且看它是否接受。如果是，知道L(M)是空集，因此M不接受w。如果R拒绝w，则只知道L(M)不空，即M接受某个串，但是不知道是否接受这个特定的w。因此，不能在M上运行R。目标：修改M，使得除了w外，M对所有串都拒绝。ETM={M|M是一个TM，且L(M)=}空问题10语言理论中的不可判定问题定理5.2ETM是不可判定的。先用标准术语来写在证明思路中描述的那个修改型机器M1.M1=“在输入x上：1)如果x≠w，则拒绝。2)如果x=w，则在x上运行M，当M接受时，就接受。”这个机器以w作为它的描述的一部分。检查x=w是否成立的方法很显然，即扫描输入并用一个字符一个字符地将它与w进行比较，就可确定它们是否相同。ETM={M|M是一个TM，且L(M)=}空问题11语言理论中的不可判定问题再假设TMR判定ETM。如下构造判定ATM的TMS:S=“在输入M,w上，此处M,w是TMM和串w的编码：1)用M和w的描述来构造上述TMM1。2)在输入M1上运行R。3)如果R接受，则拒绝；如果R拒绝，则接受。”如果R是ETM的判定器，则S就是ATM的判定器。而ATM的判定器是不存在的，故ETM必定是不可判定的。定理5.2ETM是不可判定的。ETM={M|M是一个TM，且L(M)=}空问题12语言理论中的不可判定问题另一个与图灵机有关的计算问题也很有意思，该问题是：给定一个图灵机和一个可由某个更简单的计算模型识别的语言，测定此图灵机是否识别此语言。例如：令REGULARTM是测定一个给定的图灵机是否有一个与之等价的有穷自动机问题，则这个问题与测定一个给定的图灵机是否识别一个正则语言的问题相同。REGULARTM={M|M是一个TM，且L(M)是一个正则语言}REGULARTM是不可判定的。（定理5.3）检查关于语言的任何一个性质是否可由图灵机识别都是不可判定的。（莱斯定理）13语言理论中的不可判定问题定理5.4EQTM是不可判定的。将ETM归约到EQTM。设TMR判定EQTM。如下构造判定ETM的TMS：S=“对于输入M，其中M是TM：1)在输入M,M1上运行R，其中M1是拒绝所有输入的图灵机。2)如果R接受，则接受；如果R拒绝，则拒绝。如果R判定EQTM，则S判定ETM。但由定理5.2，ETM是不可判定的，故EQTM也是不可判定的。EQTM={M1,M2|M1和M2都是TM，且L(M1)=L(M2)}14利用历史计算归约定义5.5设M是一个图灵机，w是一个串。M在w上的一个接受计算历史是一个格局序列C1,C2,…Cl，其中C1是M在w上的起始格局，Cl是M的一个接受格局，且每个Ci都是Ci-1的合法结果，即符合M的规则。M在w上的一个拒绝计算历史可类似定义，只是Cl应是一个拒绝格局。计算历史都是有限序列。如果M在w上不停机，则二者不存在。确定型图灵机最多只一个计算历史。非确定型图灵机可能有多个计算历史。15定义5.6线性界限自动机是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移出输入的两个端点，则读写头就保持在原地不动。这与普通图灵机的读写头不会离开带子的左端点的方式一样。利用历史计算归约的例子定义5.6ababa控制器16定义5.6设M是有q个状态和g个带符号的LBA。对于长度为n的带子，M恰有qngn个不同的格局。线性界限自动机引理5.7M的格局就像计算中间的一快照。格局由控制状态、读写头位置和带内容组成。这里，M有q个状态。它的带长度是n，所以读写头可能处于n个位置之一，且gn多个带符号串可能出现在带上。此三个量的乘积就是带长为n的M的格局总数。17定义5.6ALBA是可判定的。线性界限自动机的可判定问题定理5.8L=“对于输入M,w，其中M是LBA，w是串：1)在w上模拟Mqngn步，或者直到它停机。2)如果M停机，则当它接受时接受，拒绝时拒绝。如果它还没有停机，就拒绝。”如果M在w上运行qngn步还没有停机，根据引理5.7，它必定在重复某个格局，即陷入了循环。这就是算法为什么在此情形下拒绝的原因。18ELBA是不可判定的。ALLCFG={G|G是一个CFG且L(G)=*}是不可判定的。线性界限自动机的可判定问题19主要内容5.1语言理论中的不可判定问题5.2一个简单的不可判定问题(自学)5.3映射可归约性5.3.1可计算函数5.3.2映射可归约性的形式定义20主要内容5.1语言理论中的不可判定问题5.2一个简单的不可判定问题5.3映射可归约性5.3.1可计算函数5.3.2映射可归约性的形式定义21映射可归约性将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方式要根据具体应用情况。我们的选择是一种简单方式的可归约性，叫做映射可归约性。粗略地说，“用映射可归约性将问题A归约为问题B”是指，存在一个可计算函数，它将问题A的实例转换成问题B的实例。如果有了这样一个转换函数，就能用B的解决方案来解。原因是，A的任何一个实例可以这样来解：首先用这个归约将A转换为B的一个实例，然后应用B的解决方案。22例5.13整数上所有通常的算术运算都是可计算函数。例如，可以制造一个机器，它以m,n为输入且返回m与n的和m+n。定义5.6函数f:**是一个可计算函数，如果有某个图灵机M，使得在每个输入w上停机，且此时只有f(w)出现在带上。可计算函数定义5.1223可计算函数例5.14可计算函数可以是机器的描述之间的变换。例如，如果w=M是图灵机的编码，可以有一个可计算函数f，以w为输入，且返回一个图灵机的描述M。M是一个与M识别相同语言的机器，但M从不试图将它的读写头移出它的带的左端点。函数f通过在M的描述中加入一些状态来完成这个任务。如果M不是图灵机的合法编码，f就返回24定义5.6语言A是映射可归约到语言B的，如果存在可计算函数f:**使得对每个w，w∈Af(w)∈B记作A≤mB。称函数f为A到B的归约。映射可归约性的形式化定义定义5.15ABff25定义5.6如果A≤mB且B是可判定的，则A也是可判定的。映射可归约性定理5.16设M是B的判定器，f是从A到B的归约。A的判定器N的描述如下：N=“对于输入w：1)计算f(w)。2)在f(w)上运行M，输出M的输出。”显然，如果w∈A，则f(w)∈B，因为f是从A到B的归约。因此，只要w∈A，则M接受f(w)。故N的运行如所求。定义5.6如果A≤mB且A是不可判定的，则B也是不可判定的。推论5.1726例5.8定理5.1使用从ATM出发的一个，证明了HALTTM是不可判定。这个归约说明了怎么用HALTTM的判定器给出ATM的判定器。以下展示从ATM到HALTTM的映射可归约性。必须提供一个可计算函数f，它使用形如M,w的输入，返回形如M,w的输出，使得M,w∈ATM当且仅当M,w∈HALTTM下面的机器F计算了归约f:F=“对于输入M,w：1)构造下面图灵机M。M=“对于输入x：a.在x上运行M。b.如果M接受，则接受。c.如果M拒绝，则进入循环。2)输出M,w。”27映射可归约性在定理5.4的证明中，隐含了一个从ETM到EQTM的映射归约。此归约f将输入M映射到输出M，M1,其中M1是拒绝所有输入的机器。28映射可归约性如果A≤mB，且B是可图灵可识别的，则A也是图灵可识别的。定理5.22推论5.23如果A≤mB，且A不是图灵可识别的，则B也不是图灵可识别的。定理5.24EQTM既不是图灵可识别的，也不是补图灵可识别的。29主要内容5.1语言理论中的不可判定问题5.2一个简单的不可判定问题5.3映射可归约性5.3.1可计算函数5.3.2映射可归约性的形式定义作业：5.1,5.5,5.6,5.28,5.3430补充抽象模型变种对应语言相当于程序或算法自动机不确定NFA•正则语言•3型If,case,goto,无变量（内存）无数组下推机不确定下推机前后文无关语言，2型增加：堆栈。仍无变量（内存）无数组不确定线性界限下推机前后文有关语言1型语言一定停机的图灵机XXX的图灵机多带,随机，有界递归语言族增加数组，变量，内存保证了不会死循环图灵机0型，递归可枚举输入在语言外时，可能死循环，数学模型，简洁，易分析不要程序细节，易于分析本质