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

1朴秀峰[e-mail]计算理论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递归定理递归定理是一个数学结论，在可计算性理论的高级研究中起着重要的作用。考察与生命科学有关的一个悖论：1)生物都是机器。2)生物都能自再生。3)机器不能自再生。设有构造机器B的机器A：A肯定比B复杂，但一个机器不会比它自己更复杂。因此没有机器能够制造它自己，故自再生是不可能的。？？制造能生产自己的机器是可能的。4递归的意义自己调用自己从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事，讲的故事是：“从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事，讲的故事是……”自我繁殖#includestdio.hmain(){char*c=#includestdio.hmain(){char*c=%c%s%c;printf(c,34,c,34);};printf(c,34,c,34);}5自引用引理6.1存在可计算函数q:**，对任意串w,q(w)是图灵机Pw的描述，Pw打印出w，然后停机。可以任取一个字符串w，然后从它构造一个图灵机，使得此图灵机将w内装在一个表中，这样，当此图灵机开始运行后，它只要简单输出w即可。下列TMQ计算q(w)：Q=“对于输入串w：1)构造下列图灵机Pw：Pw=“对于任意输入：a)抹去输入。b)在带上写下w。c)停机。”2)输出Pw。”6图灵机SELF图灵机SELF忽略输入，且打印出它自己的描述。图灵机SELF有两个部分，分别叫做A和B，将A和B想象成两个分离的过程，它们一起组成SELF。我们希望SELF打印出SELF=AB。A部分首先运行，在根据完成情况将控制传给B。A的任务是打印出B的描述。使用机器PB来定义A，其中PB用函数q在B处的值q(B)描述，这样，A部分是一个打印出B的图灵机。A的描述依赖于是否已经有了B的描述，所以在构造出B之前，无法完成A的描述。定义B，使之能打印A：B从A产生的输出来计算A。如果B能得到B，它就能用q来得到A。当A结束时，它被留在带上。所以B只要看着带子就能得到B。在计算q(B)=A之后，B将之加到带的前面。然后将A和B组合成一个机器并在带上写下它的描述。7图灵机SELFBA(=PB)SELF的控制器…SELF的示意图，一个打印它自己的描述的TMA=P(B)，且B=“对于输入M，其中M是一个TM的一部分：1)计算q(M)。2)将其结果与M结合来组成一个完整的TM描述。3)打印这个描述，然后停机。”8图灵机SELFBA(=PB)SELF的控制器…如果现在运行SELF，能观察到如下动作：1)首先A运行，它在带上打印B；2)B开始运行，它查看带子，找到它的输入B；3)B计算q(B)=A，然后将之与B合并，构成TMSELF的描述SELF。4)B打印这个描述，且停机。9图灵机SELF容易用任何程序设计语言实现这个构造，即得到一个程序，输出就是它自己。也可用自然语言实现：打印这个句子考虑下面的变换打印下面语句的两个副本，在第二个副本上加引号；“打印下面语句的两个副本，在第二个副本上加引号；”本例中，B部分的构造是如下的句子：打印下面语句的两个副本，在第二个副本上加引号；A部分与之相同，只是用引号将之括起来。A提供了B的一个副本给B。10递归定理定理6.2设T是计算函数t:*×**的一个图灵机。则存在计算函数r:**的一个图灵机R，使得对每一个w，有：r(w)=t(R,w)只需要制造一个TMT，使之以自己的描述作为输入的一部分。然后递归定理就产生一个新的机器R，它和T一样运行，只是R的描述被自动地装在T中。ABT(=PBT)R的控制器…11递归定理A是由q(BT)描述的图灵机PBT。为了保持输入w，重新设计q，使得PBT印出任何预先在带上存在的串的输出。在A运行之后，带上包含wBT。B是如下的过程：检查带子，并将q应用于带内容。结果是A。然后B将A、B和T组成一个图灵机，并得到它的描述ABT=R。最后，描述的编码和w结合，在带上形成结果串R,w，并将控制传给T。ABT(=PBT)R的控制器…12递归定理的术语在设计图灵机算法时，可用如下方式使用递归定理。如果你正在设计一个图灵机M，则可以在M的算法的非形式描述中包含如下的短语：“得到自己的描述M”。一旦得到自己的描述，M就能像使用其他已计算出来的值一样使用这个描述。例如，M可以简单打印出M；或者计算M中的状态数；或模拟M。用递归定理来描述机器SELF：SELF=“对于任意输入：1)利用递归定理得到它自己的描述SELF；2)打印SELF。”13递归定理的术语递归定理展示了怎样实现“获得自己的描述”的构造。为了产生机器SELF，首先写下以下机器T：T=“对于输入M,w：1)打印M并停机。”TMT得到TMM和它输入的串w的描述，它打印了M的描述M。然后递归定理展示怎样获得在输入w上的TMR，像T在输入R,w上那样操作。因此R打印出R的描述，恰好是机器SELF所需要得到的。14递归定理的应用计算机病毒是一个计算机程序，它被设计成在计算机中传播它自己。为了实现自我复制的基本任务，可能使用到递归定理证明中的结构。例计算机病毒；（Autoexec.BAT)从A:盘复制到B:盘EchoThisisaVirusprogramIFexistb:\autoexec.batgotoVirusGotoNo_Virus:VirusB:Renameautoexec.batauto.bat//准备冒名顶替Copya:\autoexec.batb://自我复制部分EchoIamVirus//诚实的自白Del*.exe//实施破坏:No_virusA:\Auto//调用原来autoexec.bat，给出平安无事的假象15递归定理的应用定理6.3ATM是不可判定的。假设图灵机H可判定ATM。构造下列图灵机B。B=“对于输入w：1)由递归定理得到自己的一个描述B。2)在输入B,w上运行H。3)得到与H相反的结果，即：如果H拒绝，则接受；如果H接受，则拒绝。”对输入w，B的结果与H相反，所以H不可能判定ATM。16递归定理的应用定义6.4如果M是一个图灵机，则M的描述M的长度是描述M的串中所含符号的个数。如果没有与M等价的图灵机有更短的描述，则称M是极小的。令MINTM＝{M|M是一个极小TM}17递归定理的应用定理6.5MINTM不是图灵可识别的。假设TME枚举MlNTM，然后试图来得到矛盾。构造下列TMC。C=“对于输入w：1)由递归定理得到它自己的一个描述C。2)运行枚举器E，直到一个比C的描述更长的机器D出现。3)在输入w上模拟D。为MINTM是无限的，故E的序列中必定含有TM，其描述比C的描述更长。因此，C的第二步最终将在某个TMD上终止，且D比C更长。然后C就模拟D，且与之等价。因为C比D短且与之等价，故D不可能是极小的，但D又在E产生的序列中出现，这样就得到了矛盾。18递归定理的应用定理6.6设t:**是一个可计算函数，则存在一个图灵机F，使得t(F)描述一个与F等价的图灵机。这里假设如果串不是一个正确的图灵机编码，那么它描述的图灵机立即拒绝。设F是下列图灵机。F=“对于输入w：1)由递归定理得到它自己的一个描述F。2)计算t(F)得到一个TMG的描述。3)在输入w上模拟G。”显然，F和t(F)=G描述了等价的图灵机，因为F模拟G。19主要内容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不可压缩的串和随机性20逻辑理论的可判定性数理逻辑是数学的一个分支，它研究数学本身。数理逻辑关心如下问题：什么是定理？什么是证明？什么是真？算法能判定哪些命题是真的？所有真命题都是可证的吗？关心的焦点：能否确定一个数学命题是真是假，以及这种问题的可判定性。21逻辑理论的可判定性1),[(,1)]2),,,[(,,02)]3),[(,1(2))]nnnqpxypqxyxypabcnabcnabcqpxypqxyxypxyp命题1称，有无限多个素数存在，在大约2300年以前的欧几里德时代，就已知道这个命题是真的。命题2称为费马大定理，这个命题几年前由安德鲁·威尔士(AndrewWiles)证明为真。命题3称，有无限多个素数对存在，这被称为孪生素数猜想(twinprimeconjecture)。它到现在还未被解决。首先需要建立一个精确的语言来将这些问题形式化。我们的要求是能够考虑如下数学命题：22符号∧，∨，┐称为布尔运算；“(”和“)”是括号；符号和是量词；符号x用来代表变元；符号R1，…，Rk称为关系。逻辑理论的可判定性1{,,,(,),,,,,,}kxRR为了将之进一步精确化，现在描述这个语言的字母表：23公式公式是字母表上的良构串。形如Ri(x1,x2,…,xj)的串是原子公式，值j是关系符号Ri的元数。一个良构公式中所有出现的相同关系符号必须有相同的元数。一个串∮如满足一下条件，则是一个公式：1)是一个原子公式；2)具有形式∮1∧∮2或∮1∨∮2或┐∮1。其中∮1和∮2是更小的公式。3)具有形式∮1∧∮2或∮1∨∮2或∮1。其中x[∮1]或x[∮1]，其中∮1是更小的公式。24公式辖域：紧跟在量词化变元后的一对括号中的部分。前束范式：所有量词都出现在公式的前面。自由变元：没有被量词的辖域所约束的变元。句子或命题：没有自由变元的公式。(1)x(F(x,y)→G(x,z))(2)x(F(x)→G(y))→y(H(x)∧L(x,y,z))25例6.7在下列公式中，只有最后一个是句子：逻辑理论的可判定性21121231112123121121231)()(,,)2)[()(,,)]3)[()(,,)]RxRxxxxRxRxxxxxxRxRxxx26逻辑理论的可判定性论域：覆盖变元可能的取值。将关系符号指定为确定的关系。而关系是从论域上的k元组到{TRUE，FALSE}的函数。关系符号的元数必须和指派给它的关系和元数相同。论域连同关系到关系符号的指派一起称为模型。形式上，一个模型M是一个元组(U,P1,…,Pk)，其中U是论域，P1到Pk是指派给符号R1到Rk的关系。模型语言：在公式的集合中，只使用此模型指派的关系符号，且对每个关系符号，使用正确的元数。如果∮是某个模型语言中的句子，则∮在这个模型中不为真就为假。如果∮在模型M中为真，则说M是∮的一个模型。27逻辑理论的可判定性例6.8设∮是句子xy[R1(x,y)∨R1(y,x)]，模型M1=(N,≤)是如下的模型：它的论域是自然数集，它将“小于或等于”关系分配给符号R1。显然∮在M1中为真，因为对于任意两个自然数a和b，a≤b和b≤a必有一个成立。但如果M1将“小于”关系（而不是“小于或等于”关系）指派给R1，则∮将不真，因为当x和y相等时，它不再成立。如果事先知道什么关系将指派给Ri，就可以用这个关系的惯用记号来代替Ri，且按习惯，可用中缀记法。对于M1，可以将∮写成xy[x≤y∨y≤x]28例6.9设M2是如下的模型：它的论域是是实数集R，且讲关系PLUS指派给R1，其中：只要当a+b