计算理论导引-6-可计算理论的高级专题.ppt
1,康熠华,计算理论,第6章 可计算性理论的高级专题,2,主要内容,6.1 递归定理6.1.1 自引用6.1.2 递归定理的术语6.1.3 应用6.2 逻辑理论的可判定性6.2.1 一个可判定的理论6.2.2 一个不可判定的理论6.3 图灵可归约性6.4 信息的定义6.4.1 极小长度的描述 6.4.2 定义的优化 6.4.3 不可压缩的串和随机性,3,逻辑理论的可判定性,数理逻辑是数学的一个分支,它研究数学本身。数理逻辑关心如下问题:什么是定理?什么是证明?什么是真?算法能判定哪些命题是真的?所有真命题都是可证的吗?关心的焦点:能否确定一个数学命题是真是假,以及这种问题的可判定性。,4,逻辑理论的可判定性,命题1称,有无限多个素数存在,在大约2300年以前的欧几里德时代,就已知道这个命题是真的。命题2称为费马大定理,这个命题几年前由安德鲁威尔士(Andrew Wiles)证明为真。命题3称,有无限多个素数对存在,这被称为孪生素数猜想(twin prime conjecture)。它到现在还未被解决。,首先需要建立一个精确的语言来将这些问题形式化。我们的要求是能够考虑如下数学命题:,5,符号,称为布尔运算;“(”和“)”是括号;符号 和 是量词;符号x用来代表变元;符号R1,Rk 称为关系。,逻辑理论的可判定性,为了将之进一步精确化,现在描述这个语言的字母表:,6,公式,公式是字母表上的良构串。形如 Ri(x1,x2,xj)的串是原子公式,值 j 是关系符号 Ri的元数。一个良构公式中所有出现的相同关系符号必须有相同的元数。一个串如满足一下条件,则是一个公式:1)是一个原子公式;2)具有形式1 2 或 1 2或 1。其中1和2 是更小的公式。3)具有形式1 2 或12 或 1。其中 x1 或 x1,其中 1 是更小的公式。,7,公式,辖域:紧跟在量词化变元后的一对括号中的部分。前束范式:所有量词都出现在公式的前面。自由变元:没有被量词的辖域所约束的变元。句子或命题:没有自由变元的公式。,(1)x(F(x,y)G(x,z)(2)x(F(x)G(y)y(H(x)L(x,y,z),8,例6.7 在下列公式中,只有最后一个是句子:,逻辑理论的可判定性,9,逻辑理论的可判定性,论域:覆盖变元可能的取值。将关系符号指定为确定的关系。而关系是从论域上的k元组到TRUE,FALSE的函数。关系符号的元数必须和指派给它的关系和元数相同。论域连同关系到关系符号的指派一起称为模型。形式上,一个模型 M 是一个元组(U,P1,Pk),其中U是论域,P1 到 Pk 是指派给符号 R1 到 Rk 的关系。模型语言:在公式的集合中,只使用此模型指派的关系符号,且对每个关系符号,使用正确的元数。如果是某个模型语言中的句子,则在这个模型中不为真就为假。如果在模型 M 中为真,则说 M 是的一个模型。,10,逻辑理论的可判定性,例6.8 设是句子xy R1(x,y)R1(y,x),模型 M1=(N,)是如下的模型:它的论域是自然数集,它将“小于或等于”关系分配给符号R1。显然在M1中为真,因为对于任意两个自然数 a 和 b,a b 和 ba 必有一个成立。但如果M1将“小于”关系(而不是“小于或等于”关系)指派给R1,则将不真,因为当 x 和 y 相等时,它不再成立。,如果事先知道什么关系将指派给 Ri,就可以用这个关系的惯用记号来代替 Ri,且按习惯,可用中缀记法。对于 M1,可以将写成 xy x y yx,11,例6.9 设 M2 是如下的模型:它的论域是是实数集 R,且讲关系 PLUS 指派给 R1,其中:只要当 a+b=c 时 PLUS(a,b,c)=TURE。则 M2 是=yx R1(x,x,y)的一个模型。但如果用 N 代替 R 作为 M2 的论域,则此句子为假。,逻辑理论的可判定性,如果 M 是一个模型,这个模型语言中所有真句子的集合称为 M 的理论系统,简称为理论,记为Th(M)。,12,一个可判定性的理论,设 3 包含所有高度为 3 的 0 和 1 的列。3 上的字符串给出三行 0 和 1。把每一行看作一个二进制数,令B=w3|w 最下面的一行等于上面两行的和 则 B 是正则的。,13,Th(N,+)是可判定的,考虑如下一个实例:,构造有限自动机:(x1,x2,x3)|x1+x2=x1+x3,然后构造NFA:(x1,x2)|x3 x1+x2=x1+x3,同样:(x1)|x2x3 x1+x2=x1+x3,为真时,得到(),为假时得到。,14,一个可判定性的理论,思路:对于输入为(N,+)的语言中的句子检查其在模型中是否为真。=Q1x1Q2x2 Qlxl 对于 0l 的每一个i,令公式i 为i=Qi+1xi+1Qi+2xi+2 Qlxl 这样,0=且 l=。对于从 0 到 l 的每个 i,算法构造了一个有穷自动机 Ai,它识别如下串的集合:这些串表示i 为真的数的 i 元组。算法先直接构造 Ai,然后,对从 l 向下到 1 的每个 i,它用 Ai 构造 Ai-1。最后,一旦得到 A0,算法就检查 A0是否接受空串。如果接受,则为真,算法也就接受。,15,Th(N,+)是可判定的,则 i=包含了所有 0 和 1 构成的 i元列向量。i 上的每个串表示 i 的二进制整数(沿行读)。令0=,其中 是一个符号。现在介绍判定 Th(N,+)的算法。对于输入(其中为句子),算法如下运行:写下,且对从 0 到 l 的每个 i,如同在证明思路中介绍的那样定义i。再对每个这样的i,由i构造有穷自动机Ai,使得只要i(a1,ai)为真,它就接受i*上对应于i元组a1,ai 的串。Ai 的构造如下:,对 i 0,定义字母表,16,为构造第一个机器 Al,注意到l 是原子公式的布尔组合。在 Th(N,+)的语言中,原子公式只有单个加法。对每个这样的单个加法,可以构造个有穷自动机来计算这样的单个加法所对应的关系,然后将这些有穷自动机组合起来,就能给出自动机Al。这样做要涉及正则语言类对于交、并和补的封闭性,以计算原子公式的布尔组合。接下来说明怎么由 Ai+1 来构造 Ai。如果i=xi+1i+1,则构造 Ai 使得它的运行几乎与Ai+1一样,区别在于 Ai 非确定地猜 ai+1 的值,而不是将它作为输入的一部分而接受。更精确地说,对于 Ai+1 的每个状态,Ai 包含一个与之对应的状态;且 Ai还包含一个新的起始状态。每当 Ai 读下列符号时,,一个可判定性的理论,17,这里每个 bi0,1 是数 ai 的某一位,它非确定地猜 z0,1,且在下列输入符号上模拟 Ai+1。,一个可判定性的理论,最初,Ai 非确定地猜测 ai+1的引导位,这些引导位对应于 a1 到 ai 中隐藏的引导 0。猜测的方法是:从它新的起始状态到所有状态非确定性地进行分叉,这些状态是 Ai+1 以 i+1中下列符号的串为输入、从它的开始状态所能到达的状态。,显然,如果存在ai+1,使得Ai+1接受(a1,ai+1),则Ai接受(a1,ai)。如果i=xi+1i+1,它等价于 xi+1i+1。首先构造识别语言 Ai+1 的补的有穷自动机,然后应用上述对于量词的构造,最后再一次应用补来得到Ai。有穷自动机 A0 接收某个输入,当且仅当0为真。所以算法的最后步骤是检查 A0 是否接收。如果是,则为真,且算法接受它;否则,就拒绝。,18,一个不可判定性的理论,19,一个不可判定性的理论,证明:如果是可证的,则下列算法P接受其输入。算法P使用在可证性性质1中所说的证明检查器,检查每个可能成为的证明的候选串。如果发现一个侯选串正是一个证明,则接受它。,20,证明:用反证法。假设所有真命题都是可证的,利用这个假设来构造判定命题是否为真的算法D,与定理6.11矛盾。对于输入,算法D如下运行:在输入和 上并行地运行定理6.13的证明中给出的算法P。这两个命题总有一个为真,根据假设,总有一个是可证的。因而P在其中一个输入上停机。根据可证性性质2,如果是可证的,则为真;如果 是可证的,则为假。所以算法D能判定的真假性。,一个不可判定性的理论,21,一个不可判定性的理论,证明:设S是如下运行的TM。S“对于任意的输入:1)出递归定理得到它自己的描述。2)用引理6.12构造句子。3)在输入 上运行定理6.13给出的算法P。4)如果上一步接受,就接受;如果它停机且拒绝,则拒绝。”设 是算法S的第二步所描述的句子。为真,当是仅当S不接受0(串0是随意选择的)。如果s能找到 的一个证明,S就接受0,这个句子也就因之为假。一个假句子是不能被证明的,所以这种情形不可能发生。剩下的唯一可能性是S不能找到 的证明,因而S不接受0。但我们已宣布过 为真。,22,主要内容,6.1 递归定理6.1.1 自引用6.1.2 递归定理的术语6.1.3 应用6.2 逻辑理论的可判定性6.2.1 一个可判定的理论6.2.2 一个不可判定的理论6.3 图灵可归约性6.4 信息的定义6.4.1 极小长度的描述 6.4.2 定义的优化 6.4.3 不可压缩的串和随机性,23,图灵可归约性,考虑两个语言ATM和ATM,直观上它们可以互相归约。实际上不能。,24,图灵可归约性,例6.17 考虑 ATM 的一个谕示。带 ATM 的谕示的一个谕示图灵机比普通的团灵机能判定更多的语言,这样的图灵机能够判定ATM自身(显然成立),它只要对输入询问它的谕示即可。它也能判定 ETM,即 TM 的空性质检查问题,用的是下面称 TATM 的过程:TATM=“对于输 入,其中 M 是一个 TM:1)构造下面 TM N:N=“对任意输入:a)对*中的所有串并行运行 M。b)如果 M 接受它们中的任何一个串,则接受。”2)询问谕示以确定 ATM是否成立 3)如果谕示回答“不”,则接受;如果回答“是”,则拒绝。”如果 M 的语言不空,则N将接受每个输入,特别地,将接受 0。从而谕示将回答“是”,且 TATM 将拒绝。相反地,如果M的语言是空的,则 TATM 将接受。所以 TATM 判定 ETM。我们说 ETM 是可判定归约到 ATM。,25,图灵可归约性,26,图灵可归约性,如果 B 是可判定的,则可以用判定 B 的实际过程来替换 B 的谕示。这样就用判定 A 的普通图灵机取代了判定 A 的谕示图灵机。,图灵可归约性是映射可归约性的一个推广。如果AmB,则入ATB,因为此映射归约可以被用来给出一个相对于 B、判定 A 的谕示图灵机。带 ATM 的谕示的谕示图灵机十分强大。它能解许多不能由普通图灵机解的问题。但即使是这样一个强大的图灵机,也不能判定所有语言。,27,主要内容,6.1 递归定理6.1.1 自引用6.1.2 递归定理的术语6.1.3 应用6.2 逻辑理论的可判定性6.2.1 一个可判定的理论6.2.2 一个不可判定的理论6.3 图灵可归约性6.4 信息的定义6.4.1 极小长度的描述 6.4.2 定义的优化 6.4.3 不可压缩的串和随机性,28,信息的定义,序列A 有规律地 重复01串 17次,可压缩为 01#17序列B 比较复杂,短话说不清的,信息量较大直观感觉:表达语义的 最短尺寸,可用来度量其信息量规律性使得描述较短(信息量较小),规律的描述和输入,重复17次 01,TM w,说明可用 w 的长度来描述信息量,29,信息的定义,TM M 的描述和它的输入 x 能被描述为较长的二进制串:,如何才能知道 停止 和 开始?,我们可以给 编码:将 0 写成“00”将 1 写成“11”“01”作为分界分界位置,M 分隔符 w,30,定义6.20,设 x 是二进制数的串,x 的极小描述,记为d(x),是最短的串,其中:TM M 在输入w上停机时,x 在带上。且如果有多个这样的串存在,则在其中选择字典序下的第一个串。X 的描述复杂性记为K(x),是 K(x)=|d(x)|换句话说,K(x)是 x 的极小描述的长度。K(x)的定义是为了刻画串 x 中的信息量这个直观概念的。,信息的定义,31,信息描述复杂性的基本结论,为证明此定理给出的 K(x)的上界,只需给出一个不长于这个上界的 x 的描述。x 的极小描述可能比这个描述更短,但不会更长。考虑串 x 的下列描述。设 M 是这样一个图灵机:它一启动就停机。此图灵机计算恒等函数输出与输入是一样的函数。x 的一个描述是 x。令 c 是 的长度,就可完成证明。,32,定理6.22,串重复的描述复杂性,考虑下列图灵机 M,它要形如 的输入,其中 N 是一个图灵机,w 是它的一个输入。M=“对于输入,其中N是一个图灵机,w 是一个串:1)在 w 上运行 N 直到停止,且产生输出串 s2)输出串 ss。”xx 的一个描述是 d(x),而 d(x)是 x 的最小描述,这个描述的长度是|+d(x),即为 c+K(x),其中 c 是 的长度。,33,串连接的描述复杂性,构造 TM M,它将输入 w 拆成两个单独的描述。在第二个描述 d(y)出现以前,第一个描述 d(x)的所有位都被写两边且以 01 结束,如图6-3所示。在得到两个描述之后,它们就开始运行,得到串 x 与 y,及产生 xy。显然,xy 的这个描述的长度是 x 的复杂性的两倍加上 y 的复杂性,再加上描述 M 的固定常量 c。此和为2K(x)+K(y)+c这就完成了证明。,34,定义的优化,在用算法来定义描述复杂性的所有可能的方法中,关于K(x)的定义具有一个优化性质。假如将一般的描述语言看做一个可计算函数 p:*,并定义 x 相对于 p 的极小描述为满足 p(s)=x 的字典下最短的串 s,记为 dp(s),然后可以定义 Kp(x)=|dp(x)|。例如,将一个程序设计语言,比如 LISP(编码成二进制数),看作描述语言,则 dLISP(x)将是输出 x 的极小 LISP 程序,KLISP(x)将是这个极小程序的长度。任何此种类型的描述语言,都不会明显地比原先定义的图灵机和输入语言更简洁。,35,定义的优化,用LISP例子来说明证明思路。假设 x 有一个短的LISP描述w。令M是一个能解释LISP的TM,且以x的LISP程序w作为输入。则是x的一个描述,且它比x的LISP描述只大一个固定的量。多出的长度是LISP解释器M。,对于输入语言 p,考虑下列图灵机 M:M=“对于输入 w:1)输出 p(w)。”则 dp(x)是 x 的一个描述,它的长度至多比 Kp(x)大一个固定常量,此常量为 的长度。,36,设 x 是一个串,如果则称 x 是 c 可压缩的(c-compressible)。如果 x 不是 c 可压缩的,则称 x 是不可压缩 c 的。如果 x 是不可压缩 1 的,则称 x 是不可压缩的。,定义6.25,不可压缩的串和随机性,37,对于每个长度,都存在不可压缩的串。,定理6.26,证明:长度为n的二进制数串的个数是2n,每个描述都是一个非空的二进制数串,故长度小于n的描述的个数最多为长度小于等于n-1的串的个数之和,即:所以较短描述的个数小于长度为n的串的个数。因此,至少有一个长度为n的串是不可压缩的。,不可压缩的串和随机性,38,至少有2n-2n-c+1+1个长度为n的串是不可压缩c的。,推论6.27,证明:如同定理6.26一样,最多有2n-c+1-1个长度为n的串是c可压缩的。因为最多只有这么多个长度至多为n-c的描述存在。剩下的2n(2n-c+1 1)个都是不可压缩c的。,不可压缩的串和随机性,39,设f是一个对几乎所有串成立的性质,则对任意b0,性质f只在有限多个不可压缩b的串上的值是FALSE。,定理6.28,证明:设M是下列算法:M=“对于输入i,其中i是一个二进制整数:1)在字典序下,找到使得f(s)=FALSE的第i个串s。2)输出串s。”可以用M来得到不具有性质f的串的更短描述,方法如下:设x是这样的串,将所有不具有性质f的串排成一个序列,序列是按长度排序的,同一长度的串按字典序排列。令ix是x在这个序列中的位置或序标(index),则是f的一个描述,这个描述的长度为|ix|+c,其中c是的长度。因为没有性质f的串较少,故x的序标是小的,它的相应描述也是短的。任取b0。选择n,使得:在所有长度小于或等于n的串中,至多有1/2b+c+1不具有性质f。所有足够大的n都满足这个条件,因为f 对几乎所有,不可压缩的串和随机性,40,的串成立。令x是长度为n的没有性质f的串,长度小于等于n的串游2n+1-1个,因此,从而|ix|n b c,故的长度至多为(n b c)+c=n b。这意味着 K(x)n b这样,使得不具有性质f的每个足够长的x都是可压缩b的。因此,只有有限多个不具性质f的串是不可压缩b的。证毕。,不可压缩的串和随机性,41,考虑下列 TM M:M=“对于输入,其中 R 是一个 TM,y 是一个串:1)在 y 上运行 R,且在它的输出不具有形式 时,拒绝。2)在 z 上运行 S,且将它的输出放在带上后停机。”令 b 为|+1,证明 b 满足本定理。如不然,则对某个串 x,d(x)是 b可压缩的。从而|d(d(x)|d(x)|-b但 d(d(x)是 x 的一个描述。它的长度至多为|+|d(d(x)|(b-1)+(|d(x)|-b)=|d(x)|-1x 的这个描述比 d(x)更短。这与后者的极小性矛盾。,不可压缩的串和随机性,42,作业,6.7、6.12、6.15、6.23,