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

1、1、强迫化、计算理论、第6章计算性理论的高级专题，2、主要内容，6.1递归定理6.1.1自参考6.1.2递归定理的术语6.1.3适用6.2逻辑理论的判定性6.2.2可判定理论6.3图灵减少6.4信息定义6 . 4；数学逻辑关心以下问题：什么是定理？什么是证据？什么是真的？算法能判断哪些命题是真的吗？所有真正的命题都是可证明的吗？关注的焦点：数学命题是真的还是假的，以及能否确定这种问题的判断性。4，逻辑理论的判断性，根据命题1，据说存在无限数量的小数。大约2300年前，在欧几里得时代，已经知道牙齿命题是真的。命题2被称为费马大定理，牙齿命题几年前被安德鲁威尔士证实为事实。命题3据说存在一对被称为

2、孪生素数猜想的无限数。还没有解决。首先，为了格式化这些问题，必须构建正确的语言。我们的要求是可以考虑以下数学命题：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或

3、x1。其中1是较小的公式。7，公式，管辖区：两舍化收购正后方的一对括号的部分。前梁范式：所有数量词都出现在公式前面。自由收购：不受两家公司管辖的收购。句子或命题：没有自由参数的公式。(1) x (f (x，y) g (x，z)(2)x(f(x)g(y)y(h(x)l(x)关系是域的K元组到TRUE，FALSE的函数。关系符号的元数必须与分配给该符号的关系和元数相同。域与关系符号相关的分配一起称为模型。格式上，模型M是元组(U，P1，Pk)。其中U是可逆的，P1 Pk是指定给符号R1 Rk的关系。模型语言：在公式集中，仅使用在牙齿模型中指定的关系符号，并对每个关系符号使用正确的元数。如果是某种模

4、型语言的句子，在牙齿模型中是真的还是假的。在模型m中为真时，m称为模型。10，逻辑理论的判断性，示例6.8显然在M1中是真的，因为文章xy R1(x，y) R1(y，x)，模型M1=(N，)是以下模型，对于两个自然数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

5、，b，c)=true M2是yxr1 (x，x，y)的模型。但是如果用N代替R作为M2的逆反，牙齿句子是假的。，逻辑理论的判断性，如果是M牙齿模型，在牙齿模型语言中，所有实际句子的集合都被称为M的理论系统，简称为理论，用Th(M)记录。12，可确定性理论，设置3包含高度为3的所有0和1的列。3的字符串提供3行0和1。将每行视为二进制数，如果B=w3 | w的底部行等于上面两行的和，则B是规则的。13，Th(N，)可以配置(x1，x2，x3) | x1 x2=x1 x3，然后配置NFA: (x1，x2)来确定，14，有判断力的理论，思想=对于Q1x1Q2x2 Qlxl 0l中的每个I，公式I为i

6、=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元列矢量(由I=0和1组成)。I中的每个字符串表示I的二进制整数(沿行读取)。创建0=。其中是符号。现在介绍确定Th(N，)的算法。对于输入(其中是文章)，算法按如下方式运行：至少，对于从0到L的每个I，按照证明想法中的说明定义I。然后，对于其中的每个I，只

7、要I配置了可怜的robot 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作为输入的一部分，而是Ai不正确地推测Ai 1的值。更确

8、切地说，Ai包含与Ai 1中的每个状态相对应的状态。Ai还包含新的启动状态。每当ai读取下一个符号时，判定性理论，17，其中，每个bi0，1是数字Ai之一，在不确定z0，1的情况下，在下一个输入符号上模拟Ai 1。这是判定性理论，最初ai不确定ai 1的引导位，该引导位对应于隐藏的引导0(从a1到Ai)。推测的方法是从新的开始状态到所有状态不确定地分开。牙齿状态是Ai 1牙齿i 1中下一个符号的字符串的输入，可以从其开始状态到达的状态。(David aser，Northern Exposure(美国电视电视剧)，ai 1牙齿，ai 1牙齿接受(a1，ai 1)，Ai就会接受(a1，Ai)。如果

9、I=Xi 1i 1，则等于Xi 1i 1。首先配置用于补充识别语言Ai 1的穷机器人，然后应用上述两者的结构，最后再次应用补充以获得Ai。可怜的机器人A0只有在0牙齿真的情况下才接受输入。因此，算法的最后一步是验证是否收到A0牙齿。如果是，则为true，算法接受。否则拒绝。18，不可判定的理论，19，不可判定的理论，如果被证明，下一个算法P接受那个输入。算法P使用证据性特性1中提到的证明检查器检查每个可能证明的候选字符串。如果发现后线串就是一个证据，就接受它。20，证明：使用反证法。假设所有真命题都得到证明，利用牙齿假说来判定命题是否真实的算法D构成与定理6.11矛盾。对于输入，算法D的执行方

10、式如下：即，在输入并并行运行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就接

11、受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事实渡边杏。24，图灵可还原性，示例6.17考虑ATM的回规。有ATM会规的图灵机能比一般短期判定更多的语言。这种图灵机可以判定ATM本身。(显然成立)只需询问输入的回规。您还可以使用以下taTM流程来确定ETM(即TM)的null属性检查问题：TATM=对于输入，其中m表示TM: 1)以下TM

12、 N: N=对于任何输入：a) *的所有字符串并行运行m)B)如果接受m牙齿的这些字符串之一，请接受。点击2)为了确认ATM牙齿是否成立，询问回规。如果回规回答“否”，就接受。回答“是”就拒绝。“如果M的语言不是空的，则N接受每个输入。特别是允许零牙齿。因此回答“是”，TATM会拒绝。相反，如果M的语言是空的，TATM就会接受。所以TATM决定ETM。我们说可以皈依ETM牙齿ATM。25，图灵守规，26，图灵守规，B如果能判定，就可以用判定B的实际过程来代替B的回规。这样的话，就用判定A的谕令图灵机的普通图灵机代替了。图灵可还原性是映射可还原性的推广。如果是AmB，牙齿映射进入ATB，因为它可

13、用于提供关于B确定A的谕示图灵机。有自动取款机谕的图灵机很强。它可以解决很多普通图灵机无法解决的问题。但是，即使是这种强大的图灵机，也不能判定所有语言。，27，主要内容，6.1递归定理6.1.1自参考6.1.2递归定理的术语6.1.3适用6.2逻辑理论的判定性6.2.1可判定理论6.2.2可判定理论6.3图灵减少6.4信息定义628，信息定义，a= 0101010101010101010101010101010101010101010100100110011000110001100011000110001100110011011 。序列a有规律地重复01字符串17，信息量大，直观的感觉：表示意

14、义的最短尺寸可以测量信息量的规律性，说明短(信息量小)，有规律的说明和输入，重复17次01，TM w，以说明信息量，29，信息的定义，TM的说明，以及其输入X。您可以将代码：中的0写为“00”，将1写为“11”“01”，以此作为分隔符位置。TM分隔符W、30、定义6.20，如果存在多个设置这些字符串，请选择字典顺序下的第一个字符串。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直到停止，输出字符串s 2)生成输出字符串ss。Xx的说明