计算理论导引-6-可计算理论的高级专题.ppt

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