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

《计算理论导引-6-可计算理论的高级专题ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算理论导引-6-可计算理论的高级专题ppt课件.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。朴秀峰朴秀峰计算理论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 极小长度的描述极小长度

2、的描述 6.4.2 定义的优化定义的优化 6.4.3 不可压缩的串和随机性不可压缩的串和随机性2严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归定理q递归定理是一个数学结论，在可计算性理论的高级研究中递归定理是一个数学结论，在可计算性理论的高级研究中起着重要的作用。起着重要的作用。q考察与生命科学有关的一个悖论：考察与生命科学有关的一个悖论：1)生物都是机器。生物都是机器。2)生物都能自再生。生物都能自再生。3)机器不能自再生。机器不能自再生。q设有构造机器设有构造机器 B 的机器的机器 A：A 肯定比肯定比 B 复杂，但一个

3、机器复杂，但一个机器不会比它自己更复杂。因此没有机器能够制造它自己，故不会比它自己更复杂。因此没有机器能够制造它自己，故自再生是不可能的。？自再生是不可能的。？q制造能生产自己的机器是可能的。制造能生产自己的机器是可能的。3严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归的意义q自己调用自己自己调用自己从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事，从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事，讲的故事是：讲的故事是：“从前有个庙，庙里有个老和尚，老和尚给从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事，讲的故事是小和尚

4、讲故事，讲的故事是”q自我繁殖自我繁殖#include main()char*c=#include main()char*c=%c%s%c;printf(c,34,c,34);printf(c,34,c,34);4严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。自引用引理引理引理引理6.16.1存在可计算函数存在可计算函数 q:*，对任意串，对任意串 w,q(w)是是图灵机图灵机 Pw 的描述，的描述，Pw 打印出打印出 w，然后停机。，然后停机。q可以任取一个字符串可以任取一个字符串 w，然后从它构造一个图灵机，使得此图灵机将，

5、然后从它构造一个图灵机，使得此图灵机将 w内装在一个表中，这样，当此图灵机开始运行后，它只要简单输出内装在一个表中，这样，当此图灵机开始运行后，它只要简单输出 w 即即可。可。下列下列 TM Q 计算计算 q(w)：Q=“对于输入串对于输入串 w：1)构造下列图灵机构造下列图灵机 Pw：Pw =“对于任意输入：对于任意输入：a)抹去输入。抹去输入。b)在带上写下在带上写下 w。c)停机。停机。”2)输出输出。”5严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。图灵机 SELF图灵机图灵机 SELF 忽略输入，且打印出它自己的描述。

6、忽略输入，且打印出它自己的描述。图灵机图灵机 SELF 有两个部分，分别叫做有两个部分，分别叫做 A 和和 B，将，将 A 和和 B 想象成两个分离的想象成两个分离的过程，它们一起组成过程，它们一起组成 SELF。我们希望我们希望 SELF 打印出打印出 =。A 部分首先运行，在根据完成情况将控制传给部分首先运行，在根据完成情况将控制传给 B。A 的任务是打印出的任务是打印出 B 的的描述。描述。使用机器使用机器 P 来定义来定义 A，其中，其中 P用函数用函数 q 在在 处的值处的值q()描述描述，这，这样，样，A 部分是一个打印出部分是一个打印出 的图灵机。的图灵机。A 的描述依赖于是否已

7、经有了的描述依赖于是否已经有了 B 的描述，所以在构造出的描述，所以在构造出 B 之前，无法完成之前，无法完成 A 的描述。的描述。定义定义 B，使之能打印，使之能打印 A：B 从从 A 产生的输出来计算产生的输出来计算 A。如果如果 B 能得到能得到，它就能用，它就能用 q 来得到来得到。当。当 A 结束时，它被留在带上。结束时，它被留在带上。所以所以 B 只要看着带子就能得到只要看着带子就能得到。在计算。在计算 q()=之后，之后，B 将之将之加到带的前面。加到带的前面。然后将然后将 A 和和 B 组合成一个机器并在带上写下它的描述。组合成一个机器并在带上写下它的描述。6严格执行突发事件上

8、报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。图灵机 SELFBA(=P)SELF 的控制器的控制器SELF 的示意图，一个打印它自己的描述的的示意图，一个打印它自己的描述的 TMA=P(B)，且，且B=“对于输入对于输入，其中，其中 M 是一个是一个 TM 的一部分：的一部分：1)计算计算 q()。2)将其结果与将其结果与 结合来组成一个完整的结合来组成一个完整的 TM 描述。描述。3)打印这个描述，然后停机。打印这个描述，然后停机。”7严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事

9、件。图灵机 SELFBA(=P)SELF 的控制器的控制器如果现在运行如果现在运行 SELF，能观察到如下动作：，能观察到如下动作：1)首先首先 A 运行，它在带上打印运行，它在带上打印；2)B 开始运行，它查看带子，找到它的输入开始运行，它查看带子，找到它的输入；3)B 计算计算 q()=，然后将之与，然后将之与 合并，构成合并，构成 TM SELF 的描述的描述。4)B 打印这个描述，且停机。打印这个描述，且停机。8严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。图灵机 SELFq容易用任何程序设计语言实现这个构造，即得到一个

10、程序，容易用任何程序设计语言实现这个构造，即得到一个程序，输出就是它自己。输出就是它自己。q也可用自然语言实现：也可用自然语言实现：打印打印这个这个句子句子q考虑下面的变换考虑下面的变换打印下面语句的两个副本，在第二个副本上加引号；打印下面语句的两个副本，在第二个副本上加引号；“打印下面语句的两个副本，在第二个副本上加引号；打印下面语句的两个副本，在第二个副本上加引号；”q本例中，本例中，B 部分的构造是如下的句子：部分的构造是如下的句子：打印下面语句的两个副本，在第二个副本上加引号；打印下面语句的两个副本，在第二个副本上加引号；qA 部分与之相同，只是用引号将之括起来。部分与之相同，只是用引

11、号将之括起来。qA 提供了提供了 B 的一个副本给的一个副本给 B。9严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归定理定理定理定理定理6.26.2设设 T 是计算函数是计算函数 t:*的一个图灵机。的一个图灵机。则存在计算函数则存在计算函数 r:*的一个图灵机的一个图灵机 R，使得，使得对每一个对每一个 w，有：，有：r(w)=t(,w)只需要制造一个只需要制造一个 TM T，使之以自己的描述作为输入的一部分。，使之以自己的描述作为输入的一部分。然后递归定理就产生一个新的机器然后递归定理就产生一个新的机器 R，它和，它和

12、T 一样运行，只是一样运行，只是 R 的描述被自动地装在的描述被自动地装在 T 中中。ABT(=P)R 的控制器的控制器10严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归定理A 是由是由 q()描述的图灵机描述的图灵机 P。为了保持输入。为了保持输入w，重新设，重新设计计 q，使得，使得 P 印出任何预先在带上存在的串的输出。在印出任何预先在带上存在的串的输出。在 A 运行之后，带上包含运行之后，带上包含 w。B 是如下的过程：检查带子，并将是如下的过程：检查带子，并将 q 应用于带内容。结果是应用于带内容。结果是。然后。然

13、后 B 将将 A、B 和和 T 组成一个图灵机，并得到它的描组成一个图灵机，并得到它的描述述 =。最后，描述的编码和最后，描述的编码和 w 结合，在带上形成结果串结合，在带上形成结果串，并，并将控制传给将控制传给 T。ABT(=P)R 的控制器的控制器11严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归定理的术语q在设计图灵机算法时，可用如下方式使用递归定理。在设计图灵机算法时，可用如下方式使用递归定理。q如果你正在设计一个图灵机如果你正在设计一个图灵机 M，则可以在，则可以在 M 的算法的非形的算法的非形式描述中包含如下的短

14、语：式描述中包含如下的短语：q“得到自己的描述得到自己的描述”。一旦得到自己的描述，。一旦得到自己的描述，M 就能就能像使用其他已计算出来的值一样使用这个描述。像使用其他已计算出来的值一样使用这个描述。q例如，例如，M 可以简单打印出可以简单打印出；或者计算；或者计算 中的状态中的状态数；或模拟数；或模拟。q用递归定理来描述机器用递归定理来描述机器 SELF：SELF=“对于任意输入：对于任意输入：1)利用递归定理得到它自己的描述利用递归定理得到它自己的描述；2)打印打印。”12严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归

15、定理的术语q递归定理展示了怎样实现递归定理展示了怎样实现“获得自己的描述获得自己的描述”的构造。的构造。q为了产生机器为了产生机器 SELF，首先写下以下机器，首先写下以下机器 T：T=“对于输入对于输入：1)打印打印 并停机。并停机。”qTM T 得到得到 TM M 和它输入的串和它输入的串 w 的描述，它打印了的描述，它打印了 M 的的描述描述。然后递归定理展示怎样获得在输入。然后递归定理展示怎样获得在输入 w 上的上的 TM R，像，像 T 在输入在输入 上那样操作。因此上那样操作。因此 R 打印出打印出 R 的的描述，恰好是机器描述，恰好是机器 SELF 所需要得到的。所需要得到的。1

16、3严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归定理的应用q计算机病毒是一个计算机程序，它被设计成在计算机中传计算机病毒是一个计算机程序，它被设计成在计算机中传播它自己。为了实现自我复制的基本任务，可能使用到递播它自己。为了实现自我复制的基本任务，可能使用到递归定理证明中的结构。归定理证明中的结构。例例 计算机病毒；（计算机病毒；（Autoexec.BAT)从从A:盘盘 复制复制 到到B:盘盘 Echo This is a Virus program IF exist b:autoexec.bat goto Virus Go

17、to No_Virus :Virus B:Rename autoexec.bat auto.bat /准备冒名顶替准备冒名顶替 Copy a:autoexec.bat b:/自我复制部分自我复制部分 Echo I am Virus /诚实的自白诚实的自白 Del*.exe /实施破坏实施破坏 :No_virus A:Auto /调用原来调用原来 autoexec.bat，给出平安无事的假象，给出平安无事的假象14严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归定理的应用定理定理定理定理6.36.3ATM是不可判定的。是不可判定

18、的。假设图灵机假设图灵机 H 可判定可判定 ATM。构造下列图灵机。构造下列图灵机 B。B=“对于输入对于输入 w：1)由递归定理得到自己的一个描述由递归定理得到自己的一个描述。2)在输入在输入 上运行上运行 H。3)得到与得到与 H 相反的结果，相反的结果，即：如果即：如果 H 拒绝，则接受；如果拒绝，则接受；如果 H 接受，则拒绝。接受，则拒绝。”对输入对输入w，B 的结果与的结果与 H 相反，所以相反，所以 H 不可能判定不可能判定 ATM。15严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归定理的应用定义定义定义定义6

19、.46.4如果如果 M 是一个图灵机，则是一个图灵机，则 M 的描述的描述 的长度是的长度是描述描述 M 的串中所含的串中所含符号的个数符号的个数。如果没有与。如果没有与 M 等价等价的图灵机有更短的描述，则称的图灵机有更短的描述，则称 M 是是极小的极小的。令。令MINTM|M 是一个极小是一个极小 TM 16严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归定理的应用定理定理定理定理6.56.5MINTM不是图灵可识别的。不是图灵可识别的。假设假设 TM E 枚举枚举MlNTM，然后试图来得到矛盾。构造下列，然后试图来得到矛

20、盾。构造下列 TM C。C=“对于输入对于输入 w：1)由递归定理得到它自己的一个描述由递归定理得到它自己的一个描述。2)运行枚举器运行枚举器 E，直到一个比，直到一个比 C 的描述更长的机器的描述更长的机器D出现出现。3)在输入在输入 w上模拟上模拟 D。为为 MINTM 是无限的，故是无限的，故 E 的序列中必定含有的序列中必定含有 TM，其描述比，其描述比 C 的描述更长。的描述更长。因此，因此，C 的第二步最终将在某个的第二步最终将在某个 TM D上终止，且上终止，且 D 比比 C 更长。更长。然后然后 C 就模拟就模拟 D，且与之等价。，且与之等价。因为因为 C 比比 D 短且与之等

21、价，故短且与之等价，故 D 不可能是极小的，但不可能是极小的，但D又在又在 E 产生的序列中产生的序列中出现，这样就得到了矛盾。出现，这样就得到了矛盾。17严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。递归定理的应用定理定理定理定理6.66.6设设 t:*是一个可计算函数，则存在一个图灵是一个可计算函数，则存在一个图灵机机 F，使得，使得 t()描述一个与描述一个与 F 等价的图灵机。这等价的图灵机。这里假设如果串不是一个正确的图灵机编码，那么它里假设如果串不是一个正确的图灵机编码，那么它描述的图灵机立即拒绝。描述的图灵机立即拒

22、绝。设设 F 是下列图灵机。是下列图灵机。F =“对于输入对于输入w：1)由递归定理得到它自己的一个描述由递归定理得到它自己的一个描述。2)计算计算 t()得到一个得到一个 TM G 的描述。的描述。3)在输入在输入w上模拟上模拟 G。”显然，显然，和和 t()=描述了等价的图灵机，描述了等价的图灵机，因为因为 F 模拟模拟 G。18严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。主要内容主要内容6.1 递归定理递归定理6.1.1 自引用自引用6.1.2 递归定理的术语递归定理的术语6.1.3 应用应用6.2 逻辑理论的可判定性逻

23、辑理论的可判定性6.2.1 一个可判定的理论一个可判定的理论6.2.2 一个不可判定的理论一个不可判定的理论6.3 图灵可归约性图灵可归约性6.4 信息的定义信息的定义6.4.1 极小长度的描述极小长度的描述 6.4.2 定义的优化定义的优化 6.4.3 不可压缩的串和随机性不可压缩的串和随机性19严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。逻辑理论的可判定性q数理逻辑是数学的一个分支，它研究数学本身。数理逻辑是数学的一个分支，它研究数学本身。q数理逻辑关心如下问题：什么是定理？什么是证明？什么数理逻辑关心如下问题：什么是定理

24、？什么是证明？什么是真？算法能判定哪些命题是真的？所有真命题都是可证是真？算法能判定哪些命题是真的？所有真命题都是可证的吗？的吗？q关心的焦点：能否确定一个数学命题是真是假，以及这种关心的焦点：能否确定一个数学命题是真是假，以及这种问题的可判定性。问题的可判定性。20严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。逻辑理论的可判定性命题命题1称，有无限多个素数存在，在大约称，有无限多个素数存在，在大约2300年以前的欧几年以前的欧几里德时代，就已知道这个命题是真的。里德时代，就已知道这个命题是真的。命题命题2称为费马大定理，这个命

25、题几年前由安德鲁称为费马大定理，这个命题几年前由安德鲁威尔士威尔士(Andrew Wiles)证明为真。证明为真。命题命题3称，有无限多个素数对存在，这被称为孪生素数猜想称，有无限多个素数对存在，这被称为孪生素数猜想(twin prime conjecture)。它到现在还未被解决。它到现在还未被解决。q首先需要建立一个精确的语言来将这些问题形式化。我们首先需要建立一个精确的语言来将这些问题形式化。我们的要求是能够考虑如下数学命题：的要求是能够考虑如下数学命题：21严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。符号符号，称为称为

26、布尔运算布尔运算；“(”和和“)”是括号；符号是括号；符号 和和 是是量词量词；符号；符号x用来代表用来代表变元变元；符号；符号R1，Rk 称为称为关系关系。逻辑理论的可判定性为了将之进一步精确化，现在描述这个语言的字母表：为了将之进一步精确化，现在描述这个语言的字母表：22严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。公式q公式是字母表上的良构串。公式是字母表上的良构串。q形如形如 Ri(x1,x2,xj)的串是的串是原子公式原子公式，值，值 j 是关系符号是关系符号 Ri的的元数元数。q一个良构公式中所有出现的相同关系符号必

27、须有相同的元一个良构公式中所有出现的相同关系符号必须有相同的元数。数。q一个串一个串如满足一下条件，则是一个公式：如满足一下条件，则是一个公式：1)是一个原子公式；是一个原子公式；2)具有形式具有形式1 2 或或 1 2或或 1。其中其中1和和2 是更小的公式。是更小的公式。3)具有形式具有形式1 2 或或12 或或 1。其中其中 x1 或或 x1，其中，其中 1 是更小的公式。是更小的公式。23严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。公式q辖域：紧跟在量词化变元后的一对括号中的部分。辖域：紧跟在量词化变元后的一对括号中的

28、部分。q前束范式：所有量词都出现在公式的前面。前束范式：所有量词都出现在公式的前面。q自由变元：没有被量词的辖域所约束的变元。自由变元：没有被量词的辖域所约束的变元。q句子或命题：没有自由变元的公式。句子或命题：没有自由变元的公式。(1)x(F(x,y)G(x,z)(2)x(F(x)G(y)y(H(x)L(x,y,z)24严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例例6.7 在下列公式中，只有最后一个是句子：在下列公式中，只有最后一个是句子：逻辑理论的可判定性25严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到

29、及时发现、制止、汇报并处理各类违纪行为或突发事件。逻辑理论的可判定性q论域：覆盖变元可能的取值。论域：覆盖变元可能的取值。q将关系符号指定为确定的关系。而将关系符号指定为确定的关系。而关系关系是从论域上的是从论域上的k元组元组到到TRUE，FALSE的函数。的函数。q关系符号的元数必须和指派给它的关系和元数相同。关系符号的元数必须和指派给它的关系和元数相同。q论域连同关系到关系符号的指派一起论域连同关系到关系符号的指派一起称为称为模型模型。q形式上，一个形式上，一个模型模型 MM 是一个元组是一个元组(U,P1,Pk)，其中，其中U是是论域，论域，P1 到到 Pk 是指派给符号是指派给符号 R

30、1 到到 Rk 的关系。的关系。q模型语言模型语言：在公式的集合中，只使用此模型指派的关系符：在公式的集合中，只使用此模型指派的关系符号，且对每个关系符号，使用正确的元数。号，且对每个关系符号，使用正确的元数。q如果如果是某个模型语言中的句子，则是某个模型语言中的句子，则在这个模型中不为在这个模型中不为真就为假。真就为假。如果如果在模型在模型 M 中为真，则说中为真，则说 M 是是的一个的一个模型模型。26严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。逻辑理论的可判定性例例6.8 设设是句子是句子 x y R1(x,y)R1(y

31、,x)，模型，模型 M1=(N,)是如下的模型：它的论域是自然数集，它将是如下的模型：它的论域是自然数集，它将“小于或等小于或等于于”关系分配给符号关系分配给符号R1。显然。显然在在M1中为真，因为对于任意中为真，因为对于任意两个自然数两个自然数 a 和和 b，a b 和和 ba 必有一个成立。必有一个成立。但如果但如果M1将将“小于小于”关系（而不是关系（而不是“小于或等于小于或等于”关系）指关系）指派给派给R1，则，则将不真，因为当将不真，因为当 x 和和 y 相等时，它不再成立。相等时，它不再成立。q如果事先知道什么关系将指派给如果事先知道什么关系将指派给 Ri，就可以用这个关系的，就可

32、以用这个关系的惯用记号来代替惯用记号来代替 Ri，且按习惯，可用中缀记法。，且按习惯，可用中缀记法。q对于对于 M1，可以将，可以将写成写成 x y x y yx 27严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例例6.9 设设 M2 是如下的模型：它的论域是是实数集是如下的模型：它的论域是是实数集 R，且讲关，且讲关系系 PLUS 指派给指派给 R1，其中：只要当，其中：只要当 a+b=c 时时 PLUS(a,b,c)=TURE。则。则 M2 是是=y x R1(x,x,y)的一个模型。的一个模型。但如果用但如果用 N 代替

33、代替 R 作为作为 M2 的论域，则此句子为假。的论域，则此句子为假。逻辑理论的可判定性q如果如果 M 是一个模型，这个模型语言中所有是一个模型，这个模型语言中所有真句子的集合真句子的集合称称为为 M 的的理论系统理论系统，简称为，简称为理论理论，记为，记为Th(M)。28严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。一个可判定性的理论定理定理定理定理6.106.10Th(N,+)是可判定的。是可判定的。设设 3 包含所有高度为包含所有高度为 3 的的 0 和和 1 的列。的列。3 上的字符串给出三上的字符串给出三行行 0 和和

34、 1。把每一行看作一个二进制数，令。把每一行看作一个二进制数，令B=w 3|w 最下面的一行等于上面两行的和最下面的一行等于上面两行的和 则则 B 是正则的。是正则的。29严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。Th(N,+)是可判定的考虑如下一个实例：考虑如下一个实例：构造有限自动机：构造有限自动机：(x1,x2,x3)|x1+x2=x1+x3 然后构造然后构造NFA：(x1,x2)|x3 x1+x2=x1+x3 同样：同样：(x1)|x2 x3 x1+x2=x1+x3 为真时，得到为真时，得到(),为假时得到为假时得到

35、。30严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。一个可判定性的理论定理定理定理定理6.106.10Th(N,+)是可判定的。是可判定的。思路：对于输入为思路：对于输入为(N,+)的语言中的句子的语言中的句子检查其在模型中是否为真。检查其在模型中是否为真。=Q1x1Q2x2 Qlxl 对于对于 0l 的每一个的每一个i，令公式，令公式i 为为i=Qi+1xi+1Qi+2xi+2 Qlxl 这样，这样，0=且且 l=。对于从对于从 0 到到 l 的每个的每个 i，算法构造了一个有穷自动机，算法构造了一个有穷自动机 Ai，它识别如

36、下串的，它识别如下串的集合：这些串表示集合：这些串表示i 为真的数的为真的数的 i 元组。算法先直接构造元组。算法先直接构造 Ai，然后，然后，对对从从 l 向下到向下到 1 的每个的每个 i，它用，它用 Ai 构造构造 Ai-1。最后，一旦得到。最后，一旦得到 A0，算法就检，算法就检查查 A0是否接受空串。如果接受，则是否接受空串。如果接受，则为真，算法也就接受。为真，算法也就接受。31严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。Th(N,+)是可判定的则则 i=包含了所有包含了所有 0 和和 1 构成的构成的 i元列向量

37、。元列向量。i 上的每个串表示上的每个串表示 i 的二进制的二进制整数（沿行读）。令整数（沿行读）。令 0 =，其中，其中 是一个符号。是一个符号。现在介绍判定现在介绍判定 Th(N,+)的算法。对于输入的算法。对于输入(其中其中为句子为句子)，算法如下运，算法如下运行：写下行：写下，且对从，且对从 0 到到 l 的每个的每个 i，如同在证明思路中介绍的那样定义，如同在证明思路中介绍的那样定义i。再对每个这样的再对每个这样的i，由，由i构造有穷自动机构造有穷自动机Ai，使得只要，使得只要i(a1,ai)为真，为真，它就接受它就接受 i*上对应于上对应于i元组元组a1,ai 的串。的串。Ai 的

38、构造如下：的构造如下：对对 i 0，定义字母表，定义字母表 32严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。为构造第一个机器为构造第一个机器 Al，注意到，注意到l 是原子公式的布尔组合。是原子公式的布尔组合。在在 Th(N,+)的语言中，原子公式只有单个加法。的语言中，原子公式只有单个加法。对每个这样的单个加法，对每个这样的单个加法，可以构造可以构造个有穷自动机来计算这样的单个加法所对应的关系，然后将这个有穷自动机来计算这样的单个加法所对应的关系，然后将这些有穷自动机组合起来，就能给出自动机些有穷自动机组合起来，就能给出自动

39、机Al。这样做要涉及正则语言类对。这样做要涉及正则语言类对于交、并和补的封闭性，以计算原子公式的布尔组合。于交、并和补的封闭性，以计算原子公式的布尔组合。接下来说明怎么接下来说明怎么由由 Ai+1 来构造来构造 Ai。如果如果i=xi+1i+1，则构造则构造 Ai 使得它使得它的运行几乎与的运行几乎与Ai+1一样，区别在于一样，区别在于 Ai 非确定地猜非确定地猜 ai+1 的值的值，而不是将它作，而不是将它作为输入的一部分而接受。为输入的一部分而接受。更精确地说，对于更精确地说，对于 Ai+1 的每个状态，的每个状态，Ai 包含一个与之对应的状态；且包含一个与之对应的状态；且 Ai还包含一个

40、新的起始状态。每当还包含一个新的起始状态。每当 Ai 读下列符号时，读下列符号时，一个可判定性的理论33严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。这里每个这里每个 bi0,1 是数是数 ai 的某一位，它非确定地猜的某一位，它非确定地猜 z0,1，且在下列输入符号上模拟且在下列输入符号上模拟 Ai+1。一个可判定性的理论最初，最初，Ai 非确定地猜测非确定地猜测 ai+1的引导位，这些引导位对应于的引导位，这些引导位对应于 a1 到到 ai 中隐藏的引导中隐藏的引导 0。猜测的方法是：从它新的起始状态到所有状。猜测的方法是：

41、从它新的起始状态到所有状态非确定性地进行分叉，这些状态是态非确定性地进行分叉，这些状态是 Ai+1 以以 i+1中下列符号的中下列符号的串为输入、从它的开始状态所能到达的状态。串为输入、从它的开始状态所能到达的状态。显然，如果存在显然，如果存在ai+1，使得，使得Ai+1接受接受(a1,ai+1)，则，则Ai接受接受(a1,ai)。如果如果i=xi+1i+1，它等价于，它等价于 xi+1i+1。首先构造识别语言。首先构造识别语言 Ai+1 的补的有穷自动机，然后应用上述对于的补的有穷自动机，然后应用上述对于 量词的构造，最量词的构造，最后再一次应用补来得到后再一次应用补来得到Ai。有穷自动机有

42、穷自动机 A0 接收某个输入，当且仅当接收某个输入，当且仅当0为真。所以算法为真。所以算法的最后步骤是检查的最后步骤是检查 A0 是否接收是否接收 。如果是，则。如果是，则为真，且算为真，且算法接受它；否则，就拒绝。法接受它；否则，就拒绝。34严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。一个不可判定性的理论定理定理定理定理6.116.11Th(N,+,)是不可判定的。是不可判定的。引理引理引理引理6.126.12设设 M 是一个图灵机，是一个图灵机，w 是一个串：从是一个串：从 M 和和 w 能构能构造造(N,+,)的语言中的

43、公式的语言中的公式M,w，使得它只包含单，使得它只包含单个自由变元个自由变元 x，且句子，且句子 xM,w 为真当且仅当为真当且仅当M 接受接受w。35严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。一个不可判定性的理论定理定理定理定理6.136.13Th(N,+,)中可证命题的集合是图灵可识别的。中可证命题的集合是图灵可识别的。证明：如果证明：如果是可证的，则下列算法是可证的，则下列算法P接受其输入接受其输入。算。算法法P使用在可证性使用在可证性性质性质1中所说的证明检查器，检查每个可能成为中所说的证明检查器，检查每个可能成为的

44、证明的的证明的候选串。如果发候选串。如果发现一个侯选串正是一个证明，则接受它。现一个侯选串正是一个证明，则接受它。36严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。证明：用反证法。假设所有真命题都是可证的，利用这个假设来证明：用反证法。假设所有真命题都是可证的，利用这个假设来构造判定命题是否为真的算法构造判定命题是否为真的算法D，与定理，与定理6.11矛盾。矛盾。对于输入对于输入，算法算法D如下运行：在输入如下运行：在输入和和 上上并行地运行定并行地运行定理理6.13的证明中给出的算法的证明中给出的算法P。这两个命题总有一个为真

45、，根据假设，。这两个命题总有一个为真，根据假设，总有一个是可证的。因而总有一个是可证的。因而P在其中一个输入上停机。根据可证性性质在其中一个输入上停机。根据可证性性质2，如果如果是可证的，则是可证的，则为真；如果为真；如果 是可证的，则是可证的，则为假。所以算为假。所以算法法D能判定能判定的真假性。的真假性。一个不可判定性的理论定理定理定理定理6.146.14Th(N,+,)中存在不可证的真命题。中存在不可证的真命题。37严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。一个不可判定性的理论本定理的证明中描述的句子是本定理的证明中描

46、述的句子是 不可证的。不可证的。定理定理定理定理6.156.15 证明：设证明：设S是如下运行的是如下运行的TM。S“对于任意的输入：对于任意的输入：1)出递归定理得到它自己的描述出递归定理得到它自己的描述。2)用引理用引理6.12构造句子构造句子 。3)在输入在输入 上运行定理上运行定理6.13给出的算法给出的算法P。4)如果上一步接受，就接受；如果它停机且拒绝，则拒绝。如果上一步接受，就接受；如果它停机且拒绝，则拒绝。”设设 是算法是算法S的第二步所描述的句子的第二步所描述的句子 。为真，当是仅当为真，当是仅当S不接受不接受0（串（串0是随意选择的是随意选择的)。如果如果s能找到能找到 的

47、一个证明，的一个证明，S就接受就接受0，这个句子也就因，这个句子也就因之为假。一个假句子是不能被证明的，所以这种情形不可能发生。剩下之为假。一个假句子是不能被证明的，所以这种情形不可能发生。剩下的唯一可能性是的唯一可能性是S不能找到不能找到 的证明，因而的证明，因而S不接受不接受0。但我们已。但我们已宣布过宣布过 为真。为真。38严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。主要内容主要内容6.1 递归定理递归定理6.1.1 自引用自引用6.1.2 递归定理的术语递归定理的术语6.1.3 应用应用6.2 逻辑理论的可判定性逻辑理

48、论的可判定性6.2.1 一个可判定的理论一个可判定的理论6.2.2 一个不可判定的理论一个不可判定的理论6.3 图灵可归约性图灵可归约性6.4 信息的定义信息的定义6.4.1 极小长度的描述极小长度的描述 6.4.2 定义的优化定义的优化 6.4.3 不可压缩的串和随机性不可压缩的串和随机性39严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。图灵可归约性语言语言 B 的一个的一个谕示谕示(oracle)是一个是一个能够报告某个串能够报告某个串 w是否为是否为 B 的成员的外部装置的成员的外部装置。一个谕示图灵机是一种。一个谕示图灵

49、机是一种修改过的图灵机，它有询问一个谕示的额外能力。记修改过的图灵机，它有询问一个谕示的额外能力。记MB为对语言为对语言B有谕示的谕示图灵机。有谕示的谕示图灵机。定义定义定义定义6.166.16q考虑两个语言考虑两个语言ATM和和ATM，直观上它们可以互相归约。，直观上它们可以互相归约。实际上不能。实际上不能。40严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。图灵可归约性例例6.17 考虑考虑 ATM 的一个的一个谕示谕示。带。带 ATM 的的谕示谕示的一个的一个谕示谕示图灵机比普通的图灵机比普通的团灵机能判定更多的语言，这样的

50、图灵机能够判定团灵机能判定更多的语言，这样的图灵机能够判定ATM自身自身(显然成立显然成立)，它，它只要只要对输入询问它的谕示对输入询问它的谕示即可。它也能判定即可。它也能判定 ETM，即，即 TM 的空性质检查问的空性质检查问题，用的是下面称题，用的是下面称 TATM 的过程：的过程：TATM=“对于输对于输 入入，其中，其中 M 是一个是一个 TM：1)构造下面构造下面 TM N：N=“对任意输入：对任意输入：a)对对 *中的所有串并行运行中的所有串并行运行 M。b)如果如果 M 接受它们中的任何一个串，则接受。接受它们中的任何一个串，则接受。”2)询问询问谕示谕示以确定以确定 ATM是否