计算理论导引6可计算理论的高级专题.ppt
《计算理论导引6可计算理论的高级专题.ppt》由会员分享,可在线阅读,更多相关《计算理论导引6可计算理论的高级专题.ppt(59页珍藏版)》请在三一办公上搜索。
1、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,递归定理,递归定理是一个数学结论,在可计算性理论的高级研究中起着重要的作用。考察与生命科学有关的一个悖论:1)生物都是机器。2)生物都能自再生。3)机器不能自再生。设有构造机器 B 的机器 A:A 肯定比 B 复杂,但一个机器不会比它自己更复杂
2、。因此没有机器能够制造它自己,故自再生是不可能的。?制造能生产自己的机器是可能的。,4,递归的意义,自己调用自己从前有个庙,庙里有个老和尚,老和尚给小和尚讲故事,讲的故事是:“从前有个庙,庙里有个老和尚,老和尚给小和尚讲故事,讲的故事是”,自我繁殖#include main()char*c=#include main()char*c=%c%s%c;printf(c,34,c,34);printf(c,34,c,34);,5,自引用,可以任取一个字符串 w,然后从它构造一个图灵机,使得此图灵机将 w内装在一个表中,这样,当此图灵机开始运行后,它只要简单输出 w 即可。下列 TM Q 计算 q(w
3、):Q=“对于输入串 w:1)构造下列图灵机 Pw:Pw=“对于任意输入:a)抹去输入。b)在带上写下 w。c)停机。”2)输出。”,6,图灵机 SELF,图灵机 SELF 忽略输入,且打印出它自己的描述。图灵机 SELF 有两个部分,分别叫做 A 和 B,将 A 和 B 想象成两个分离的过程,它们一起组成 SELF。我们希望 SELF 打印出=。A 部分首先运行,在根据完成情况将控制传给 B。A 的任务是打印出 B 的描述。使用机器 P 来定义 A,其中 P用函数 q 在 处的值q()描述,这样,A 部分是一个打印出 的图灵机。A 的描述依赖于是否已经有了 B 的描述,所以在构造出 B 之前
4、,无法完成 A 的描述。定义 B,使之能打印 A:B 从 A 产生的输出来计算 A。如果 B 能得到,它就能用 q 来得到。当 A 结束时,它被留在带上。所以 B 只要看着带子就能得到。在计算 q()=之后,B 将之加到带的前面。然后将 A 和 B 组合成一个机器并在带上写下它的描述。,7,图灵机 SELF,B,A,(=P),SELF 的控制器,SELF 的示意图,一个打印它自己的描述的 TM,A=P(B),且B=“对于输入,其中 M 是一个 TM 的一部分:1)计算 q()。2)将其结果与 结合来组成一个完整的 TM 描述。3)打印这个描述,然后停机。”,8,图灵机 SELF,B,A,(=P
5、),SELF 的控制器,如果现在运行 SELF,能观察到如下动作:,1)首先 A 运行,它在带上打印;2)B 开始运行,它查看带子,找到它的输入;3)B 计算 q()=,然后将之与 合并,构成 TM SELF 的描述。4)B 打印这个描述,且停机。,9,图灵机 SELF,容易用任何程序设计语言实现这个构造,即得到一个程序,输出就是它自己。也可用自然语言实现:打印这个句子考虑下面的变换打印下面语句的两个副本,在第二个副本上加引号;“打印下面语句的两个副本,在第二个副本上加引号;”本例中,B 部分的构造是如下的句子:打印下面语句的两个副本,在第二个副本上加引号;A 部分与之相同,只是用引号将之括起
6、来。A 提供了 B 的一个副本给 B。,10,递归定理,只需要制造一个 TM T,使之以自己的描述作为输入的一部分。然后递归定理就产生一个新的机器 R,它和 T 一样运行,只是 R 的描述被自动地装在 T 中。,A,B,T,(=P),R 的控制器,11,递归定理,A 是由 q()描述的图灵机 P。为了保持输入w,重新设计 q,使得 P 印出任何预先在带上存在的串的输出。在 A 运行之后,带上包含 w。B 是如下的过程:检查带子,并将 q 应用于带内容。结果是。然后 B 将 A、B 和 T 组成一个图灵机,并得到它的描述=。最后,描述的编码和 w 结合,在带上形成结果串,并将控制传给 T。,A,
7、B,T,(=P),R 的控制器,12,递归定理的术语,在设计图灵机算法时,可用如下方式使用递归定理。如果你正在设计一个图灵机 M,则可以在 M 的算法的非形式描述中包含如下的短语:“得到自己的描述”。一旦得到自己的描述,M 就能像使用其他已计算出来的值一样使用这个描述。例如,M 可以简单打印出;或者计算 中的状态数;或模拟。用递归定理来描述机器 SELF:SELF=“对于任意输入:1)利用递归定理得到它自己的描述;2)打印。”,13,递归定理的术语,递归定理展示了怎样实现“获得自己的描述”的构造。为了产生机器 SELF,首先写下以下机器 T:T=“对于输入:1)打印 并停机。”TM T 得到
8、TM M 和它输入的串 w 的描述,它打印了 M 的描述。然后递归定理展示怎样获得在输入 w 上的 TM R,像 T 在输入 上那样操作。因此 R 打印出 R 的描述,恰好是机器 SELF 所需要得到的。,14,递归定理的应用,计算机病毒是一个计算机程序,它被设计成在计算机中传播它自己。为了实现自我复制的基本任务,可能使用到递归定理证明中的结构。,例 计算机病毒;(Autoexec.BAT)从A:盘 复制 到B:盘 Echo This is a Virus program IF exist b:autoexec.bat goto Virus Goto No_Virus:Virus B:Rena
9、me autoexec.bat auto.bat/准备冒名顶替 Copy a:autoexec.bat b:/自我复制部分 Echo I am Virus/诚实的自白 Del*.exe/实施破坏:No_virus A:Auto/调用原来 autoexec.bat,给出平安无事的假象,15,递归定理的应用,假设图灵机 H 可判定 ATM。构造下列图灵机 B。B=“对于输入 w:1)由递归定理得到自己的一个描述。2)在输入 上运行 H。3)得到与 H 相反的结果,即:如果 H 拒绝,则接受;如果 H 接受,则拒绝。”对输入w,B 的结果与 H 相反,所以 H 不可能判定 ATM。,16,递归定理的
10、应用,定义6.4,如果 M 是一个图灵机,则 M 的描述 的长度是描述 M 的串中所含符号的个数。如果没有与 M 等价的图灵机有更短的描述,则称 M 是极小的。令MINTM|M 是一个极小 TM,17,递归定理的应用,假设 TM E 枚举MlNTM,然后试图来得到矛盾。构造下列 TM C。C=“对于输入 w:1)由递归定理得到它自己的一个描述。2)运行枚举器 E,直到一个比 C 的描述更长的机器D出现。3)在输入 w上模拟 D。为 MINTM 是无限的,故 E 的序列中必定含有 TM,其描述比 C 的描述更长。因此,C 的第二步最终将在某个 TM D上终止,且 D 比 C 更长。然后 C 就模
11、拟 D,且与之等价。因为 C 比 D 短且与之等价,故 D 不可能是极小的,但D又在 E 产生的序列中出现,这样就得到了矛盾。,18,递归定理的应用,设 F 是下列图灵机。F=“对于输入w:1)由递归定理得到它自己的一个描述。2)计算 t()得到一个 TM G 的描述。3)在输入w上模拟 G。”显然,和 t()=描述了等价的图灵机,因为 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
12、.4.2 定义的优化 6.4.3 不可压缩的串和随机性,20,逻辑理论的可判定性,数理逻辑是数学的一个分支,它研究数学本身。数理逻辑关心如下问题:什么是定理?什么是证明?什么是真?算法能判定哪些命题是真的?所有真命题都是可证的吗?关心的焦点:能否确定一个数学命题是真是假,以及这种问题的可判定性。,21,逻辑理论的可判定性,命题1称,有无限多个素数存在,在大约2300年以前的欧几里德时代,就已知道这个命题是真的。命题2称为费马大定理,这个命题几年前由安德鲁威尔士(Andrew Wiles)证明为真。命题3称,有无限多个素数对存在,这被称为孪生素数猜想(twin prime conjecture)
13、。它到现在还未被解决。,首先需要建立一个精确的语言来将这些问题形式化。我们的要求是能够考虑如下数学命题:,22,符号,称为布尔运算;“(”和“)”是括号;符号 和 是量词;符号x用来代表变元;符号R1,Rk 称为关系。,逻辑理论的可判定性,为了将之进一步精确化,现在描述这个语言的字母表:,23,公式,公式是字母表上的良构串。形如 Ri(x1,x2,xj)的串是原子公式,值 j 是关系符号 Ri的元数。一个良构公式中所有出现的相同关系符号必须有相同的元数。一个串如满足一下条件,则是一个公式:1)是一个原子公式;2)具有形式1 2 或 1 2或 1。其中1和2 是更小的公式。3)具有形式1 2 或
14、12 或 1。其中 x1 或 x1,其中 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 在下列公式中,只有最后一个是句子:,逻辑理论的可判定性,26,逻辑理论的可判定性,论域:覆盖变元可能的取值。将关系符号指定为确定的关系。而关系是从论域上的k元组到TRUE,FALSE的函数。关系符号的元数必须和指派给它的关系和元数相同。论域连同关系到关系符号的指派
15、一起称为模型。形式上,一个模型 M 是一个元组(U,P1,Pk),其中U是论域,P1 到 Pk 是指派给符号 R1 到 Rk 的关系。模型语言:在公式的集合中,只使用此模型指派的关系符号,且对每个关系符号,使用正确的元数。如果是某个模型语言中的句子,则在这个模型中不为真就为假。如果在模型 M 中为真,则说 M 是的一个模型。,27,逻辑理论的可判定性,例6.8 设是句子xy R1(x,y)R1(y,x),模型 M1=(N,)是如下的模型:它的论域是自然数集,它将“小于或等于”关系分配给符号R1。显然在M1中为真,因为对于任意两个自然数 a 和 b,a b 和 ba 必有一个成立。但如果M1将“
16、小于”关系(而不是“小于或等于”关系)指派给R1,则将不真,因为当 x 和 y 相等时,它不再成立。,如果事先知道什么关系将指派给 Ri,就可以用这个关系的惯用记号来代替 Ri,且按习惯,可用中缀记法。对于 M1,可以将写成 xy x y yx,28,例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
17、的理论系统,简称为理论,记为Th(M)。,29,一个可判定性的理论,设 3 包含所有高度为 3 的 0 和 1 的列。3 上的字符串给出三行 0 和 1。把每一行看作一个二进制数,令B=w3|w 最下面的一行等于上面两行的和 则 B 是正则的。,30,Th(N,+)是可判定的,考虑如下一个实例:,构造有限自动机:(x1,x2,x3)|x1+x2=x1+x3,然后构造NFA:(x1,x2)|x3 x1+x2=x1+x3,同样:(x1)|x2x3 x1+x2=x1+x3,为真时,得到(),为假时得到。,31,一个可判定性的理论,思路:对于输入为(N,+)的语言中的句子检查其在模型中是否为真。=Q1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 理论 导引 可计算 高级 专题

链接地址:https://www.31ppt.com/p-6024203.html